解决n-queen拼图

Question

我刚刚解决了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() 

Answer 1

对于N-Queens问题的回溯算法是最坏情况下的因子算法.因此对于N = 8,8!在最坏的情况下检查解决方案的数量,N = 9使其成为9!等等.可以看出,可能的解决方案的数量变得非常大,非常快.如果您不相信我,只需转到计算器并开始乘以连续数字,从1开始.让我知道计算器耗尽内存的速度.

幸运的是,并非所有可能的解决方案都必须进 不幸的是,正确解决方案的数量仍然遵循大致因子增长模式.因此,算法的运行时间以阶乘的速度增长.

由于您需要找到所有正确的解决方案,因此加快程序的速度并不多.你已经在从搜索树中修剪不可能的分支方面做得很好.我不认为还有其他任何会产生重大影响的事情.这只是一个缓慢的算法.