8皇后棋盘| PYTHON |内存错误

我碰到这个问题，其中8个皇后应该放在一个棋盘，使得没有人能杀死每个other.This来到我就是试图解决这个问题：8皇后棋盘| PYTHON |内存错误

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 = [ '' 加入（p）对于p在itertools.combinations（chessPositions，8）]

的MemoryError

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

来源

2017-09-04 Novice

你试图做的是不可能的;）！

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

的RAM

，因为这将有64 choose 8元素的列表，每个元素将有8子像'A1'，每个这样的子字符串由2个字符组成。一个字符需要1个字节。

你必须找到另一种方式。我不回答这个问题，因为那是你的工作。 n皇后问题属于动态编程。我建议你谷歌'皇后问题python'并寻找答案。然后尝试了解代码和动态编程。

我找过你了，看看this video。正如@JeanFrançois-Fabre所示，回溯。现在您的工作是观看视频一次，两次，只要您不了解问题的解决方案。然后打开你最喜欢的编辑器（我的是Vi：D）并将其编码！

来源

2017-09-04 17:07:47 campovski

它可以通过尝试和_backtracking_解决，直到找到一个有效的解决方案（暗示递归） –

每个字符串像“”A1“'是2个字节的大小。 2 * 4426165368> 8Gb。除非一个人拥有更多的10GB内存，或者不以某种特殊的方式使用某种交换方式，否则他无法计算该阵列。既然他说他是Python的新手，我认为他不能做任何上述的描述。当然，这可以通过做一些生病的编程的东西来完成，但我怀疑他的课程是关于这个的;） – campovski

10GB或RAM以及大量的CPU功率。 10GB的ram在企业服务器上很常见，但填满阵列的时间太多了。 –

这是一个理解计算机科学的“科学”（或更准确地说，数学）部分很重要的案例，尽管理解编程的细节和螺栓非常重要。

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

我假设你没有那么多的记忆:-)。计算这个问题的答案需要经过深思熟虑的算法，而不仅仅是“蛮力”。我建议对这个问题做一些研究 - Wikipedia看起来是一个很好的开始。

来源

2017-09-04 17:17:42 augray

我知道我不应该对此评论，但非常好的答案@augray。当有人展示他们使用的逻辑和数学来得出结论并解释错误时，我总是喜欢它。 +1 –

正如其他答案所说，你不能让每个组合都适合内存，并且你不应该使用蛮力，因为速度会很慢。但是，如果你想用蛮力，你能限制的问题，消除常见的行和列，并检查对角线

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，并一次只提供一个检查功能。

来源

2017-09-04 19:44:37 DJK

8皇后棋盘| PYTHON |内存错误

回答

相关问题