leetCode 51. N-Queens | 回溯問題(N皇后問題) | hard

51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

題目大意：

給定一個(gè)n*n的棋盤，在棋盤里放入n個(gè)Q，要求每一行，每一列都只有一個(gè)Q，而且每個(gè)Q的對(duì)角線上只能有一個(gè)Q。

思路：

這是一個(gè)典型的回溯問題。一條路走到黑，走到黑了退回來一步，然后再走，直到走通一條路。退回來繼續(xù)尋找其他出路。

解決這個(gè)問題需要解決幾個(gè)關(guān)鍵點(diǎn)：

1.關(guān)于保存一個(gè)可行路線的數(shù)據(jù)結(jié)構(gòu)的選擇

保存一個(gè)可行路線的時(shí)候，選擇數(shù)據(jù)結(jié)構(gòu)時(shí)選擇一個(gè)2維數(shù)組還是什么這里需要?jiǎng)幽X筋了，最后衡量，選擇了一維數(shù)組。

比如說4-Queue時(shí)一個(gè)合法路線為

[".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

那么它對(duì)應(yīng)的1位數(shù)組為{1，3，0，2}

解釋：

1是數(shù)組第0位，對(duì)應(yīng)二維數(shù)組第0行，對(duì)應(yīng)的值是1，表示在第0行時(shí)，第1列可以放Q。

3是數(shù)組第1位，對(duì)應(yīng)二維數(shù)組第1行，對(duì)應(yīng)的值是3，表示在第1行時(shí)，第3列可以放Q。

0是數(shù)組第2位，對(duì)應(yīng)二維數(shù)組第3行，對(duì)應(yīng)的值是0，表示在第2行時(shí)，第0列可以放Q。

2是數(shù)組第3位，對(duì)應(yīng)二維數(shù)組第3行，對(duì)應(yīng)的值是2，表示在第3行時(shí)，第2列可以放Q。

數(shù)組的下標(biāo)為行，數(shù)組的元素值為列。通過行列來確定Q的位置。

2.關(guān)于如何判斷要加入的元素是否為合法

要插入一個(gè)合法元素到合法位置上，需要判斷是否合法，在這里使用了函數(shù)

bool isValid(int curIndex, int val ,int n, vector<int> &a)

curIndex表示當(dāng)前要插入的元素在合法數(shù)組中的下標(biāo)，也就是行。val是要插入的列值。n是有多少個(gè)Queue，a是保存臨時(shí)合法路線的一個(gè)數(shù)組。

判斷a[i] == val 相等說明該列重復(fù)。

對(duì)角線的斜率為1或-1，所以如果 |val - a[i]| / |cur - i| == 1，那么說明在同一對(duì)角線上。

3.將合法的路徑一個(gè)一個(gè)的放入結(jié)果臨時(shí)數(shù)組中。從結(jié)果臨時(shí)數(shù)組轉(zhuǎn)換成結(jié)果數(shù)組。

代碼如下：

class Solution {
public:
    //判斷當(dāng)前要插入的值val在這個(gè)位置curIndex是否合法
    bool isValid(int curIndex, int val ,int n, vector<int> &a)
    {
    	if (curIndex < n )
    	{
    		for (int i = curIndex - 1; i >= 0; --i)
    		{
    			if (a[i] == val)//判斷列上是否有重復(fù)的
    				return false;
    		}
    		for (int i = curIndex - 1; i >= 0; --i)
    		{
    			if (abs(val - a[i]) == (curIndex - i))//判斷斜線上是否有重復(fù)的
    			{
    				return false;
    			}
    		}
    		return true;
    	}
    
    	return false;
    }
    
    void PutQueens(int val , vector<int> &a)//將合法的值放入當(dāng)前臨時(shí)結(jié)果數(shù)組
    {
    	a.push_back(val);
    }
    //start開始的行數(shù)，也就是第start+1個(gè)Queue的放置
    void solveNQueensToIntVector(int start,int n, vector<int> &cur,
    vector<vector<int>> &result)//先轉(zhuǎn)換成int來處理
    {
    	if (cur.size() == n)
    	{
    		result.push_back(cur);
    		return;
    	}
    	if (start == n)
    		return;
        //典型的回溯套路
    	for (int i = 0; i < n; i++)
    	{
    		if (!isValid(cur.size(),i, n, cur))
    			continue;
    		vector<int> temp(cur);//保存變化前的vector
    		PutQueens(i, cur);
    		solveNQueensToIntVector(start + 1, n, cur, result);
    		cur.swap(temp);
    	}
    }
    
    vector<vector<string>> solveNQueens(int n) 
    {
    	vector<int> cur; 
    	vector<vector<int>> tempResult;
    	vector<vector<string>> result;
    	solveNQueensToIntVector(0,n,cur,tempResult);
    
    	//vector<vector<int>> tempResult 轉(zhuǎn)換成 目標(biāo)結(jié)果result
    
    	for (int i = 0; i < tempResult.size(); i++)
    	{
    		vector<string> floorVector;
    		string floor;
    
    		for (int j = 0; j < tempResult[i].size(); j++)
    		{
    			for (int k = 0; k < tempResult[i][j]; k++)
    			{
    				floor += ".";
    			}
    			floor += "Q";
    			for (int k = tempResult[i][j] + 1; k < n ; k++)
    			{
    				floor += ".";
    			}
    			floorVector.push_back(floor);
    			floor.clear();
    		}
    		result.push_back(floorVector);
    		floorVector.clear();
    	}
    	return result;
    }
};

本題總結(jié)：

回溯問題在N-Queue這道題中體現(xiàn)的十分明顯。

（3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。

回溯就是讓計(jì)算機(jī)自動(dòng)的去搜索，碰到符合的情況就結(jié)束或者保存起來，在一條路徑上走到盡頭也不能找出解，就回到原來的岔路口，選擇一條以前沒有走過的路繼續(xù)探測(cè)，直到找到解或者走完所有路徑為止。就這一點(diǎn)，回溯和所謂的DFS（深度優(yōu)先搜索）是一樣的。那現(xiàn)在的關(guān)鍵是，怎么實(shí)現(xiàn)搜索呢？回溯既然一般使用遞歸來實(shí)現(xiàn)，那個(gè)這個(gè)遞歸調(diào)用該如何來寫呢？我的理解就是，先判斷這一次試探是否有效，如果有效則加入這個(gè)元素，然后進(jìn)行下一次遞歸，遞歸后恢復(fù)加入這個(gè)合法元素之前的狀態(tài)，進(jìn)行下一次循環(huán)；如果無效則直接進(jìn)行下一次循環(huán)。

2016-08-15 15:53:37