NQueens -递归BackTracking问题
NQueens -递归BackTracking问题
提问于 2020-11-14 03:17:42
我目前正在使用Python学习BackTracking算法，每个人通常首先要问的第一个问题就是NQueens。NQueens是你拿一个大小为N x N的棋盘的地方，你必须决定在哪里放置N个皇后，按照这样的顺序，它们不会受到任何其他皇后的攻击。
示例：
N=5
'Q'，0，0，0，0
0，0，'Q'，0，0
0，0，0，0，'Q‘
0，'Q'，0，0，0
0，0，0，'Q'，0
目前，我的算法返回所有可能的解决方案。我如何产生一个结果。例如，当N=8时，有92个最优结果，我如何只返回一个结果，而不是打印92个单独的结果。
#This is our main recursive function that will determine optimal outcome
def NQueens(row,Current,N):
#this tells us when to stop
if row == N:
print("\n")
return printBoard(Current)
for choice in range(0,N):
if isValid(row,choice,Current,N):
#Place Queen in appropriate spot
Current[row][choice] = "Q"
#Go to next row
NQueens(row+1,Current,N)
Current[row][choice] = 0
return "All Solutions Found"
#This function determines whether we can put a Queen in a certain orientation on the board
def isValid(row,col,Current,N):
#check whether current state of game has queen in row/column
for i in range(0,N):
#checks column/row and sees whether a queen exists already
if Current[row][i] == "Q" or Current[i][col] == "Q":
return False
# Check upper diagonal on right side
i = row-1
j = col + 1
#Do while row is greater than 0 and column is less than N
while i >= 0 and j < N:
if Current[i][j] == "Q":
return False
i -= 1
j += 1
# Check upper diagonal on left side
#Do while row is greater than 0 and column is greater than N
i = row-1
j = col - 1
while i >= 0 and j >= 0:
if Current[i][j] == "Q":
return False
i -= 1
j -= 1
#If we pass the diagonal/row/column tests, we can then determine this is a valid move
return True
###############################################################################################################
#These functions deal with board creation and printing them in a proper format
def generateBoard(N):
#generate board based on User Input N in Main()
Board = [[0 for i in range(0,N)] for j in range(0,N)]
return Board
def printBoard(arr):
#Loop through each row to print an organized board
for row in arr:
print(row)
def main():
#ask number from user
print("What sized board would you like?"
" Please input a number higher that 3: ")
#user input used to determine size of board
N = int(input())
#generate Board that will be used
Board = generateBoard(N)
#this is the current status of the board
printBoard(Board)
print("\n")
#Runs Algorithm
print(NQueens(0,Board,N))
if __name__ == "__main__":
main()回答 2
Stack Overflow用户
发布于 2020-11-14 03:31:02
NQueens需要通知它的调用者已经找到了解决方案；如果是这样，一个简单的return True就可以了。我对您的代码做了以下更改(前面的代码已注释)：
def NQueens(row,Current,N):
#this tells us when to stop
if row == N:
print("\n")
#return printBoard(Current)
return True # found a solution, say so
for choice in range(0,N):
if isValid(row,choice,Current,N):
#Place Queen in appropriate spot
Current[row][choice] = "Q"
#Go to next row
# NQueens(row+1,Current,N)
if NQueens(row+1,Current,N): # recursive call found a solution, let's stop
return True
Current[row][choice] = 0
#return "All Solutions Found" 在main()中
# ...
#Runs Algorithm
#print(NQueens(0,Board,N))
if NQueens(0,Board,N):
printBoard(Board) # found a solution, print itStack Overflow用户
发布于 2020-11-21 01:59:00
我已经修复了您的代码，使其具有良好的性能:我将此代码https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/和您的代码合并以获得它。
count = 1
def printOut(arrayMap):
global count
print('{}: -'.format(count))
count += 1
for i in range(0, len(arrayMap)):
print(arrayMap[i])
# This is our main recursive function that will determine optimal outcome
def NQueens(currentRow, arrayMap, matrixSize):
# this tells us when to stop
if currentRow == matrixSize:
print()
printOut(arrayMap)
return True # found a solution, say so
res = False
for col in range(0, matrixSize):
if isValid(currentRow, col, arrayMap, matrixSize):
# Place Queen in appropriate spot
arrayMap[currentRow][col] = 0
# Go to next row
# NQueens(row+1,Current,N)
res = NQueens(currentRow + 1, arrayMap, matrixSize) or res # recursive call found a solution, let's stop
arrayMap[currentRow][col] = 1
# return "All Solutions Found"
return res
# This function determines whether we can put a Queen in a certain orientation on the board
def isValid(row, col, arrayMap, matrixSize):
# check whether current state of game has queen in row/column
for i in range(0, matrixSize):
# checks column/row and sees whether a queen exists already
if arrayMap[row][i] == 0 or arrayMap[i][col] == 0:
return False
# Check upper diagonal on right side
i = row - 1
j = col + 1
# Do while row is greater than 0 and column is less than N
while i >= 0 and j < matrixSize:
if arrayMap[i][j] == 0:
return False
i -= 1
j += 1
# Check upper diagonal on left side
# Do while row is greater than 0 and column is greater than N
i = row - 1
j = col - 1
while i >= 0 and j >= 0:
if arrayMap[i][j] == 0:
return False
i -= 1
j -= 1
# If we pass the diagonal/row/column tests, we can then determine this is a valid move
return True
###############################################################################################################
if __name__ == "__main__":
# ask number from user
print("What sized board would you like?")
N = int(input('Choose your size: '))
# generate Board that will be used
Board = [[1 for i in range(0, N)] for j in range(0, N)]
count = 0
NQueens(0, Board, N)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/64826784
复制相关文章
相似问题
腾讯云开发者
