我刚刚解决了python中的nqueen问题。该解决方案输出在 nXn 棋盘上放置 n 个皇后的解决方案总数,但尝试使用 n=15 需要一个多小时才能得到答案。任何人都可以看一下代码并给我一些加速这个程序的技巧......一个新手Python程序员。
#!/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 开始。让我知道计算器内存不足的速度。
幸运的是,并非所有可能的解决方案都必须进行检查。不幸的是,正确解决方案的数量仍然遵循大致的阶乘增长模式。因此,算法的运行时间以阶乘速度增长。
由于您需要找到所有正确的解决方案,因此对于加快程序速度实际上无能为力。您已经很好地从搜索树中删除了不可能的分支。我不认为还有什么会产生重大影响。这只是一个缓慢的算法。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)