两种八皇后问题python源代码

以下是两种八皇后问题的Python源代码：

# 第一种方法：
def printSolution(board):
for i in range(8):
for j in range(8):
print (board[i][j], end = " ")
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, 8, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False

return True

def solveNQUtil(board, col):
if col >= 8:
return True

for i in range(8):
if isSafe(board, i, col):
board[i][col] = 1
if solveNQUtil(board, col+1) == True:
return True
board[i][col] = 0

return False

def solveNQ():
board = [ [0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0] ]

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

printSolution(board)
return True

solveNQ()

# 第二种方法：
import random

def conflict(state, nextX):
nextY = len(state)
for i in range(nextY):
if abs(state[i] - nextX) in (0, nextY - i):
return True
return False

def queens(num, state=()):
for pos in range(num):
if not conflict(state, pos):
if len(state) == num - 1:
yield (pos,)
else:
for result in queens(num, state + (pos,)):
yield (pos,) + result

def print_board(solution):
def line(pos, length=len(solution)):
return '. ' * (pos) + 'X ' + '. ' * (length-pos-1)
for pos in solution:
print(line(pos))

if __name__ == "__main__":
solutions = list(queens(8))
print("The total number of solutions is: " + str(len(solutions)))
print("\nSolution example:")
print_board(random.choice(solutions))