Too much memory consumption when generating magic squares in erlang - Need help for optimization

Question

for university I have to implement an algorithm which creates all possibile magic squares for a given edge length and a specific sum. For n=3 the algorithm is working as expected. But when generating all magic squares for n=4 after a while I ran out of memory. This problem was already mentioned in the task description. I already tried to optimize the a code but it is still not working as it should. So I hope someone can give me some advice.

My basic idea is: First I generate all possible rows which I can use with the given numbers and then I'm trying to combine these in a way that the restrictions of a magic square are fullfilled. This happens via backtracking. I think the problem is the function makeRows which consumes too much memory after while for storing all the rows.

If you need some more explanation of the code I can give!

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.

Ok I've tried to add checks for rows and squares earlier in the calculation process. Here are the modified functions.

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).

could we add some concurrency here ? Erlang ninjas, what can be parallelized here? — Muzaaya Joshua, Dec 13 '12 at 16:13
I also thought about this but for now I would be happy if the algorithm would work in general (means with less than 48GB of ram). I think the process of building the squares could be parallelized but I'm not quite sure how I would avoid double calculations — soupdiver, Dec 13 '12 at 16:15

score 9 · Answer 1 · answered Dec 13 '12 at 13:31

Well, erlang isn't lazy, so

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

tries to build the list of all 3121348608 possible combinations of four rows, each summing to 34, using all the numbers from 1 to 16 (inclusive) between them, when called with arguments 4 and 34.

Even if each square took only 16 bytes (one for each cell), that would need about 48GB of memory, not counting list overhead.

Your algorithm would work - albeit slowly - in a lazy language. But in a non-lazy language, you need to prune more and earlier, or choose an altogether different algorithm.

You could test whether the verticals and diagonals even have a chance to sum to the target value already in buildSquare, that might push the memory requirement low enough that it fits into memory for a 4×4 magic square (but I'm less than convinced). If you build only (N-1)×N grids and compute the last row from the vertical sums, that would reduce the size of Squares by another factor of N!, that has a better chance of fitting into memory (for N == 4, not really for larger N) together with the earlier pruning.

But you should restructure your algorithm to use the constraints as early as possible. Say you check the first row 1 2 15 16. Then you know that the three numbers below 1 in the left column, and the three remaining numbers on the main diagonal each must sum to 33. So you need a set of six numbers chosen from { 3,4,5,6,7,8,9,10,11,12,13,14} summing to 66. There aren't many choices of these six numbers, since the six largest among them sum to 69 only, so you have

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

only three possibilities. The two numbers in the bottom corners are also constrained by the right column, and the main north-east diagonal. Considering these constraints together further restricts the search space.

If you consider the possible squares sequentially, one top-row after the other, and don't store the candidates [you could store the magic 4×4 squares, they aren't too many], you can find all magic squares in small memory, and if you handle the constraints in a good way, even relatively quickly.

ok so I have to combine buildSquare and makeRows somehow in one function so that I can check much earlier if square makes sense or not right? — soupdiver, Dec 13 '12 at 15:32
No, you can have `makeRows` separate as is (though it would be more efficient to pass it the list of eligible numbers so that no number is used more than once from the start), but you have to do more and earlier checking in `buildSquare`. N(ebenbei) B(emerkt), you have mixed up `X` and `L` in one place in `makeRows`. — Daniel Fischer, Dec 13 '12 at 15:40
You draw `X` from the recursive call to `makeRows`, and `L` from the `seq(1,n)`, but in the result you put `[X|L]`, so the list before the number (yay for static typing, that would have caught it at compile time). In one of the two places, you should exchange `X` and `L`. — Daniel Fischer, Dec 13 '12 at 15:51
ok I've added some modifications in my post. What do you think could this work out? — soupdiver, Dec 13 '12 at 16:07
Just for interest's sake, I *believe* that the general magic-square problem is NP-complete meaning (loosely speaking) that all algorithmic solutions to the general case will require exponentially increasing memory or time (or both) with respect to the size of the input of the problem. — Jr0, Dec 14 '12 at 14:48

score 0 · Answer 2 · answered Dec 23 '12 at 18:17

I have a direction that might prove helpful. I almost have it working, but will not be able to spend any time on it over the next couple of days.

First though, I believe this problem is NP-Complete which would indicate that you are going to use exponential memory or time as the input size increases linearly.

In any event, this was my approach:

If your magic square involves the numbers 1..N, your going to create all permutations for those N numbers. After all, magicSquare(3,15) will be a subset of all possible permutations of 1..15
The trick is to remove each permutation as it is generated if all of the rows that it represents do not sum up to the magic number. In this way you do not store all permutations, only those which are very promising thereby avoiding exponential memory (but not exponential time). In other words, in-line with generating each permutation, only save it if it is possible for it to be a magic square. I used a list comprehension to create the permutations with a qualifier on a generator that did a test to ensure that all of the rows summed correctly
My test function took a parameter that indicated the row length (3 in this case) and was able to examine the permutation of [8,1,6,3,5,7,4,9,2] and determine that each row (each sublist 1-3, 4-6,7-9 summed to 15.
after getting the permutations where at least every row sums to the Magic Number, then filter for the rest of the MN criteria.

Make sure that your algorithm to create the permutations is tail-recursive, by the way.

Again, this seemed to be working for me (except where it wasn't ;)), but I am away from my computer for a few days.

Hopefully this helps.

I think I already do this... `makeRows(Fields, Numbers, Value, TargetLength) -> [ [X|L] || L <- makeRows(Fields-1, Numbers, Value, TargetLength), X <- lists:seq(1,Numbers), checkRow([X|L], TargetLength, Value)]. ` already checks every new generated row it it is possible to use. The problem is `buildSquare` I just don't detect early enough if the square can make a valid one — soupdiver, Dec 24 '12 at 15:19

Too much memory consumption when generating magic squares in erlang - Need help for optimization

2 Answers2