棋盘上的 8 个皇后 | PYTHON |内存错误

Question

我遇到了这个问题，应该将 8 个皇后放在棋盘上，这样 none 可以杀死每个皇后 other.This 我就是这样解决的：

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

我还是newbie.How我可以克服这个错误吗？或者有什么更好的方法可以解决这个问题吗？

Answer 1

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

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

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

你得另辟蹊径。我不会回答这个问题，因为那是你的工作。 n-queens问题属于动态规划。我建议您 google 'n queens problem python' 并搜索答案。然后尝试看懂代码和动态规划

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

Answer 2

在这种情况下，了解计算机科学的 "science"（或更准确地说，数学）部分与了解编程的具体细节一样重要。

从 documentation for 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 得到这些子序列所占内存的 Gig 数，大约 66GB。

我假设您没有那么多内存:-)。计算这个问题的答案需要经过深思熟虑的算法，而不仅仅是 "brute force"。我建议对该问题进行一些研究 - Wikipedia 看起来是个不错的起点。

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 并一次只输入一个检查函数。

棋盘上的 8 个皇后 | PYTHON |内存错误

8 Queens on a chessboard | PYTHON | Memory Error

python

chess