2020

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 上图为 8 皇后问题的一种解法。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。 示例：

输入：4 输出：[ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”],

["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ] 解释: 4 皇后问题存在两个不同的解法。

提示：

皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-queens 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

经典回溯算法，一开始还担心会不会时间不过后来发现是想多了。总之，用一个二维数组记录已经被占据的点位，一行的皇后位置暂定之后开始找下一行可行的皇后位置；每一行内部一个迭代：

class Solution { List<List<String>> ans; int[] array_ans; int[][] occupied; void occupy(int row, int col, int add, int n) { int tRow = row, tCol = col; while(tRow < n) { occupied[tRow][tCol] += add; ++tRow; } tRow = row; while(tCol >= 0 && tRow < n) { occupied[tRow][tCol] += add; ++tRow; --tCol; } tRow = row; tCol = col; while(tCol < n && tRow < n) { occupied[tRow][tCol] += add; ++tRow; ++tCol; } } void arrToAns(int n) { List<String> cur = new LinkedList<>(); StringBuilder builder = new StringBuilder(); for(int row = 0; row < n; ++row) { builder.setLength(0); int col = array_ans[row]; for(int i = 0; i < n; ++i) { builder.append(i == col ? 'Q' : '.'); } cur.add(builder.toString()); } ans.add(cur); } void tryRow(int row, int n) { for(int col = 0; col < n; ++col) { if(occupied[row][col] == 0) { array_ans[row] = col; if(row == n - 1) { arrToAns(n); } else { occupy(row, col, 1, n); tryRow(row + 1, n); occupy(row, col, -1, n); } } } } public List<List<String>> solveNQueens(int n) { ans = new LinkedList<>(); array_ans = new int[n]; occupied = new int[n][n]; tryRow(0, n); return ans; } }

看看题解有没有什么优化的方法。首先，其实判断是否被占领只需要三个整形数组就好了，分别表示列、左上右下对角线和右上左下对角线是否被占领。然后就是很无聊的用原始的代替java封装好的的优化：

class Solution { List<List<String>> ans; int[] array_ans; int[] colOccupied; int[] l2rOccupied; int[] r2lOccupied; boolean isNotOccupied(int row, int col, int n) { return colOccupied[col] == 0 && l2rOccupied[row - col + n - 1] == 0 && r2lOccupied[row + col] == 0; } void occupy(int row, int col, int add, int n) { colOccupied[col] += add; l2rOccupied[row - col + n - 1] += add; r2lOccupied[row + col] += add; } void arrToAns(int n) { List<String> cur = new LinkedList<>(); char[] builder = new char[n]; for(int row = 0; row < n; ++row) { int col = array_ans[row]; for(int i = 0; i < n; ++i) { builder[i] = (i == col ? 'Q' : '.'); } cur.add(String.valueOf(builder)); } ans.add(cur); } void tryRow(int row, int n) { for(int col = 0; col < n; ++col) { if(isNotOccupied(row, col, n)) { array_ans[row] = col; if(row == n - 1) { arrToAns(n); } else { occupy(row, col, 1, n); tryRow(row + 1, n); occupy(row, col, -1, n); } } } } public List<List<String>> solveNQueens(int n) { //回溯看看时间给不给过 ans = new LinkedList<>(); array_ans = new int[n]; colOccupied = new int[n]; l2rOccupied = new int[2 * n - 1]; r2lOccupied = new int[2 * n - 1]; tryRow(0, n); return ans; } }

4ms变成了3ms，不错。 题解还给出了一种用位代表对角线是否被占领的方法，但是这种方法并没有节省空间，因为用位表示上面的int[]可以得到相同的空间效果(其实能省n-1bit)…还有就是这种方法需要来回传递表示对角线状况的数，其实更繁琐一点…懒得实现了

另外，翻了下自己一年前第一遍做这个的代码，发现有一个优化。对第一行只搜索前一半，输出答案的时候如果在前一半就输出一个对称的：

class Solution { List<List<String>> ans; int[] array_ans; int[] colOccupied; int[] l2rOccupied; int[] r2lOccupied; boolean isNotOccupied(int row, int col, int n) { return colOccupied[col] == 0 && l2rOccupied[row - col + n - 1] == 0 && r2lOccupied[row + col] == 0; } void occupy(int row, int col, int add, int n) { colOccupied[col] += add; l2rOccupied[row - col + n - 1] += add; r2lOccupied[row + col] += add; } void arrToAns(int n) { List<String> cur = new LinkedList<>(); char[] builder = new char[n]; for(int row = 0; row < n; ++row) { int col = array_ans[row]; for(int i = 0; i < n; ++i) { builder[i] = (i == col ? 'Q' : '.'); } cur.add(String.valueOf(builder)); } ans.add(cur); cur = new LinkedList<>(); if(array_ans[0] < n / 2) { //输出一个对称的 for(int row = 0; row < n; ++row) { int col = array_ans[row]; for(int i = 0; i < n; ++i) { builder[n - i - 1] = (i == col ? 'Q' : '.'); } cur.add(String.valueOf(builder)); } ans.add(cur); } } void tryRow(int row, int n) { int maxCol = row == 0 ? (n + 1) / 2 : n; for(int col = 0; col < maxCol; ++col) { if(isNotOccupied(row, col, n)) { array_ans[row] = col; if(row == n - 1) { arrToAns(n); } else { occupy(row, col, 1, n); tryRow(row + 1, n); occupy(row, col, -1, n); } } } } public List<List<String>> solveNQueens(int n) { //回溯看看时间给不给过 ans = new LinkedList<>(); array_ans = new int[n]; colOccupied = new int[n]; l2rOccupied = new int[2 * n - 1]; r2lOccupied = new int[2 * n - 1]; tryRow(0, n); return ans; } }

嗯，变成了2ms，这可是82%和95%的区别啊！！！顺便我一年前写的纯迭代的回溯还蛮可爱的。也贴在这把纪念一下：

class Solution { public: void printAns(vector<vector<string>> & ans, int * pAns, int n) { string s; vector<string> temp; //第一个是不管咋样都需要打印的 for (int j = 0; j < n; j++) s.push_back('.'); for (int i = 0; i < n; i++) temp.push_back(s); ans.push_back(temp); for (int i = 0; i < n; i++) ans.back()[i][pAns[i]] = 'Q'; //从数组打印答案 第一行的数是0到n/2 - 1时打印俩 if (pAns[0] < n / 2) { //打印俩 ans.push_back(temp); for (int i = 0; i < n; i++) ans.back()[i][n - 1 - pAns[i]] = 'Q'; } } vector<vector<string>> solveNQueens(int n) { if (n == 1) return{ { "Q" } }; if (n < 4) return{}; vector<vector<string>> ans; //想不出来好方法暴力试凑 bool * pvCol = new bool[n];//特定列是否被占 bool * pvLCross = new bool[n * 2 - 1];//左向右对角线 索引计算col - row + n - 1 bool * pvRCross = new bool[n * 2 - 1];//索引计算col + row int * pAns = new int[n]; for (int i = 0; i < n; i++) pAns[i] = pvCol[i] = 0; for (int i = 0; i < n * 2 - 1; i++) pvLCross[i] = pvRCross[i] = 0; int row = 0, col = 0; while (pAns[0] <= (n + 1) / 2 - 1)//只用考虑左边一半 { //cout << "row = " << row << endl; //cout << "col = " << col << endl << endl; if (col == n)//下一行没戏了 { row--; col = pAns[row]; pvCol[col] = false; pvLCross[col - row + n - 1] = false; pvRCross[col + row] = false;//清空当前位置 col++; continue; } if (pvCol[col] || pvLCross[col - row + n - 1] || pvRCross[col + row])//如果当前位置不可行 { col++; continue; } else { pAns[row] = col; if (row != n - 1)//当前位置可行 找下一行 { pvCol[col] = true; pvLCross[col - row + n - 1] = true; pvRCross[col + row] = true;//装上当前位置 row++; col = 0; } else//找到一组答案 { printAns(ans, pAns, n); row--; col = pAns[row]; pvCol[col] = false; pvLCross[col - row + n - 1] = false; pvRCross[col + row] = false;//清空当前位置 col++; } } } delete[] pvCol; delete[] pvLCross; delete[] pvRCross; delete[] pAns; return ans; } };