当在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标准的休息之后。

确保您的算法创建的排列是尾递归， 顺便一提。

同样，这似乎是为我工作（除非它不是;）），但我从我的电脑离开几天。

希望这会有所帮助。