Question
The n-queens puzzle is the problem of placing n
queens on an n x n
chessboard such that no two queens attack each other.
Given an integer n
, return all distinct solutions to the n-queens puzzle . You may return the answer in any order .
Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q'
and '.'
both indicate a queen and an empty space, respectively.
Solution 话说今天出这道题真的不是搞事情嘛?
八皇后问题,回溯+剪枝。按顺序搜索可以减少情况的重复计算。 由于棋盘的大小为n * n,要放n个皇后,因此每一行(列)上都有且只有一位皇后 。 我们可以依顺序逐行回溯 ,对逐行的每一列进行回溯。 由于每一行的可选位置都减少1,因此时间复杂度为O(N!)。
回溯 通过一个char数组board[][]记录棋子状态。将board[][]初始化为’.’。 遍历这一行的所有列,如果该位置有效,则board[i][j]改为’Q’,将这个点设置为有棋子,并递归下一行。 回溯,将board[i][j]重新设置为’.’。
当递归次数达到n时,将char[]数组转换为字符串加入答案。
辅助方法 isValid 检测该位置是否有效。即该位置的路径上是否已经有棋子,或该位置已经有棋子。 由于我们的回溯方法是逐行确定棋子位置,因此不需要查看全部八个方向,而是查看之前已经遍历过的行 即可。
Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 class Solution { List<List<String>> ret; int size; int [][] operations; public List<List<String>> solveNQueens (int n) { ret = new ArrayList <>(); size = n; operations = new int [][]{{-1 ,-1 },{-1 ,1 },{-1 ,0 }}; char [][] board = new char [n][n]; for (char [] s : board){ Arrays.fill(s,'.' ); } backtracking(board,0 ,0 ); return ret; } private void backtracking (char [][] board, int n, int i) { if (n == size){ List<String> ans = new ArrayList <>(); for (char [] s : board) ans.add(new String (s)); ret.add(ans); return ; } for (int j = 0 ; j < size; j++){ if (isValid(board, i, j)){ board[i][j] = 'Q' ; backtracking(board, n+1 , i+1 ); board[i][j] = '.' ; } } } private boolean isValid (char [][] board, int i, int j) { for (int [] operation : operations){ int p = i + operation[0 ]; int q = j + operation[1 ]; while (p >= 0 && p < size && q >= 0 && q < size){ if (board[p][q] == 'Q' ) return false ; p += operation[0 ]; q += operation[1 ]; } } return true ; } }
Solution 2 简单回溯。 在回溯时搜索二维位置,因此增加了时间复杂度,正常是过不了的。 通过按顺序 进行搜索(只搜索当前行之后的位置)进行剪枝。
Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 class Solution { List<List<String>> ret; int size; int [][] operations; HashSet<String> set; public List<List<String>> solveNQueens (int n) { ret = new ArrayList <>(); size = n; operations = new int [][]{{1 ,1 },{1 ,-1 },{1 ,0 },{0 ,1 },{0 ,-1 }}; backtracking(new int [n][n],0 ,0 ); return ret; } private void backtracking (int [][] border, int n, int start) { if (n == size){ List<String> ans = new ArrayList <>(); for (int i = 0 ; i < size; i++){ StringBuffer sb = new StringBuffer (); for (int j = 0 ; j < size; j++){ if (border[i][j] == 1 ){ sb.append("Q" ); } else { sb.append("." ); } } ans.add(sb.toString()); } ret.add(ans); return ; } for (int i = start; i < size; i++){ for (int j = 0 ; j < size; j++){ if (border[i][j] == 0 ){ border[i][j] = 1 ; List<int []> temp = new ArrayList <>(); for (int [] operation : operations){ int p = i, q = j; while (p >= 0 && p < size && q >= 0 && q < size){ if (border[p][q] == 0 ){ border[p][q] = 2 ; temp.add(new int []{p,q}); } p += operation[0 ]; q += operation[1 ]; } } backtracking(border, n+1 , i+1 ); for (int [] t : temp){ border[t[0 ]][t[1 ]] = 0 ; } border[i][j] = 0 ; } } } } }