完成过程中的一些问题:
- 一开始没有审题,只设置了两个数组判断行列上是否有元素,没有考虑斜线的问题。
- 出现了行的重复,对行只需要递归,不需要循环。
- 思路:按行摆放棋子,摆放棋子时检查列上和斜线上是否有棋子,如果有,进行剪枝。
辅助函数:
1、leanLine
:位置
(
r
o
w
,
c
o
l
)
(row, col)
(row,col)的45°和135°斜线是否有元素占据。
public boolean leanLine(int row, int col) {
// 检查45度往上
int i = row - 1;
int j = col + 1;
while (i >= 0 && j < n){
if (used[i][j]) {
return false;
}
i--;
j++;
}
// 45度往下
i = row + 1;
j = col - 1;
while (i < n && j >= 0) {
if (used[i][j]) {
return false;
}
i++;
j--;
}
// 检查135度往上
i = row - 1;
j = col - 1;
while (i >= 0 && j >= 0) {
if (used[i][j]) {
return false;
}
i--;
j--;
}
// 135度往下
i = row + 1;
j = col + 1;
while (i < n && j < n){
if (used[i][j]) {
return false;
}
i++;
j++;
}
return true;
}
2、从boolean[][]
的棋盘得到指定输出。
public List<String> getOutput() {
// 从used数组得到输出
List<String> strs = new ArrayList<>();
for (boolean[] row: used) {
StringBuilder s = new StringBuilder();
for (boolean b : row) {
s.append(b ? "Q" : ".");
}
strs.add(s.toString());
}
return strs;
}
主要函数:
DFS(i)
:第i行上方的棋子已经选择好,只需要考虑第i行以下部分。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
class Solution {
boolean[] colsUsed; // 快速判断行列有无元素
boolean[][] used; // 判断斜线有无元素,以及负责输出
int count = 0; // 已经布置的queen的个数
int n;
List<List<String>> res = new ArrayList<>();
public boolean leanLine(int row, int col) { ... }
public List<String> getOutput() { ... }
public List<List<String>> solveNQueens(int n) {
this.n = n;
colsUsed = new boolean[n];
used = new boolean[n][n];
DFS(0);
return res;
}
public void DFS(int i) {
// 从第i行开始选择,上方的棋子已经选择好
if (count == n) {
res.add(getOutput());
return;
}
for (int j = 0; j < n; j++) {
// 同一列有棋子,剪枝
if (colsUsed[j]) {
continue;
}
// 斜线上有棋子,剪枝
if (!leanLine(i, j)) {
continue;
}
count++;
colsUsed[j] = true;
used[i][j] = true;
DFS(i + 1);
colsUsed[j] = false;
used[i][j] = false;
count--;
}
}
}