设计一种算法,打印 N 皇后在 NxN 棋盘上的各种摆法,其中每个皇后都不同行、不同列,也不在对角线上。这里的"对角线"指的是所有的对角线,不只是平分整个棋盘的那两条对 线。 注意:本题相对原题做了扩展示例: 输入:4 输出:[[". Q ..","... Q "," Q ...",".. Q ."],[".. Q ."," Q ...","... Q ",". Q .."]] 解释:4皇后问题存在如下两个不同的解法。 [". Q ..",//解法1"... Q ", " Q ...", ".. Q ."], [".. Q .",//c++编写
时间: 2023-06-03 22:05:40 浏览: 86
C++算法设计 N皇后问题.txt
以下是算法实现的 Python 代码:
def is_valid(board, row, col, n):
# 检查同一列上是否有皇后
for i in range(row):
if board[i][col] == "Q":
return False
# 检查左上方是否有皇后
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == "Q":
return False
i, j = i - 1, j - 1
# 检查右上方是否有皇后
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == "Q":
return False
i, j = i - 1, j + 1
return True
def backtrack(board, row, n, solutions):
# 找到一个合法解
if row == n:
solutions.append(["".join(row) for row in board])
return
# 枚举皇后放置的列
for col in range(n):
if is_valid(board, row, col, n):
board[row][col] = "Q"
backtrack(board, row + 1, n, solutions)
board[row][col] = "."
def solve_n_queens(n):
board = [["." for _ in range(n)] for _ in range(n)]
solutions = []
backtrack(board, 0, n, solutions)
return solutions
# 测试代码
print(solve_n_queens(4)) # 输出 [['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]
阅读全文