51. N-Queens

51. N-Queens

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){
//print(border);
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;
}
}
}
}
}
Author

Xander

Posted on

2022-06-04

Updated on

2022-06-05

Licensed under

Comments