在python中存储8皇后问题板的最好方法是什么

Question

我正在尝试使用iterative-deepening search或A* search等搜索算法来解决8 queen problem问题。我已经给出了一个棋盘，我应该找到最少的移动次数来得到一个不会互相威胁的棋盘。我不知道我应该使用什么数据结构或包来在python中存储我的板子。

我要打印并保存访问过的板，我认为我应该使用最好的数据结构来优化时间和空间。

我开始使用pandas.DataFrame，因为我的数据是以csv格式提供的。然后我注意到我应该检查相同的电路板，我切换到numpy.array()以便于比较电路板。另一种方法是使用简单的python元组列表：

[(q1_x, q1_y), (q2_x, q2_y), ....(q8_x, q8_y)]

但我不知道哪一个是最好的解决方案。

谢谢你的帮助。

Answer 1

要表示合法状态，请执行以下操作：

在棋盘上存储皇后位置的一种快速而紧凑的方法是一个简单的数组(或列表)，其中索引表示列号，值表示皇后所在的行号。如果列中没有女王，您可能想要使用-1来标记：

例如：queens = [0, 1, 2, 3, 4, 5, 6, 7]表示以下配置：

  0 1 2 3 4 5 6 7
0 Q
1   Q
2     Q
3       Q
4         Q
5           Q
6             Q
7               Q

同样，您也可以使用8位整数的numpy数组

编辑以表示所有状态：

您可以在0和255之间紧凑地使用一个由8个二进制数组成的数组，其中1表示女王的列位置：

import random

class Queens:
    def __init__(self):
        self.config = [bin(random.randrange(0, 256))[2:].zfill(8) for _ in range(8)]
        
    def __repr__(self):
        return'\n'.join(self.config)
    
    def __str__(self):
        result = ['  ' + ' '.join(str(idx) for idx in range(8))]
        for rdx, elt in enumerate(self.config):
            a = elt.replace('1', 'Q ')
            a = a.replace('0', '  ')
            a = str(rdx) + ' ' + a
            result.append(a)
        return'\n'.join(result)
                
q = Queens()
print(repr(q), end='\n\n')
print(q)

输出：

01010001
10000010
01000010
10100001
01011110
10001110
01010110
11000000

  0 1 2 3 4 5 6 7
0   Q   Q       Q 
1 Q           Q   
2   Q         Q   
3 Q   Q         Q 
4   Q   Q Q Q Q   
5 Q       Q Q Q   
6   Q   Q   Q Q   
7 Q Q             

Answer 2

另一种选择是Numba：http://numba.pydata.org/。它允许编写朴素的for循环，这在纯python中很慢，但仍然可以获得良好的性能。