當在erlang中生成幻方時需要太多的內存消耗 - 需要優化的幫助

Question

對於大學我必須實現一種算法，該算法爲給定的邊長和特定的總和創建所有可能的幻方。對於n = 3，算法按預期工作。但是，當一段時間後，當n = 4產生所有的幻方時，我的內存耗盡。這個問題已經在任務描述中提到。我已經嘗試過優化代碼，但它仍然不能正常工作。所以我希望有人能給我一些建議。

我的基本想法是：首先，我生成所有可能的行，我可以使用給定的數字，然後我試圖結合這些方法，以滿足魔術方塊的限制。這發生在回溯。我認爲問題是功能makeRows在存儲所有行之後消耗太多內存。

如果您需要更多我可以給出的代碼的解釋！

magicSquare(N, Value) -> 
    Squares = buildSquare(N, makeRows(N, N*N, Value, N)), 
    io:fwrite("Squares ready"), io:fwrite("~n"), 
    Result = lists:filter(fun(X) -> testsquare(X, N, Value) end, Squares), 
    io:write(length(Result)), 
    Result. 

buildSquare(0, _) -> [[]]; 
buildSquare(Rows, AvailableRows) -> 
    [ [X|L] || L <- buildSquare(Rows-1, AvailableRows), X <- AvailableRows, onlyUniqueNumbers(lists:flatten([X|L]))]. 

onlyUniqueNumbers(List) -> erlang:length(List) == sets:size(sets:from_list(List)). 

%produces all possible rows with a dimension of Fields and the Numbers from 1 to Numbers and the right sum for each row 
makeRows(0,_,_,_) -> [[]]; 
makeRows(Fields, Numbers, Value, TargetLength) -> 
    [ [X|L] || X <- makeRows(Fields-1, Numbers, Value, TargetLength), L <- lists:seq(1,Numbers), checkRow([X|L], TargetLength, Value)]. 

checkRow(Row, Length, Value) when length(Row) < Length -> true; 
checkRow(Row, Length, Value) -> 
    Sum = lists:sum(Row), 
    if Sum == Value -> true; 
    true -> false 
    end. 

testsquare(Square, N, Value) -> checkAllDiagonal(Square, Value) andalso checkAllHorizontal(Square, Value) andalso checkAllVertical(Square, N, Value). 

checkAllHorizontal([H|T], Value) -> 
    case checkHorizontal(H, Value, 0) of 
     true -> checkHorizontal(lists:nth(1, T), Value, 0); 
     false -> false 
    end; 
checkAllHorizontal([], Value) -> true. 

checkHorizontal([H|T], Value, Summe) -> checkHorizontal(T, Value, Summe + H); 
checkHorizontal([], Value, Summe) when Summe == Value -> true; 
checkHorizontal([], Value, Summe) -> false. 

checkAllVertical(Square, N, Value) -> checkAllVertical(Square, N, Value, 1). 
checkAllVertical(Square, N, Value, Column) -> 
    if 
     Column > N -> true; 
     true -> 
      case checkVertical(Square, Value, 0, Column) of 
       true -> checkAllVertical(Square, N, Value, Column + 1); 
       false -> false 
      end 
    end. 

checkVertical([], Value, Summe, Column) when Summe == Value -> true; 
checkVertical([], Value, Summe, Column) -> false; 
checkVertical([H|T], Value, Summe, Column) -> checkVertical(T, Value, Summe + lists:nth(Column, H), Column). 

checkAllDiagonal(Square, Value) -> 
    case checkDiagonal(Square, Value, 0, 1,1) of 
     true -> case checkDiagonal(Square, Value, 0, length(lists:nth(1, Square)),-1) of 
          true -> true; 
          false -> false 
         end; 
     false -> false 
    end. 

checkDiagonal([H|T], Value, Summe, Position, Richtung) -> checkDiagonal(T, Value, Summe + lists:nth(Position, H), Position + Richtung, Richtung); 
checkDiagonal([], Value, Summe, Position, Richtung) when Summe == Value -> true; 
checkDiagonal([], Value, Summe, Position, Richtung) -> false. 

好，我試圖添加檢查行和更早在計算過程中的廣場。這裏是修改後的功能。

buildSquare(0, _, _, _) -> [[]]; 
buildSquare(Rows, AvailableRows, RowLength, Value) -> 
    [ [X|L] || L <- buildSquare(Rows-1, AvailableRows, RowLength, Value), X <- AvailableRows, validateSquare([X|L], RowLength, Value)]. 

checkOnlyUniqueNumbers(List) -> erlang:length(lists:flatten(List)) == sets:size(sets:from_list(lists:flatten(List))). 

validateSquare(List, RowLength, Value) when length(List) == RowLength -> testsquare(List, RowLength, Value) andalso checkOnlyUniqueNumbers(List); 
validateSquare(List, _,_) -> checkOnlyUniqueNumbers(List). 

%produces all possible rows with a dimension of Fields and the Numbers from 1 to Numbers 
makeRows(0,_,_,_) -> [[]]; 
makeRows(Fields, Numbers, Value, TargetLength) -> 
    [ [X|L] || L <- makeRows(Fields-1, Numbers, Value, TargetLength), X <- lists:seq(1,Numbers), checkRow([X|L], TargetLength, Value)]. 

%Checks if the sum of the row is Value when the row has the needed length Length 
checkRow(Row, Length, _) when length(Row) < Length -> checkOnlyUniqueNumbers(Row); 
checkRow(Row, _, Value) -> 
    Sum = lists:sum(Row), 
    Sum == Value andalso checkOnlyUniqueNumbers(Row). 

Answer 1

那麼，Erlang是不懶惰，所以

magicSquare(N, Value) -> 
    Squares = buildSquare(N, makeRows(N, N*N, Value, N)), 

嘗試構建四行所有3121348608個可能組合的列表，每個求和至34，使用的所有數字從1至16 （包括）之間，當用參數4和34調用時。

即使每個方塊只需要16個字節（每個單元一個），這將需要大約48GB的內存，不計算列表開銷。

你的算法雖然會慢一些，但卻很慢 - 用一種懶惰的語言。但是在非懶惰語言中，您需要需要來更多和更早地修剪，或選擇完全不同的算法。

您可以測試垂直線和對角線是否有機會與buildSquare中已經達到的目標值相加，這可能會將內存要求降低到足以適合4 x 4魔術方塊的內存（但I'米不如說服）。如果僅構建(N-1)×N網格並計算垂直總和中的最後一行，那麼會將Squares的大小減小另一個因子N!，這樣可以更好地將它嵌入內存（對於N == 4，對於較大的N並非真正對於較大的N），以及早期的修剪。

但是您應該重構您的算法以儘可能早地使用約束。假設你檢查第一行1 2 15 16。然後你知道左邊欄中1以下的三個數字和主對角線上剩下的三個數字必須總和爲33.所以你需要一組六個數字，從{ 3,4,5,6,7,8,9,10,11,12,13,14}中選擇六個數字，總和爲66.沒有多少選擇這六個數字，因爲其中最大的六個總和只有69個，所以你有

6, 10, 11, 12, 13, 14 
7, 9, 11, 12, 13, 14 
8, 9, 10, 12, 13, 14 

只有三種可能性。底角的兩個數字也受右列和主要東北對角線的限制。考慮到這些限制條件進一步限制了搜索空間。

如果考慮可能的順序廣場，一個頂行前一後，不保存考生[你可以存儲神奇4×4格，他們沒有太多的]，你可以找到所有小記憶中的魔方，如果你以一種好的方式處理約束，甚至可以相對快速地處理。

Answer 2

我有可能證明是有益的方向。我幾乎有工作，但將無法在未來幾天花時間就可以了。

首先，雖然，我相信這個問題是NP完全這將表明您要使用指數內存或時間線性輸入尺寸增大。

在任何情況下，這是我的方法：

1. 如果你的幻方涉及的數字1..N，你去爲那些N個所有排列。畢竟，幻方（3,15）將是1..15

2. 所有可能的排列的一個子集的訣竅是，因爲它是生成如果以除去每個置換所有它代表不行的總結到幻數。這樣你就不會存儲所有的排列，只有那些非常有希望的排列，從而避免了指數內存（但不是指數時間）。換句話說，符合產生每個排列，只有在它有可能是一個幻方時才保存它。我用一個列表理解來創建一個生成器做了測試限定詞的排列，以確保所有行的正確總結

3. 我的測試功能採取的是表示在這種情況下，行長度（3參數），並能夠檢查[8,1,6,3,5,7,4,9,2]的排列並確定每行（每個子列表1-3,4-6,7-9總計爲15 。
4. 得到排列，每一個行總和的幻數至少，然後篩選的MN標準的休息之後。

確保您的算法創建的排列是尾遞歸， 順便一提。

同樣，這似乎是爲我工作（除非它不是;）），但我從我的電腦離開幾天。

希望這會有所幫助。