prune.p

%  =================================================================
%  ==                                                             ==
%  ==          An Introduction to ARTIFICIAL INTELLIGENCE         ==
%  ==                  Janet Finlay and Alan Dix                  ==
%  ==                       UCL Press, 1996                       ==
%  ==                                                             ==
%  =================================================================
%  ==                                                             ==
%  ==         chapter 3, pages 50-51:  search tree pruning        ==
%  ==                                                             ==
%  ==            Prolog example, Alan Dix, August 1996            ==
%  ==                                                             ==
%  =================================================================

%  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

%  RUNNING THIS CODE
%
%  You can type:

%>     prune_magic(Magic,Sum).
%
%  It will give you a solution somewhat faster than the
%  generate and test code (time them both if you can be bothered
%  to wait for generate and test!
%  
%  Howevere, for even faster reponse, you know that the sum of
%  the magic square must be 15 = (1+2+3+4+5+6+7+8+9)/3 so you
%  can instead type:

%>     prune_magic(Magic,15).
%
%  This will run much faster again.
%  Without the hint that the sum has to be 15, the test at stage '1to3'
%  will do no pruning and the first pruning cannot occur until '4to6',
%  when the first and second rows can be compared.
%
%  Lesson:  a little bit of foresight can make a search perform
%           phenominaly faster
%

%  EXERCISE
%
%  In the book, we noted that different orders for choosing the numbers
%  in the partial solution can make it faster or slower.
%  The example at the bottom of page 50 is particularly bad!
%  Modify the above code to make it search in an even more efficient
%  fashion!  (hint see page 73).
%