在棋盘上放置8个皇后 | PYTHON | 内存错误

Question

我遇到了这样一个问题，需要在棋盘上放置8个皇后，使得它们互相不能攻击。以下是我的解决方法：

import itertools
def allAlive(position):
    qPosition=[]
    for i in range(8):
        qPosition.append(position[2*i:(2*i)+2])
    hDel=list(qPosition)     #Horizontal
    for i in range(8): 
        a=hDel[0]
        del hDel[0]
        l=len(hDel)
        for j in range(l):
            if a[:1]==hDel[j][:1]:
                return False
    vDel=list(qPosition)     #Vertical
    for i in range(8):
        a=vDel[0]
        l=len(vDel)
        for j in range(l):
            if a[1:2]==vDel[j][1:2]:
                return False
    cDel=list(qPosition)     #Cross
    for i in range(8):
        a=cDel[0]
        l=len(cDel)
        for j in range(l):
            if abs(ord(a[:1])-ord(cDel[j][:1]))==1 and abs(int(a[1:2])-int(cDel[j][1:2]))==1:
                return False
    return True
chessPositions=['A1','A2','A3','A4','A5','A6','A7','A8','B1','B2','B3','B4','B5','B6','B7','B8','C1','C2','C3','C4','C5','C6','C7','C8','D1','D2','D3','D4','D5','D6','D7','D8','E1','E2','E3','E4','E5','E6','E7','E8','F1','F2','F3','F4','F5','F6','F7','F8','G1','G2','G3','G4','G5','G6','G7','G8','H1','H2','H3','H4','H5','H6','H7','H8']
qPositions=[''.join(p) for p in itertools.combinations(chessPositions,8)]
for i in qPositions:
    if allAlive(i)==True:
        print(i)

错误回溯（最近调用）：

qPositions=[''.join(p) for p in itertools.combinations(chessPositions,8)]

内存错误

我还是个新手。我该如何解决这个错误？或者是否有更好的解决方法？

- Novice

Answer 1

这是一个案例，需要理解计算机科学中“科学”（更准确地说是数学）部分的重要性，与理解编程的基础知识同样重要。从 itertools.combinations 的文档 中，我们可以看到返回的项目数量为 n! / r! / (n-r)!，其中n是输入集合的长度（在您的情况下是棋盘位置的数量，即64），r是要返回的子序列的长度（在您的情况下是8）。正如@campovski所指出的那样，这将导致4,426,165,368个结果。每个返回的子序列将由8 * 2个字符组成，每个字符是一个字节（更不用说其他数据结构的开销来保存这些并计算答案了）。每个字符占用1个字节，因此仅计算结果子序列的内存消耗就会产生4,426,165,368*2*8=70818645888。将其除以1024 ^ 3可得到这些子序列保存的内存量，约为66GB。

我假设你没有那么多内存:-)。计算这个问题的答案需要一个深思熟虑的算法，而不仅仅是"暴力破解"。我建议对这个问题进行一些研究- 维基百科 看起来是一个很好的开始。

- augray

---

我知道我不应该评论这个，但是@augray的回答非常好。当有人展示他们用来得出结论和解释错误的逻辑和数学时，我总是很喜欢。+1 - Christian Dean

Answer 2

你想做的事情是不可能的 ;)！

qPositions=[''.join(p) for p in itertools.combinations(chessPositions,8)]

这意味着您将获得一个长度为64 choose 8 = 4426165368的列表，因为len(chessPositions) = 64，这是无法在内存中存储的。为什么呢？结合我在评论中提到的和@augray在他的回答中提到的内容，上述操作的结果将是一个列表，它将占用

(64 choose 8) * 2 * 8 bytes ~ 66GB

由于它将有64个选择8个元素，每个元素将有8个子字符串，如'A1'，并且像这样的每个子字符串由2个字符组成。一个字符占用1字节的内存。

你必须找到另一种方法。我不回答那个问题，因为那是你的工作。 n皇后问题属于动态规划范畴。建议你使用谷歌搜索'n queens problem python'，查找答案。然后尝试理解代码和动态规划。

---

我已经替你搜过了，看看这个视频。正如@Jean François-Fabre所建议的那样，采用回溯法。你现在的任务是观看视频一次、两次... 直到你理解问题的解决方案。然后打开你最喜欢的编辑器（我的是Vi :D）并把它编码下来！

- campovski

---

可以通过尝试和回溯直到找到有效的解决方案来解决它（暗示递归）。 - Jean-François Fabre

每个像“A1”这样的字符串大小为2个字节。 2 * 4426165368> 8Gb。除非一个人有超过10GB的RAM或以某种奇特的方式不使用某些交换，否则他无法计算该数组。由于他说他是Python新手，我认为他不能做任何上述描述的事情。当然，通过进行一些疯狂的编程操作可以完成它，但我怀疑他的课程是否涉及此类内容;) - campovski

10GB的RAM和大量的CPU计算能力。10GB的RAM在企业服务器上很常见，但填充数组的时间太长了。 - Jean-François Fabre

确实。虽然我不认为他在企业服务器上做作业 ;) - campovski

简而言之：解决方案的开始：放一个皇后，然后尝试把下一个放在下一列，以便它们不互相攻击。继续（通过递归调用）直到无法放置皇后或成功为止。你需要一个好的“can_take_each_other”函数。 - Jean-François Fabre

Answer 3

正如其他答案所述，您无法将每个组合都放入内存中，也不应使用蛮力算法，因为速度会很慢。但是，如果您想使用蛮力算法，可以限制问题，并消除常见的行和列并检查对角线。

from itertools import permutations
#All possible letters
letters = ['a','b','c','d','e','f','g','h']

#All possible numbers
numbers = [str(i) for i in range(1,len(letters)+1)]

#All possible permutations given rows != to eachother and columns != to eachother
r = [zip(letters, p) for p in permutations(numbers,8)]

#Formatted for your function
points = [''.join([''.join(z) for z in b]) for b in r]

---

作为一条提示，这行代码试图先找到所有组合，然后将其传递给您的函数，这是浪费内存的。

qPositions=[''.join(p) for p in itertools.combinations(chessPositions,8)]

如果您决定使用暴力方法，那么是可能的。只需修改itertools combinations的代码。删除yield和return，然后逐个输入到您的检查函数中即可。

- DJK