N 皇后（ LeetCode 51 ）
一、题目描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]]
解释：4 皇后问题存在两个不同的解法。
二、题目解析
三、参考代码
1、Java 代码
class Solution {
// 保存所有符合要求的解
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
// attack 用来表示皇后的攻击范围
int[][] attack = new int[n][n];
// queen 用来记录皇后的位置
char[][] queen = new char[n][n];
// 初始化二维数组 queen 中所有的元素为 '.'
for(char[] c : queen) {
Arrays.fill(c, '.');
}
// 初始化二维数组 attack 中所有的元素为 0
// 0 代表没有皇后能攻击得到
// 1 代表出于任意一个皇后的攻击范围内
for(int[] c : attack) {
Arrays.fill(c, 0);
}
// 从棋盘的第 0 行第 0 列处理 n 皇后的情况
backtrack(0,n,queen,attack);
// 最后，返回所有符合要求的解
return res;
}
// 很显然，每一行只能放置一个皇后，所以我们每一行每一行的来放置皇后
// k 表示当前处理的行
// n 表示需要放置多少个皇后，同时也代表棋盘的大小为 n * n
// queen 用来记录皇后的位置
// attack 用来表示皇后的攻击范围
private void backtrack(int k ,int n , char[][] queen,int[][] attack){
// 如果发现在棋盘的最后一行放置好了皇后，那么就说明找到了一组符合要求的解
if(k == n){
// 由于 queen 为二维字符数组，所以需要转换为字符串数组
List<String> list = new ArrayList<>();
// 遍历二维数组 queen
// 取出 queen 的每一行字符数组 c
for (char[] c : queen) {
// 把字符数组 c 中的所有字符转换为字符串的形式进行拼凑
// 比如 ['.','Q','.','.',]
// 转换为 '.Q..'
// 把这个字符串加入到 list 中
list.add(String.copyValueOf(c));
}
// list 即为一组符合要求的解，把它加入到结果数组中
res.add(list);
// 由于遍历完了所有的行，无需再遍历下去，所以返回
return;
}
// 每一行只能放置一个皇后
// 并且每一列也只能放置一个皇后
// 所以在 k 行中，从 0 列到 n - 1 列，判断皇后应该放置到哪个位置
for(int i = 0 ; i < n ; i++){
// 如果发现 attack[k][i] == 0
// 说明这个位置不在任何一个皇后的攻击范围内
// 所以可以考虑放置皇后
if(attack[k][i] == 0){
// 如果在 ( k , i ) 位置放置了皇后，那么就需要考虑在 k + 1 行应该怎么放置其它的皇后了
// 由于有可能在( k , i ) 位置放置了皇后之后，在后续的其它行会无法再放置其它的皇后
// 那么就需要回到 ( k , i ) 的状态，考虑能不能在 ( k , i + 1 )的位置放置
// 为了能够回到 ( k , i ) 的状态，所以需要先记录此时的 attack
// 使用一个临时的二维数组，深度拷贝 attack
// 如果不使用深度拷贝，而是直接使用 int[][] temp = c
// 会导致 attack 发生改变是 temp 也会发生改变
// 这样也就无法保存之前的状态了
int[][] temp = new int[n][n];
// 通过两个 for 循环，把 attack 中的所有元素深度拷贝到 temp
for(int l = 0 ; l < n ; l++){
for( int m = 0 ; m < n ; m++){
temp[l][m] = attack[l][m];
}
}
// queen 用来记录皇后的位置
// 那么 ( k , i ) 的位置 queen[k][i] = 'Q'
queen[k][i] = 'Q';
// 由于新放置了一个皇后，所以攻击范围又更多了
// 所以需要更新 attack 数组
// 新放置皇后的坐标为 ( k , i ) ，同样的需要更新它的八个方向
checkQueenAttack(k,i,attack);
// 如果在 ( k , i ) 位置放置了皇后，那么就需要考虑在 k + 1 行应该怎么放置其它的皇后
// 递归的调用 backtrack 在 k + 1 行放置皇后
backtrack(k + 1,n,queen,attack);
// 递归结束后，拿走皇后，恢复 attack 的状态，考虑能不能在 ( k ,i + 1 )的位置放置
attack = temp;
// 恢复 queen 的状态，说明此时皇后不放置在( k , i ) 位置
queen[k][i] = '.';
}
}
}
// 坐标 ( x , y) 为皇后所处的位置
// 更新 attack
private void checkQueenAttack(int x ,int y,int[][] attack){
// 对于每一个坐标 (x,y) 来说，都有上、下、左、右、左上、左下、右上、右下 八个方向
//【左上】的坐标为 (x - 1, y - 1)
//【上】的坐标为 (x - 1, y )
//【右上】的坐标为 (x - 1, y + 1)
//【左】的坐标为 (x, y + 1)
//【右】的坐标为 (x , y - 1)
//【左下】的坐标为 (x + 1, y - 1)
//【下】的坐标为 (x + 1, y)
//【右下】的坐标为 (x + 1, y + 1)
// 通过两个一维数组可以表示这八个方向
// dx 表示 x 的方向
int dx[] = { -1 , -1 , -1 , 0 , 0 , 1 , 1 , 1 };
// dy 表示 y 的方向
int dy[] = { -1 , 0 , 1 , -1 , 1 , -1 , 0 , 1 };
// 皇后所处的坐标肯定是皇后能攻击的位置，设置为 1
attack[x][y] = 1;
// 以坐标 ( x , y) 为中心，去更新它八个方向的坐标
for(int j = 0 ; j < 8; j++){
// 由内向外的进行更新
for(int i = 1 ; i < attack.length ; i++){
// 新的位置的坐标行为 x + i * dx[j]
int nx = x + i * dx[j];
// 新的位置的坐标列为 y + i * dy[j]
int ny = y + i * dy[j];
// 如果新位置的坐标在 n * n 的棋盘范围内
if(nx >= 0 && nx < attack.length && ny >= 0 && ny < attack.length){
// 那么这些位置就是在坐标为 （x，y）的皇后的攻击范围内，更新为 1
attack[nx][ny] = 1;
}
}
}
}
}
2、C++ 代码
3、Python 代码
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
# 更新皇后的坐标[x][y]之后更新attack的位置
def updateAttack(x,y,attack):
# 更改attack[x][y]上、下、左、右、左上、左下、右上、右下的0为1
# dx表示x的方向，dy表示y的方向
dx = [-1, -1, 1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
# 八个方向更新
for j in range(8):
# 内到外更新
for i in range(n):
nx = x + i * dx[j]
ny = y + i * dy[j]
# 新坐标在棋盘内则更新
if nx >= 0 and nx < n and ny >= 0 and ny < n:
attack[nx][ny] = 1
# k为当前处理的行
# n表示需要放置的皇后数和棋盘大小
# queen皇后的位置
# attack攻击范围
def backtrack(k,n,queen,attack):
print(k)
# 如果棋盘最后一行放置好了皇后则找到一组解
if k == n:
rl = []
# queen为分隔的二维数组，去转为字符串数组
for i in queen:
rl.append(''.join(i))
res.append(rl)
return
# 每行每列只能放一个皇后，所以在k行中，从0～n-1列判断皇后放置的位置
for i in range(n):
# 如果attack[k][i]为0，即不在攻击范围内，可考虑放置皇后
if attack[k][i] == 0:
# k行i列放置后需考虑k+1行如何放置
# 若k+1无法放置，需回退，考虑k行i+1列能否放置
# 用临时数组记录k行i列时的attack状态
# temp = attack[:]
# 要使用深度拷贝
temp = copy.deepcopy(attack)
queen[k][i] = 'Q'
# 更新attack数组
updateAttack(k,i,attack)
# print(attack,queen,'after')
# 递归的调用backtrack考虑在k+1行放置皇后
backtrack(k+1,n,queen,attack)
# 递归结束移走皇后恢复[k][i]不能放置状态
attack = temp
# print(attack,3)
# 恢复queen状态
queen[k][i] = '.'
res = []
# attack表示皇后攻击范围
# 初始化攻击为0
'''0表示没有皇后能攻击得到，1表示处于任意一个皇后的攻击范围内'''
attack = []
for i in range(n):
attack.append([0] * n)
# queen记录皇后位置
# 初始化queen所有元素为'.'
queen = []
for i in range(n):
queen.append(['.'] * n)
# 从棋盘的第0行第0列处理n皇后情况
backtrack(0, n, queen, attack)
# 返回结果
return res
