N-Queens I
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.."]]
暴力法
复杂度
时间 O(N^3) 空间 O(N)
思路
因为n皇后问题中，同一列不可能有两个皇后，所以我们可以用一个一维数组来表示二维棋盘上皇后的位置。一维数组中每一个值的下标代表着对应棋盘的列，每一个值则是那一列中皇后所在的行。这样我们可以只对一个一维数组进行深度优先搜索，来找出对于每一列，我们的皇后应该放在哪一行。在下一轮搜索之前，我们先检查一下新构成的数组是否是有效的，这样可以剪掉不必要的分支。检查的方法则是看之前排好的每一个皇后是否冲突。
代码
public class Solution { List > res; public List > solveNQueens(int n) { res = new LinkedList >(); int[] nqueens = new int[n]; helper(nqueens, n, 0); return res; } public void helper(int[] nqueens, int n, int i){ if(i == nqueens.length){ List one = new LinkedList (); // 构成表示整个棋盘的字符串 for(int num : nqueens){ // 构成一个形如....Q....的字符串 StringBuilder sb = new StringBuilder(); for(int j = 0; j < num; j++){ sb.append('.'); } sb.append('Q'); for(int j = num + 1; j < n; j++){ sb.append('.'); } one.add(sb.toString()); } res.add(one); } else { //选择下一列的数字 // 比如之前已经选了13xxxxxx，下一列可以选6，形成136xxxxx for(int num = 0; num < n; num++){ nqueens[i] = num; // 如果是有效的，继续搜索 if(isValid(nqueens, i)){ helper(nqueens, n, i+1); } } } } private boolean isValid(int[] nqueens, int i){ for(int idx = 0; idx < i; idx++){ // 检查对角线只要判断他们差的绝对值和坐标的差是否相等就行了 if(nqueens[idx] == nqueens[i] || Math.abs(nqueens[idx] - nqueens[i]) == i - idx){ return false; } } return true; }}
集合法
复杂度
时间 O(N^2) 空间 O(N)
思路
该方法的思路和暴力法一样，区别在于，之前我们判断一个皇后是否冲突，是遍历一遍当前皇后排列的列表，看每一个皇后是否冲突。这里，我们用三个集合来保存之前皇后的信息，就可以O(1)时间判断出皇后是否冲突。三个集合分别是行集合，用于存放有哪些行被占了，主对角线集合，用于存放哪个右上到左下的对角线被占了，副对角线集合，用于存放哪个左上到右下的对角线被占了。如何唯一的判断某个点所在的主对角线和副对角线呢？我们发现，两个点的行号加列号的和相同，则两个点在同一条主对角线上。两个点的行号减列号的差相同，则两个点再同一条副对角线上。
注意
主对角线row + col，副对角线row - col
代码
public class Solution { List > res = new LinkedList >();; Set rowSet = new HashSet (); Set diag1Set = new HashSet (); Set diag2Set = new HashSet (); public List > solveNQueens(int n) { helper(new LinkedList (), n, 0); return res; } public void helper(LinkedList tmp, int n, int col){ if(col == n){ List one = new LinkedList (); for(Integer num : tmp){ StringBuilder sb = new StringBuilder(); for(int j = 0; j < num; j++){ sb.append('.'); } sb.append('Q'); for(int j = num + 1; j < n; j++){ sb.append('.'); } one.add(sb.toString()); } res.add(one); } else { // 对于列col，看皇后应该放在第几行 for(int row = 0; row < n; row++){ int diag1 = row + col; int diag2 = row - col; // 如果三条线上已经有占据的皇后了，则跳过该种摆法 if(rowSet.contains(row) || diag1Set.contains(diag1) || diag2Set.contains(diag2)){ continue; } // 用回溯法递归求解 tmp.add(row); rowSet.add(row); diag1Set.add(diag1); diag2Set.add(diag2); helper(tmp, n, col + 1); diag2Set.remove(diag2); diag1Set.remove(diag1); rowSet.remove(row); tmp.removeLast(); } } }}
N-Queens II
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
暴力法
复杂度
时间 O(N^3) 空间 O(N)
思路
跟I的解法一样，只不过把原本构造字符串的地方换成了计数器加一。
代码
public class Solution { List > res; int cnt = 0; public int totalNQueens(int n) { int[] nqueens = new int[n]; helper(nqueens, n, 0); return cnt; } public void helper(int[] nqueens, int n, int i){ if(i == nqueens.length){ cnt++; } else { for(int num = 0; num < n; num++){ nqueens[i] = num; if(isValid(nqueens, i)){ helper(nqueens, n, i+1); } } } } private boolean isValid(int[] nqueens, int i){ for(int idx = 0; idx < i; idx++){ if(nqueens[idx] == nqueens[i] || Math.abs(nqueens[idx] - nqueens[i]) == i - idx){ return false; } } return true; }}
集合法
复杂度
时间 O(N^2) 空间 O(N)
思路
跟I的解法一样，只不过把原本构造字符串的地方换成了计数器加一。
代码
public class Solution { Set rowSet = new HashSet (); Set diag1Set = new HashSet (); Set diag2Set = new HashSet (); int cnt = 0; public int totalNQueens(int n) { helper(n, 0); return cnt; } public void helper(int n, int col){ if(col == n){ cnt++; } else { for(int row = 0; row < n; row++){ int diag1 = row + col; int diag2 = row - col; if(rowSet.contains(row) || diag1Set.contains(diag1) || diag2Set.contains(diag2)){ continue; } rowSet.add(row); diag1Set.add(diag1); diag2Set.add(diag2); helper(n, col + 1); diag2Set.remove(diag2); diag1Set.remove(diag1); rowSet.remove(row); } } }}