目录
51.题目
-
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
题解：回溯
from typing import List
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = [] # 存储最终的解
board = [['.' for _ in range(n)] for _ in range(n)] # 初始化棋盘
self.backtrack(board, 0, n, res) # 进行回溯搜索
return res
def backtrack(self, board: List[List[str]], row: int, n: int, res: List[List[str]]):
if row == n: # 如果当前行等于 n，说明已经找到一个合法解
res.append([''.join(row) for row in board]) # 将当前棋盘状态加入结果列表
return
for col in range(n): # 遍历当前行的所有列
if self.is_valid(board, row, col, n): # 判断当前位置是否合法
board[row][col] = 'Q' # 放置一个皇后
self.backtrack(board, row + 1, n, res) # 递归处理下一行
board[row][col] = '.' # 撤销选择，恢复为空位
def is_valid(self, board: List[List[str]], row: int, col: int, n: int) -> bool:
for i in range(row): # 检查当前位置上方的所有行
if board[i][col] == 'Q': # 如果存在皇后在同一列上
return False
for i, j in zip(range(row-1, -1, -1), range(col+1, n)): # 检查当前位置的右上方对角线
if board[i][j] == 'Q': # 如果存在皇后
return False
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)): # 检查当前位置的左上方对角线
if board[i][j] == 'Q': # 如果存在皇后
return False
return True # 当前位置合法，返回 True
52题目
- 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
题解：回溯
from typing import List
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = [] # 存储最终的解
board = [['.' for _ in range(n)] for _ in range(n)] # 初始化棋盘
self.backtrack(board, 0, n, res) # 进行回溯搜索
return len(res)#返回结果列表长度
def backtrack(self, board: List[List[str]], row: int, n: int, res: List[List[str]]):
if row == n: # 如果当前行等于 n，说明已经找到一个合法解
res.append([''.join(row) for row in board]) # 将当前棋盘状态加入结果列表
return
for col in range(n): # 遍历当前行的所有列
if self.is_valid(board, row, col, n): # 判断当前位置是否合法
board[row][col] = 'Q' # 放置一个皇后
self.backtrack(board, row + 1, n, res) # 递归处理下一行
board[row][col] = '.' # 撤销选择，恢复为空位
def is_valid(self, board: List[List[str]], row: int, col: int, n: int) -> bool:
for i in range(row): # 检查当前位置上方的所有行
if board[i][col] == 'Q': # 如果存在皇后在同一列上
return False
for i, j in zip(range(row-1, -1, -1), range(col+1, n)): # 检查当前位置的右上方对角线
if board[i][j] == 'Q': # 如果存在皇后
return False
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)): # 检查当前位置的左上方对角线
if board[i][j] == 'Q': # 如果存在皇后
return False
return True # 当前位置合法，返回 True
优化
- res不用保存每一个可行解，只进行计数
class Solution:
def totalNQueens(self, n: int) -> int:
self.res = 0 # 解决方案数
board = [['.' for _ in range(n)] for _ in range(n)] # 初始化棋盘
self.backtrack(board, 0, n) # 进行回溯搜索
return self.res #返回解决方案数
def backtrack(self, board: List[List[str]], row: int, n: int):
if row == n: # 如果当前行等于 n，说明已经找到一个合法解
self.res+=1 # 解决方案数加1
return
for col in range(n): # 遍历当前行的所有列
if self.is_valid(board, row, col, n): # 判断当前位置是否合法
board[row][col] = 'Q' # 放置一个皇后
self.backtrack(board, row + 1, n) # 递归处理下一行
board[row][col] = '.' # 撤销选择，恢复为空位
def is_valid(self, board: List[List[str]], row: int, col: int, n: int) -> bool:
for i in range(row): # 检查当前位置上方的所有行
if board[i][col] == 'Q': # 如果存在皇后在同一列上
return False
for i, j in zip(range(row-1, -1, -1), range(col+1, n)): # 检查当前位置的右上方对角线
if board[i][j] == 'Q': # 如果存在皇后
return False
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)): # 检查当前位置的左上方对角线
if board[i][j] == 'Q': # 如果存在皇后
return False
return True # 当前位置合法，返回 True