Prolog recursing through list of lists

Question

I'm attempting a prolog question that states the following:

A magic square is a 3× 3 matrix of distinct numbers (between 1 and 9) such that all rows and columns add up to the same total (but not necessarily the diagonals). For example: 2 7 6 9 5 1 4 3 8 is a magic square. We will represent squares in Prolog as 3 × 3 matrices, i.e. lists of lists [R1, R2, R3] where each R_i is a list of three numbers. For example, the representation of the above magic square is [[2,7,6],[9,5,1],[4,3,8]]

Define a predicate magic/1 that tests whether a ground 3 × 3 matrix (i.e. where all the entries are numbers) is a magic square.

I've done this the following way, and I'm pretty sure it's allowed if I also do it like this in an exam, however to me it seems like sort of a hack:

magic([[A,B,C], [D,E,F], [G,H,I]]) :- 
                Y is A + B + C, 
                Y is D + E + F, 
                Y is G + H + I, 
                Y is A + D + G,
                Y is B + E + H,
                Y is C + F + I.

My desired way would be to recurse through each list in the outer list, and sum it up. For each of the lists in outer list, they should sum up to the same value (I think 15 is actually the only possible solution for this "magic" matrix). Likewise, I do the same for the columns (take the first, second and 3rd of each list and add up respectively). However, I'm not entirely sure how to do the latter as I haven't been working with list of lists much. I would appreciate if anybody would give a neat solution on how these sort of computations can be done generally.

Thanks

score 0 · Answer 1 · edited May 23 '17 at 12:16

Note that your solution does not check that A, ..,I values are distinct and in the range 1..9. Here is a solution for NxN squares for N > 2:

magic(L) :-
    magic_range(L),
    magic_sum(S, L),
    magic_line(S, L),
    transpose(L, T),
    magic_line(S, T).

% S value from https://oeis.org/A006003
magic_sum(S, L) :-
    length(L, N),
    S is N * (N*N + 1) / 2.

magic_range(L) :-
    flatten(L, F),
    sort(F, S),
    length(L, N),
    N2 is N * N,
    numlist(1, N2, S).

magic_line(_, []).
magic_line(S, [A | As]) :-
    sumlist(A, S),
    magic_line(S, As).

% https://github.com/SWI-Prolog/swipl-devel/blob/9452af09962000ebb5157fe06169bbf51af5d5c9/library/clp/clpfd.pl#L6411
transpose(Ls, Ts) :-
    must_be(list(list), Ls),
    lists_transpose(Ls, Ts).

lists_transpose([], []).
lists_transpose([L|Ls], Ts) :-
    foldl(transpose_, L, Ts, [L|Ls], _).

transpose_(_, Fs, Lists0, Lists) :-
    maplist(list_first_rest, Lists0, Fs, Lists).

list_first_rest([L|Ls], L, Ls).

Some queries

?- magic([[1,1,1],[1,1,1],[1,1,1]]).
false.

?- magic([[2,7,6],[9,5,1],[4,3,8]]).
true ;
false.

?- magic([[16,3,2,13], [5,10,11,8], [9,6,7,12], [4,15,14,1]]).
true ;
false.

The transpose predicate is the most complicated part. See here for some alternatives.

Prolog recursing through list of lists

1 Answers1