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