# 回溯法 n皇后 python 解法一

global N
N = 4

def printSolution(board):
for i in range(N):
for j in range(N):
print(board[i][j], end="")
print()
print()

def isSafe(board, row, col):
for i in range(col):
if board[row][i] == 1:
return False
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
for i, j in zip(range(row, N, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True

def solveNQUtil(board, col):
if col >= N:
printSolution(board)
else:
for i in range(N):
if isSafe(board, i, col):
board[i][col] = 1
solveNQUtil(board, col + 1)
board[i][col] = 0
return False

def solveNQ():
# 写成这样更具适应性
# board = [[0 for i in range(N)] for j in range(N)]
board = [[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]

if not solveNQUtil(board, 0):
print("Solution does not exist")
return False

printSolution(board)
return True

if __name__ == "__main__":
solveNQ()

# output
# 0010
# 1000
# 0001
# 0100

# 0100
# 0001
# 1000
# 0010

global N
N = 4

def printSolution(board):
for i in range(N):
for j in range(N):
print(board[i][j], end="")
print()
print()

def isSafe(board, row, col):
for i in range(col):
if board[row][i] == 1:
return False
# 检查对角线（左上角）是否有冲突
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
# 检查对角线（左下角）是否有冲突
for i, j in zip(range(row, N, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True

def solveNQUtil(board, col):
if col >= N:
# printSolution(board)
return True
for i in range(N):
if isSafe(board, i, col):
board[i][col] = 1
# 有变动的地方
if solveNQUtil(board, col + 1):
return True
board[i][col] = 0
return False

def solveNQ():
# board = [[0 for i in range(N)] for j in range(N)]
board = [[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]

if not solveNQUtil(board, 0):
print("Solution does not exist")
return False

printSolution(board)
return True

if __name__ == "__main__":
solveNQ()

# output
# 0010
# 1000
# 0001
# 0100
原文作者：回溯法
原文地址: https://blog.csdn.net/normol/article/details/78654822
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。