% From the book
% PROLOG PROGRAMMING IN DEPTH
% by Michael A. Covington, Donald Nute, and Andre Vellino
% (Prentice Hall, 1997).
% Copyright 1997 Prentice-Hall, Inc.
% For educational use only

% TRIANGLE.PL
% This program solves the triangle puzzle.

%
% triangle(+N)
%   Finds and displays a solution to the triangle problem
%   where the Nth peg is removed first.
%

triangle(N) :-
     remove_peg(N,StartingTriangle),
     solve_triangle(14,[StartingTriangle],Solution),
     reverse(Solution,[],OrderedSolution),
     nl,nl,
     show_triangles(OrderedSolution).

%
% solve_triangle(+N,+Sofar,-Solution)
%   Searches for a solution to the triangle problem from a
%   position with N pegs arranged in the pattern Sofar.
%

solve_triangle(1,Solution,Solution).
solve_triangle(Count,[CurrentTriangle|PriorTriangles],Solution):-
     jump(CurrentTriangle,NextTriangle),
     NewCount is Count - 1,
     write(NewCount), nl,
     solve_triangle(NewCount,
                    [NextTriangle,CurrentTriangle|PriorTriangles],
                    Solution).

%
% remove_peg(+N,-Triangle)
%   Produces a Triangle with an empty Nth hole and pegs
%   in all other holes.
%

remove_peg(1,triangle(0,1,1,1,1,1,1,1,1,1,1,1,1,1,1)).
remove_peg(2,triangle(1,0,1,1,1,1,1,1,1,1,1,1,1,1,1)).
remove_peg(3,triangle(1,1,0,1,1,1,1,1,1,1,1,1,1,1,1)).
remove_peg(4,triangle(1,1,1,0,1,1,1,1,1,1,1,1,1,1,1)).
remove_peg(5,triangle(1,1,1,1,0,1,1,1,1,1,1,1,1,1,1)).
remove_peg(6,triangle(1,1,1,1,1,0,1,1,1,1,1,1,1,1,1)).
remove_peg(7,triangle(1,1,1,1,1,1,0,1,1,1,1,1,1,1,1)).
remove_peg(8,triangle(1,1,1,1,1,1,1,0,1,1,1,1,1,1,1)).
remove_peg(9,triangle(1,1,1,1,1,1,1,1,0,1,1,1,1,1,1)).
remove_peg(10,triangle(1,1,1,1,1,1,1,1,1,0,1,1,1,1,1)).
remove_peg(11,triangle(1,1,1,1,1,1,1,1,1,1,0,1,1,1,1)).
remove_peg(12,triangle(1,1,1,1,1,1,1,1,1,1,1,0,1,1,1)).
remove_peg(13,triangle(1,1,1,1,1,1,1,1,1,1,1,1,0,1,1)).
remove_peg(14,triangle(1,1,1,1,1,1,1,1,1,1,1,1,1,0,1)).
remove_peg(15,triangle(1,1,1,1,1,1,1,1,1,1,1,1,1,1,0)).

%
% jump(+CurrentTriangle,-NextTriangle)
%   Finds a NextTriangle that can be produced from
%   CurrentTriangle by a legal jump. To save space,
%   all but the first clause are displayed in linear
%   format.
%

jump(triangle(1,
             1,C,
            0,E,F,
           G,H,I,J,
          K,L,M,N,P),
     triangle(0,
             0,C,
            1,E,F,
           G,H,I,J,
          K,L,M,N,P)).
jump(triangle(1,B,1,D,E,0,G,H,I,J,K,L,M,N,P),
     triangle(0,B,0,D,E,1,G,H,I,J,K,L,M,N,P)).
jump(triangle(A,1,C,1,E,F,0,H,I,J,K,L,M,N,P),
     triangle(A,0,C,0,E,F,1,H,I,J,K,L,M,N,P)).
jump(triangle(A,1,C,D,1,F,G,H,0,J,K,L,M,N,P),
     triangle(A,0,C,D,0,F,G,H,1,J,K,L,M,N,P)).
jump(triangle(A,B,1,D,1,F,G,0,I,J,K,L,M,N,P),
     triangle(A,B,0,D,0,F,G,1,I,J,K,L,M,N,P)).
jump(triangle(A,B,1,D,E,1,G,H,I,0,K,L,M,N,P),
     triangle(A,B,0,D,E,0,G,H,I,1,K,L,M,N,P)).
jump(triangle(0,1,C,1,E,F,G,H,I,J,K,L,M,N,P),
     triangle(1,0,C,0,E,F,G,H,I,J,K,L,M,N,P)).
jump(triangle(A,B,C,1,1,0,G,H,I,J,K,L,M,N,P),
     triangle(A,B,C,0,0,1,G,H,I,J,K,L,M,N,P)).
jump(triangle(A,B,C,1,E,F,G,1,I,J,K,L,0,N,P),
     triangle(A,B,C,0,E,F,G,0,I,J,K,L,1,N,P)).
jump(triangle(A,B,C,1,E,F,1,H,I,J,0,L,M,N,P),
     triangle(A,B,C,0,E,F,0,H,I,J,1,L,M,N,P)).
jump(triangle(A,B,C,D,1,F,G,1,I,J,K,0,M,N,P),
     triangle(A,B,C,D,0,F,G,0,I,J,K,1,M,N,P)).
jump(triangle(A,B,C,D,1,F,G,H,1,J,K,L,M,0,P),
     triangle(A,B,C,D,0,F,G,H,0,J,K,L,M,1,P)).
jump(triangle(0,B,1,D,E,1,G,H,I,J,K,L,M,N,P),
     triangle(1,B,0,D,E,0,G,H,I,J,K,L,M,N,P)).
jump(triangle(A,B,C,0,1,1,G,H,I,J,K,L,M,N,P),
     triangle(A,B,C,1,0,0,G,H,I,J,K,L,M,N,P)).
jump(triangle(A,B,C,D,E,1,G,H,1,J,K,L,0,N,P),
     triangle(A,B,C,D,E,0,G,H,0,J,K,L,1,N,P)).
jump(triangle(A,B,C,D,E,1,G,H,I,1,K,L,M,N,0),
     triangle(A,B,C,D,E,0,G,H,I,0,K,L,M,N,1)).
jump(triangle(A,0,C,1,E,F,1,H,I,J,K,L,M,N,P),
     triangle(A,1,C,0,E,F,0,H,I,J,K,L,M,N,P)).
jump(triangle(A,B,C,D,E,F,1,1,0,J,K,L,M,N,P),
     triangle(A,B,C,D,E,F,0,0,1,J,K,L,M,N,P)).
jump(triangle(A,B,0,D,1,F,G,1,I,J,K,L,M,N,P),
     triangle(A,B,1,D,0,F,G,0,I,J,K,L,M,N,P)).
jump(triangle(A,B,C,D,E,F,G,1,1,0,K,L,M,N,P),
     triangle(A,B,C,D,E,F,G,0,0,1,K,L,M,N,P)).
jump(triangle(A,0,C,D,1,F,G,H,1,J,K,L,M,N,P),
     triangle(A,1,C,D,0,F,G,H,0,J,K,L,M,N,P)).
jump(triangle(A,B,C,D,E,F,0,1,1,J,K,L,M,N,P),
     triangle(A,B,C,D,E,F,1,0,0,J,K,L,M,N,P)).
jump(triangle(A,B,0,D,E,1,G,H,I,1,K,L,M,N,P),
     triangle(A,B,1,D,E,0,G,H,I,0,K,L,M,N,P)).
jump(triangle(A,B,C,D,E,F,G,0,1,1,K,L,M,N,P),
     triangle(A,B,C,D,E,F,G,1,0,0,K,L,M,N,P)).
jump(triangle(A,B,C,0,E,F,1,H,I,J,1,L,M,N,P),
     triangle(A,B,C,1,E,F,0,H,I,J,0,L,M,N,P)).
jump(triangle(A,B,C,D,E,F,G,H,I,J,1,1,0,N,P),
     triangle(A,B,C,D,E,F,G,H,I,J,0,0,1,N,P)).
jump(triangle(A,B,C,D,0,F,G,1,I,J,K,1,M,N,P),
     triangle(A,B,C,D,1,F,G,0,I,J,K,0,M,N,P)).
jump(triangle(A,B,C,D,E,F,G,H,I,J,K,1,1,0,P),
     triangle(A,B,C,D,E,F,G,H,I,J,K,0,0,1,P)).
jump(triangle(A,B,C,D,E,F,G,H,I,J,0,1,1,N,P),
     triangle(A,B,C,D,E,F,G,H,I,J,1,0,0,N,P)).
jump(triangle(A,B,C,0,E,F,G,1,I,J,K,L,1,N,P),
     triangle(A,B,C,1,E,F,G,0,I,J,K,L,0,N,P)).
jump(triangle(A,B,C,D,E,0,G,H,1,J,K,L,1,N,P),
     triangle(A,B,C,D,E,1,G,H,0,J,K,L,0,N,P)).
jump(triangle(A,B,C,D,E,F,G,H,I,J,K,L,1,1,0),
     triangle(A,B,C,D,E,F,G,H,I,J,K,L,0,0,1)).
jump(triangle(A,B,C,D,E,F,G,H,I,J,K,0,1,1,P),
     triangle(A,B,C,D,E,F,G,H,I,J,K,1,0,0,P)).
jump(triangle(A,B,C,D,0,F,G,H,1,J,K,L,M,1,P),
     triangle(A,B,C,D,1,F,G,H,0,J,K,L,M,0,P)).
jump(triangle(A,B,C,D,E,F,G,H,I,J,K,L,0,1,1),
     triangle(A,B,C,D,E,F,G,H,I,J,K,L,1,0,0)).
jump(triangle(A,B,C,D,E,0,G,H,I,1,K,L,M,N,1),
     triangle(A,B,C,D,E,1,G,H,I,0,K,L,M,N,0)).

%
% Procedure to display a solution.
%

show_triangles([]) :- !.
show_triangles([
     triangle(A,
             B,C,
            D,E,F,
           G,H,I,J,
          K,L,M,N,P)|LaterTriangles]) :-
     sp(4),write(A),nl,
     sp(3),write(B),sp(1),write(C),nl,
     sp(2),write(D),sp(1),write(E),sp(1),write(F),nl,
     sp(1),write(G),sp(1),write(H),sp(1),write(I),sp(1),write(J),nl,
     write(K),sp(1),write(L),sp(1),write(M),sp(1),
          write(N),sp(1),write(P),nl,
     write('Press any key to continue. '),
     get0(_),
     nl,nl,
     show_triangles(LaterTriangles).

sp(0).
sp(N) :- write(' '),
         M is N - 1,
         sp(M).