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

Question

我正在尝试解决 8 queen problem使用搜索算法，例如 iterative-deepening search或 A* search . 我已经给了一个棋盘，我应该找到最少的步数来得到一个没有皇后相互威胁的棋盘。 我不知道应该使用什么数据结构或包来将我的板存储在 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 数组

[edit] 表示所有状态:

您可以紧凑地使用 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