% This program solves magic squares too, but is more is more efficient
% than simple generate and test.
% Instead of waiting for a complete solution to be generated, whenever
% enough of the solution has been chosen to test a constraint (that
% is a row, column or diagonal sum), the partial solution is tested.
% If the numbers in the square are allocated from the top right by rows,
% tests can be done at the end of the first row (after the first three
% numbers) at the end of the second row (after the next three) and as
% each of the last row is completed.
% Five predicates are defined to generate the solution: gen_magic_123,
% gen_magic_456, gen_magic_7, gen_magic_8 and gen_magic_9.
% Five matching test predicates are also defined: test_magic_123,
% test_magic_456, test_magic_7, test_magic_8 and test_magic_9.
% These are used alternately by the predicate prune_magic with.
prune_magic(Magic,Sum) :-
gen_magic_123(Magic,[1,2,3,4,5,6,7,8,9],Rest1to3),
write('trying partial solution '), write(Magic), nl,
test_magic_123(Magic,Sum),
write('OK so far ...'), nl,
gen_magic_456(Magic,Rest1to3,Rest4to6),
write('trying partial solution '), write(Magic), nl,
test_magic_456(Magic,Sum),
write('OK so far ...'), nl,
gen_magic_7(Magic,Rest4to6,Rest7),
write('trying partial solution '), write(Magic), nl,
test_magic_7(Magic,Sum),
write('OK so far ...'), nl,
gen_magic_8(Magic,Rest7,Rest8),
write('trying partial solution '), write(Magic), nl,
test_magic_8(Magic,Sum),
write('OK so far ...'), nl,
gen_magic_9(Magic,Rest8,[]),
write('trying partial solution '), write(Magic), nl,
test_magic_9(Magic,Sum),
write('YES!'), nl.
% The generate predicates simply choose the relevant cells in
% the solution (using the same representation as in the generte
% and test code).
% Notice how these simply break up the generate_magic predicate
% from the generate and test code.
gen_magic_123([N11,N12,N13,_,_,_,_,_,_],List,Rest13) :-
choose_list(N11,List,Rest11),
choose_list(N12,Rest11,Rest12),
choose_list(N13,Rest12,Rest13).
gen_magic_456([_,_,_,N21,N22,N23,_,_,_],List,Rest23) :-
choose_list(N21,List,Rest21),
choose_list(N22,Rest21,Rest22),
choose_list(N23,Rest22,Rest23).
gen_magic_7([_,_,_,_,_,_,N31,_,_],List,Rest31) :-
choose_list(N31,List,Rest31).
gen_magic_8([_,_,_,_,_,_,_,N32,_],List,Rest32) :-
choose_list(N32,List,Rest32).
gen_magic_9([_,_,_,_,_,_,_,_,N33],List,Rest33) :-
choose_list(N33,List,Rest33).
% The same choose_list predicate is used as in the generate
% and test solution.
choose_list(N,[N|Rest],Rest).
choose_list(N,[M|Rest],[M|R2]) :- choose_list(N,Rest,R2).
% Like the generate predicates, the test predicates are a
% split ou form of test_magic in the generate and test code.
% In fact, this is often a good way to produce efficient search
% code, simply write the generate and test code and then merge
% the generate and test parts, testing as soon as possible.
test_magic_123([N11,N12,N13,_,_,_,_,_,_],Sum) :-
Sum is N11+N12+N13. % row 1
test_magic_456([_,_,_,N21,N22,N23,_,_,_],Sum) :-
Sum is N21+N22+N23. % row 2
test_magic_7([N11,_,N13,N21,N22,_,N31,_,_],Sum) :-
Sum is N11+N21+N31, % column 1
Sum is N13+N22+N31. % diagonal running north east
test_magic_8([_,N12,_,_,N22,_,_,N32,_],Sum) :-
Sum is N12+N22+N32. % column 2
test_magic_9([N11,_,N13,_,N22,N23,N31,N32,N33],Sum) :-
Sum is N31+N32+N33, % row 3
Sum is N13+N23+N33, % column 3
Sum is N11+N22+N33. % diagonal running north west