问题描述
给你一个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)