python - 棋盘上的 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)

Traceback (most recent call last):

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

MemoryError

我还是个新手，我该如何克服这个错误？或者有什么更好的方法来解决这个问题？

Answer 1

你想做的事是不可能的 ;)!

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

意味着您将获得一个长度为 64 的列表，选择 8 = 4426165368，因为 len(chessPositions) = 64，您无法将其存储在内存中。为什么不？结合我在评论中所说的和@augray 在他的回答中的内容，上述操作的结果将是一个列表，需要

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

RAM，因为它将有 64 choose 8 元素，每个元素将有 8 个子字符串，如 'A1'，每个子字符串由 2 个字符组成。一个字符占用 1 个字节。

你得另辟蹊径。我不会回答这个问题，因为那是你的工作。 n 皇后 问题属于动态规划。我建议你用谷歌搜索“n queens problem python”并搜索答案。然后尝试理解代码和动态规划。

---

我找你了，看看this video .正如@Jean François-Fabre 所建议的那样，回溯。你现在的工作是看一次视频，两次，...只要你不明白问题的解决方法。然后打开你最喜欢的编辑器(我的是 Vi :D)并把它写下来!