如果读者对于回溯算法思路解法还不是很了解，可以先点击链接查阅我之前的一篇博文《算法之【回溯算法】详解》，很详细的介绍了回溯算法求解思路及方法，有利于你更好的学习回溯算法。
题目描述
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
注：下图为 8 皇后问题的一种解法。
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
N皇后问题.png
示例1
输入：4 输出：
解法 1： [".Q..", "...Q", "Q...", "..Q."],解法 2：["..Q.", "Q...", "...Q", ".Q.."]
解释: 4 皇后问题存在两个不同的解法。
问题分析
直接套用《算法之【回溯算法】详解》中的回溯算法基本步骤以及回溯算法的通用框架模板。
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def backtrack(board, row):
if row >= n:
# 此处是将每一行转换为题目要求的字符串形式,如"..Q."代表一行
cur_res = [''.join(row) for row in board]
res.append(cur_res) #保存结果
return
for i in range(n):
if isValid(row, i, board): #isValid用于判断该位置是否合法，能够放置皇后
board[row][i] = 'Q' #放置皇后
backtrack(board, row+1) # row+1进入下一行
board[row][i] = '.' #回溯
res = []
board = [['.'] * n for _ in range(n)] # 初始化棋盘
backtrack(board, 0) # row从0开始
return res
1. 状态变量为行：row,每次在当前行选择完一个可以放置的皇后位置后进入下一行row+1;
2. 递归结束条件:当row>=n时，row从0开始，表示前n-1所有行的皇后均已放置完成，将结果添加到res中。
if row >= n:
# 此处是将每一行转换为题目要求的字符串形式,如"..Q."代表一行
cur_res = [''.join(row) for row in board]
res.append(cur_res)
return
3. 可选择的列表：每一行能够选择的位置为0到n-1，但是该位置是否能够被选择，需要满足皇后彼此不能相互攻击的条件。
此处判断是否能够相互攻击即判断当前位置(row, col)所在的列，右斜线方向即左斜线方向是否已经有皇后存在，如果有的话，则当前位置不能再放皇后。
判断是否有冲突的方式有两种：
方法一：直接通过循环判断
def isVaild(board,row, col):
#判断同一列是否冲突
for i in range(len(board)):
if board[i][col] == 'Q':
return False
# 判断左上角是否冲突
i = row -1
j = col -1
while i>=0 and j>=0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# 判断右斜线方向是否冲突
i = row - 1
j = col + 1
while i>=0 and j < len(board):
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
方法二: 左斜线:同一斜线每个点row-col恒定; 右斜线：同一斜线每个点row+col恒定
左斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0)和 (3,3)在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。
左斜.png
右斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 (3,0)(3,0) 和 (1,2)(1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。
右斜.png
下面我们主要使用第二种方法来进行判断所放置的位置是否合法。
def isValid(row, col):
# 判断所放置的位置是否合法
for i in range(row):
for j in range(n):
# 注：左斜对角线上，同一条斜线上的每个位置满足行下标与列下标之差相等
# 注：右斜对角线上，同一条斜线上的每个位置满足行下标与列下标之和相等
if board[i][j] == 'Q' and (j == col or i + j == row + col or i-j == row-col):
return False
return True
最终代码
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def isValid(row, col):
# 判断所放置的位置是否合法
for i in range(row):
for j in range(n):
if board[i][j] == 'Q' and (j == col or i + j == row + col or i-j == row-col):
return False
return True
def backtrack(board, row):
if row >= n:
cur_res = [''.join(row) for row in board]
res.append(cur_res)
return
for i in range(n):
if isValid(row, i, board):
board[row][i] = 'Q'
backtrack(board, row+1)
board[row][i] = '.'
res = []
board = [['.'] * n for _ in range(n)]
backtrack(board,0)
return res
代码优化：通过集合记录之前放置过元素的正向对角线，负向对角线，及列，判断当前点是否在集合中，在的话说明不满足要求，这种判断方式速度更快。
def solveNQueens(self, n: int) -> List[List[str]]:
def isValid(row, col):
# 如果该点所对应的右斜线或左斜线或列已经放置了皇后则放回Fasle
if col in col_hash or (row + col) in pie_hash or (row-col) in na_hash:
return False
return True
def backtrack(board, row):
if row >= n:
cur_res = [''.join(row) for row in board]
res.append(cur_res)
return
for col in range(n):
if isValid(row, col, board):
board[row][col] = 'Q'
pie_hash.add(row + col)
na_hash.add(row - col)
col_hash.add(col)
backtrack(board, row+1)
board[row][col] = '.'
pie_hash.remove(row + col)
na_hash.remove(row-col)
col_hash.remove(col)
res = []
board = [['.'] * n for _ in range(n)]
pie_hash = set() # 记录放置了皇后的右斜线
na_hash = set() # 记录放置了皇后的左斜线
col_hash = set() # 记录放置了皇后的列
backtrack(board,0)
return res
后续会继续更新关于回溯算法的相关题解，欢迎持续关注！
如果喜欢作者，欢迎点赞、收藏及关注，谢谢！
网友评论