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 |內存錯誤

回答

相關問題