问题描述
给你一个n*n的棋盘，如何在上面放置n个皇后。
放置皇后时有如下规则，同一行、同一列，左右对角线均不能有其他皇后。
举个例子：
Update at 2020_0723
多谢Y总
重新梳理下思路：
首先，创建一个n * n的char类型数组g，并将其初始化为.。
然后，进行DFS，当r == n时，说明我们找到了一个答案，
那么将g数组中的数据构建成一个List<String>。
接着，继续进行DFS递归遍历。
重点在于，如何判断当前结点是否可以放皇后？
我们使用三个boolean数组进行判断，分别是列col、正对角线dg和反对角线udg。
其中正反对角线的判断有点小技巧：
先来看正对角线，如图：
它的特点是：col - row是个固定的值，为了防止负数，我们将其加一个n。
再来看反对角线：
它的特点是：col + row是一个固定的值。
来看下完整实现:
class Solution {
int N = 20;
char[][] g = new char[N][N];
boolean[] col = new boolean[N]; // 列
boolean[] dg = new boolean[N]; // 正对角线
boolean[] udg = new boolean[N]; // 斜对角线
List<List<String>> ans = new LinkedList<>();
public void dfs(int r, int n){
// 找到一个答案
if (r == n){
List<String> child = new LinkedList<>();
for (int i = 0; i < n; i++){
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; j++){
sb.append(g[i][j]);
}
child.add(new String(sb));
}
ans.add(child);
return;
}
// DFS递归遍历
for (int c = 0; c < n; c++){
// 确保当前单元可以放皇后
if (!col[c] && !dg[c + r] && !udg[c - r + n]){
g[r][c] = 'Q';
col[c] = true; dg[c + r] = true; udg[c - r + n] = true;
dfs(r + 1, n);
// 恢复现场
col[c] = false; dg[c + r] = false; udg[c - r + n] = false;
g[r][c] = '.';
}
}
}
public List<List<String>> solveNQueens(int n) {
// 初始化棋盘
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
g[i][j] = '.';
}
}
dfs(0, n);
return ans;
}
}
解法1
Thanks
N Queen Problem Using Backtracking Algorithm
此题应该使用回溯思想。
思路是这样的：
首先，我们构建一个n*n的字符矩阵，初始值赋为.。
然后，进行递归调用，我们用一个字段来标识当前行row，初始值为0。
接着进入递归函数内部。
第一步，我们的目标是什么？
一旦row == chess.length，就说明已经生成了一个答案。
所以，我们构建字符串列表，并将其放入最终结果列表ans中。
private List<String> construct(char[][] chess){
List<String> child = new LinkedList<>();
for (char[] ch: chess){
child.add(new String(ch));
}
return child;
}
第二步，依次遍历每列。
需要判断当前位置是否允许放置皇后，判断的依据就是当前行、列、左右斜对角是否有皇后。
这边有个判断技巧：
假设当前单元的坐标为(row, col)，左斜对角线的坐标为(i, j)，有如下规律：
row - col == i - j。
同理，右对角线有如下规律：
row + col == i + j
private boolean isValid(char[][] chess, int row, int col){
for (int i = 0; i < chess.length; i++){
for (int j = 0; j < chess[0].length; j++){
if (chess[i][j] == 'Q' && (i - j == row - col || i + j == row + col ||
i == row || j == col)){
return false;
}
}
}
return true;
}
最后，就是常规回溯操作。
来看下实现：
class Solution {
public List<List<String>> solveNQueens(int n) {
char[][] chess = new char[n][n];
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
chess[i][j] = '.';
}
}
List<List<String>> ans = new LinkedList<>();
bt(chess, ans, 0);
return ans;
}
private void bt(char[][] chess, List<List<String>> ans, int row){
// Goal
if (row == chess.length){
ans.add(construct(chess));
return;
}
// Choice
for (int col = 0; col < chess.length; col++){
if (isValid(chess, row, col)){
chess[row][col] = 'Q';
bt(chess, ans, row + 1);
chess[row][col] = '.';
}
}
}
private boolean isValid(char[][] chess, int row, int col){
for (int i = 0; i < chess.length; i++){
for (int j = 0; j < chess[0].length; j++){
if (chess[i][j] == 'Q' && (i - j == row - col || j + i == col + row ||
i == row || j == col)){
return false;
}
}
}
return true;
}
private List<String> construct(char[][] chess){
List<String> child = new LinkedList<>();
for (char[] ch: chess){
child.add(new String(ch));
}
return child;
}
}
Enjoy it !
一位喜欢提问、尝试的程序员
（转载本站文章请注明作者和出处 姚屹晨-yaoyichen）