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.."] ]
思路I：按行递归，在每个递归过程中按列循环，此时可能会有多种选择，所以使用回溯法。
注意每个小对角线也要check。
class Solution { public: vector<vector<string>> solveNQueens(int n) { if(n==0) return result; string str=""; for(int i = 0; i< n; i++){ //construct "...." str += '.'; } vector<string> item(n,str); backTracking(n, item, 0); return result; } void backTracking(int n, vector<string>& item, int depth){ //depth is the line number if(depth==n){ result.push_back(item); return; } for(int i = 0; i < n; i++){ //traverse column item[depth][i] = 'Q'; if(check(n,item, depth, i)) backTracking(n,item,depth+1); item[depth][i] = '.'; //back track } } bool check(int n, vector<string>& item, int i, int j){ int k; //check line to see if there's repetition for(k = 0; k < n; k++){ if(k==i) continue; if(item[k][j]=='Q') return false; } //check column to see if there's repetition for(k = 0; k < n; k++){ if(k==j) continue; if(item[i][k]=='Q') return false; } //check upper left for(k = 1; i-k >= 0 && j-k>=0; k++){ if(item[i-k][j-k]=='Q') return false; } //check lower right for(k = 1; i+k <n && j+k<n; k++){ if(item[i+k][j+k]=='Q') return false; } //check upper right for(k = 1; i-k >= 0 && j+k<n; k++){ if(item[i-k][j+k]=='Q') return false; } //check lower left for(k = 1; i+k <n && j-k>=0; k++){ if(item[i+k][j-k]=='Q') return false; } return true; } private: vector<vector<string>> result; };
思路II：对思路I，简化check
首先，对于每一行，不用check，因为在一个for循环中已经用回溯规避了重复。
对于列，我们用一个一维数组标记Q的位置，下标为行号，值为出现Q的列号。
对于对角线的check，check每一列Q所在的(row2,column2) 与当前点(row1, column1)是否满足|row1-row2| = |column1 - column2|，满足表示在一个对角线上。
class Solution { public: vector<vector<string>> solveNQueens(int n) { if(n==0) return result; vector<int> flag(n,-1); //每行的Q出现在哪列 backTracking(n, flag, 0); return result; } void backTracking(int n, vector<int>& flag, int depth){ //depth is the line number if(depth==n){ vector<string>item(n, string(n,'.')); //initialize as all '.' for(int i = 0; i < n; i++) item[i][flag[i]] = 'Q'; result.push_back(item); return; } for(int i = 0; i < n; i++){ //traverse column if(check(n,flag, depth, i)) { flag[depth] = i; backTracking(n,flag,depth+1); flag[depth] = -1; // back track } } } bool check(int n, vector<int>& flag, int i, int j){ for(int k = 0; k < i; k++){ if(flag[k] < 0) continue;//no Q in this column if(flag[k]==j) return false;//check columns if(abs(i-k)==abs(j-flag[k])) return false; //check cross lines } return true; } private: vector<vector<string>> result; };
思路III: 递归调用会有很多函数堆栈处理，参数拷贝，耗时耗内存，所以改用循环。思路还是back track，在没有答案的时候要回溯到上一行的Q位置之后的那个位置。
class Solution { public: vector<vector<string>> solveNQueens(int n) { if(n==0) return result; vector<int> flag(n,-1); int i = 0, j = 0; while(!(i==0 && j==n)){ if(j==n){ //no valid Q in this line, back track i--; j = flag[i]+1; flag[i] = -1; continue; } if(i==n){ //find one solution vector<string>item(n, string(n,'.')); //initialize as all '.' for(int k = 0; k < n; k++) item[k][flag[k]] = 'Q'; result.push_back(item); //back track i--; j = flag[i]+1; flag[i] = -1; continue; } if(check(n,flag, i, j)) { flag[i] = j; i++; j = 0; } else{ j++; } } return result; } bool check(int n, vector<int>& flag, int i, int j){ for(int k = 0; k < i; k++){ if(flag[k] < 0) continue;//no Q in this column if(flag[k]==j) return false;//check columns if(abs(i-k)==abs(j-flag[k])) return false; //check cross lines } return true; } private: vector<vector<string>> result; };
思路IV：通过为操作继续简化状态变量，将一维数组简化为整型。通过状态row、ld、rd分别表示在列和两个对角线方向的限制条件下，当前行的哪些地方不能放置皇后。
举例说明：前三行放置了皇后
他们对第3行（行从0开始）的影响如下：
（1）列限制条件下，第3行的0、2、4列（紫色线和第3行的交点）不能放皇后，因此row = 101010
（2）左对角线限制条件下，第3行的0、3列（蓝色线和第3行的交点）不能放皇后，因此ld = 100100
（3）右对角线限制条件下，第3行的3、4、5列（绿色线和第3行的交点）不能放皇后，因此rd = 000111
~(row | ld | rd) = 010000，即第三行只有第1列能放置皇后。
在3行1列这个位置放上皇后，row，ld，rd对下一行的影响为：
row的第一位置1，变为111010
ld的第一位置1，并且向左移1位（因为左对角线对下一行的影响是当前位置向左一个），变为101000
rd的第一位置1，并且向右移1位（因为右对角线对下一行的影响是当前位置向右一个），变为001011
第4行状态如下图
class Solution { public: vector<vector<string>> solveNQueens(int n) { if(n==0) return result; mask = (1<<n) - 1; //Bit operation: 低n位置1 vector<string> cur(n, string(n,'.')); backTracking(0, 0, 0, cur, 0); return result; } void backTracking(const int row, const int ld, const int rd, vector<string>& cur, int depth){ //depth is the line number if(row==mask){ //find one solution result.push_back(cur); return; } int pos, p; pos = mask & (~(row|ld|rd)); //pos置1的位置表示可以放置Q while(pos){ p = pos & (~pos + 1);//Bit Operation: 获取pos最右边的1 pos = pos - p; //把pos最右边的1清0 setQueen(cur, depth, p, 'Q'); backTracking(row|p, (ld|p)<<1, (rd|p)>>1, cur, depth+1); //iterate next line setQueen(cur, depth, p, '.'); //back track } } void setQueen(vector<string>& cur, int depth, int p, char val){ int col = 0; while(!(p&1)){ p >>= 1; col++; } cur[depth][col]=val; } private: vector<vector<string>> result; int mask; };