解决 n 皇后难题

发布于 2024-10-15 00:40:39 字数 3182 浏览 3 评论 0原文

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

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() 

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(6

你是暖光i 2024-10-22 00:40:40

解决方案的数量可以使用 Donald Knuth 的随机估计方法来估计。

从没有放置皇后开始,下一行允许的位置数为 n。
随机选择一个位置并计算下一行允许的位置数 (p) 并将其乘以 n 并将其存储为解总数 (total = n * p) ,然后随机选择一个允许的位置。

对于这一行,计算下一行允许的位置数 (p),并将解决方案总数乘以该数 (total *= p)。重复此操作,直到棋盘无法解决(在这种情况下,解决方案的数量为零),或者直到棋盘被解决为止。

重复此操作多次并计算解的平均数量(包括任何零)。这将为您提供快速且相当准确的解数近似值,并且运行次数越多,近似值就会越高。

我希望这是有道理的;)

The number of solutions can be estimated using Donald Knuth's randomised estimation method.

Starting from no queens placed the number of allowed positions for the next row is n.
Randomly pick one of the positions and calculate the number of allowed positions (p) for the next row and multiple this by n and store it as the total number of solutions (total = n * p) , then randomly choose one of the allowed positions.

For this row calculate the number of allowed positions (p) for the next row and mutiple the total number of solutions by this (total *= p). Repeat this until either the board cannot be solved, in which case the number of solutions equals zero, or until the board is solved.

Repeat this many times and calculate the average number of solutions (including any zeros). This should give you a quick and pretty accurate approximation of the number of solutions with the approximation improving the more runs you do.

I hope this makes sense ;)

黎歌 2024-10-22 00:40:40

我建议您查看 test_generators.py 来自 Python 源代码,用于 N 皇后问题的替代实现。

Python 2.6.5 (release26-maint, Sep 12 2010, 21:32:47) 
[GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from test import test_generators as tg
>>> n= tg.Queens(15)
>>> s= n.solve()
>>> next(s)
[0, 2, 4, 1, 9, 11, 13, 3, 12, 8, 5, 14, 6, 10, 7]
>>> next(s)
[0, 2, 4, 6, 8, 13, 11, 1, 14, 7, 5, 3, 9, 12, 10]

I would suggest you peek at the test_generators.py from the Python source for an alternative implementation of the N-Queens problem.

Python 2.6.5 (release26-maint, Sep 12 2010, 21:32:47) 
[GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from test import test_generators as tg
>>> n= tg.Queens(15)
>>> s= n.solve()
>>> next(s)
[0, 2, 4, 1, 9, 11, 13, 3, 12, 8, 5, 14, 6, 10, 7]
>>> next(s)
[0, 2, 4, 6, 8, 13, 11, 1, 14, 7, 5, 3, 9, 12, 10]
零時差 2024-10-22 00:40:40

刚看到这个问题。我想贡献 2 个解决方案。

  1. 此返回所有不同的解决方案

  2. 此返回找到的第一个有效解决方案

感谢反馈。干杯

Just saw this question. I'd like to contribute 2 solutions.

  1. This one returns all distinct solutions

  2. This one returns the first valid solution found

Feedback is appreciated. Cheers

梦里寻她 2024-10-22 00:40:40

下面是我的 PYTHON 实现。您可能想使用 PYPY 来提高速度。

通过使用 O(1) 时间方法来检查下一个皇后是否受到已经放置在棋盘上的皇后的攻击,可以提高其速度。

假设程序是“nqueen.py”,运行它的示例是“python nqueen.py 6”,其中6是6x6板的大小。

#!/bin/python
#
# TH @stackoverflow, 2016-01-20, "N Queens" with an O(1) time method to check whether the next queen is attacked
#
import sys


board_size = int(sys.argv[1])
Attacked_H  = { i:0 for i in range(0, board_size) }
Attacked_DU = { i:0 for i in range(0, board_size*2) }
Attacked_DD = { i:0 for i in range(-board_size, board_size) }


def nqueen(B, N, row, col):
    if(row >= N):
        return 1
    if(col >= N):
        print "board:\n" + str.join("\n", ["_|"*q + "Q|" + "_|"*(board_size - q - 1) for q in B])
        return 0
    B[col] = row
    if(0==(Attacked_H[row] + Attacked_DU[row+col] + Attacked_DD[row-col])):
        [Attacked_H[row], Attacked_DU[row+col], Attacked_DD[row-col]] = [ 1,1,1 ]
        nqueen(B, N, 0, col + 1)
        [Attacked_H[row], Attacked_DU[row+col], Attacked_DD[row-col]] = [ 0,0,0 ]
    nqueen(B, N, row + 1, col)


nqueen(list(range(0, board_size)), board_size, 0, 0)

Below is my PYTHON implementation. You might want to use PYPY for more speed.

Its speed is helped by using an O(1) time method to check whether the next queen is attacked by those already placed on the board.

Assuming the program is "nqueen.py", an example to run it is "python nqueen.py 6", where 6 is the size of a 6x6 board.

#!/bin/python
#
# TH @stackoverflow, 2016-01-20, "N Queens" with an O(1) time method to check whether the next queen is attacked
#
import sys


board_size = int(sys.argv[1])
Attacked_H  = { i:0 for i in range(0, board_size) }
Attacked_DU = { i:0 for i in range(0, board_size*2) }
Attacked_DD = { i:0 for i in range(-board_size, board_size) }


def nqueen(B, N, row, col):
    if(row >= N):
        return 1
    if(col >= N):
        print "board:\n" + str.join("\n", ["_|"*q + "Q|" + "_|"*(board_size - q - 1) for q in B])
        return 0
    B[col] = row
    if(0==(Attacked_H[row] + Attacked_DU[row+col] + Attacked_DD[row-col])):
        [Attacked_H[row], Attacked_DU[row+col], Attacked_DD[row-col]] = [ 1,1,1 ]
        nqueen(B, N, 0, col + 1)
        [Attacked_H[row], Attacked_DU[row+col], Attacked_DD[row-col]] = [ 0,0,0 ]
    nqueen(B, N, row + 1, col)


nqueen(list(range(0, board_size)), board_size, 0, 0)
悲念泪 2024-10-22 00:40:40

我们也可以用遗传算法来解决 n 皇后问题。这在 edX 课程 ColumbiaX 的一场讲座中https://youtu.be/l6qll5OldHQ对此进行了描述:CSMM.101x 人工智能 (AI)。

目标函数试图优化非攻击皇后对的数量。
下面的动画显示了 R 中 n=20 的解决方案示例。有关如何使用遗传算法解决 n 皇后问题的更多详细信息,请参阅:https://sandipanweb.wordpress.com/2017/03/09/solving-the-n-queen-puzzle-with-遗传算法in-r/?frame-nonce=76cf9b156a

输入图像此处描述

We can solve n-queens with genetic algorithms too. This is described here https://youtu.be/l6qll5OldHQ, in one of the lectures of the edX course ColumbiaX: CSMM.101x Artificial Intelligence (AI).

The objective function tries to optimize number of non-attacking pairs of queens.
The animation below shows an example solution in R with n=20. Further details on how to solve n-queens with genetic algorithms can be found here: https://sandipanweb.wordpress.com/2017/03/09/solving-the-n-queen-puzzle-with-genetic-algorithm-in-r/?frame-nonce=76cf9b156a.

enter image description here

羁绊已千年 2024-10-22 00:40:39

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.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文