解决n皇后难题 [英] Solving the n-queen puzzle
问题描述
我刚刚解决了python中的nqueen问题.该解决方案输出了将n个皇后放在nXn棋盘上的解决方案总数，但是在n = 15的情况下进行尝试需要一个多小时才能得到答案.任何人都可以看一下代码，并给我一些加快该程序的技巧吗……python新手.
I have just solved the nqueen problem in python. The solution outputs the total number of solutions for placing n queens on an nXn chessboard but trying it with n=15 takes more than an hour to get an answer. Can anyone take a look at the code and give me tips on speeding up this program...... A novice python programmer.
#!/usr/bin/env python2.7
##############################################################################
# a script to solve the n queen problem in which n queens are to be placed on
# an nxn chess board in a way that none of the n queens is in check by any other
#queen using backtracking'''
##############################################################################
import sys
import time
import array
solution_count = 0
def queen(current_row, num_row, solution_list):
if current_row == num_row:
global solution_count
solution_count = solution_count + 1
else:
current_row += 1
next_moves = gen_nextpos(current_row, solution_list, num_row + 1)
if next_moves:
for move in next_moves:
'''make a move on first legal move of next moves'''
solution_list[current_row] = move
queen(current_row, num_row, solution_list)
'''undo move made'''
solution_list[current_row] = 0
else:
return None
def gen_nextpos(a_row, solution_list, arr_size):
'''function that takes a chess row number, a list of partially completed
placements and the number of rows of the chessboard. It returns a list of
columns in the row which are not under attack from any previously placed
queen.
'''
cand_moves = []
'''check for each column of a_row which is not in check from a previously
placed queen'''
for column in range(1, arr_size):
under_attack = False
for row in range(1, a_row):
'''
solution_list holds the column index for each row of which a
queen has been placed and using the fact that the slope of
diagonals to which a previously placed queen can get to is 1 and
that the vertical positions to which a queen can get to have same
column index, a position is checked for any threating queen
'''
if (abs(a_row - row) == abs(column - solution_list[row])
or solution_list[row] == column):
under_attack = True
break
if not under_attack:
cand_moves.append(column)
return cand_moves
def main():
'''
main is the application which sets up the program for running. It takes an
integer input,N, from the user representing the size of the chessboard and
passes as input,0, N representing the chess board size and a solution list to
hold solutions as they are created.It outputs the number of ways N queens
can be placed on a board of size NxN.
'''
#board_size = [int(x) for x in sys.stdin.readline().split()]
board_size = [15]
board_size = board_size[0]
solution_list = array.array('i', [0]* (board_size + 1))
#solution_list = [0]* (board_size + 1)
queen(0, board_size, solution_list)
print(solution_count)
if __name__ == '__main__':
start_time = time.time()
main()
print(time.time()
推荐答案
在最坏的情况下，N皇后问题的回溯算法是阶乘算法.所以对于N = 8，8！在最坏的情况下，将检查解决方案的数量，N = 9使其变为9 !，以此类推.可以看出，可能的解决方案的数量非常大，非常快地增长.如果您不相信我，只需进入计算器并开始乘以从1开始的连续数字.让我知道计算器用尽内存的速度.
The backtracking algorithm to the N-Queens problem is a factorial algorithm in the worst case. So for N=8, 8! number of solutions are checked in the worst case, N=9 makes it 9!, etc. As can be seen, the number of possible solutions grows very large, very fast. If you don't believe me, just go to a calculator and start multiplying consecutive numbers, starting at 1. Let me know how fast the calculator runs out of memory.
幸运的是，并非必须检查所有可能的解决方案.不幸的是，正确解决方案的数量仍遵循大致的阶乘增长模式.因此，该算法的运行时间以阶乘的速度增长.
Fortunately, not every possible solution must be checked. Unfortunately, the number of correct solutions still follows a roughly factorial growth pattern. Thus the running time of the algorithm grows at a factorial pace.
由于您需要找到所有正确的解决方案，因此加快程序的速度实际上并没有太多的事情要做.您已经在修剪搜索树中不可能的分支方面做得很好.我认为没有任何其他因素会产生重大影响.这只是一个缓慢的算法.
Since you need to find all correct solutions, there's really not much that can be done about speeding up the program. You've already done a good job in pruning impossible branches from the search tree. I don't think there's anything else that will have a major effect. It's simply a slow algorithm.
这篇关于解决n皇后难题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
