examples/prolog/peg.pl

% File   : peg.pl
% Authors: Naoyuki Tamura (tamura@kobe-u.ac.jp)
% Updated: 14 February 2008
% Purpose: Peg solitaire game
% Notes  : Slightly changed by M.Banbara

/*
This solitaire game consists of a board of the following shape
and initial configuration

        x
       x x
      x o x
     x x x x
    x x x x x

where x denotes a peg and o an empty hole.  A peg may jump over
an adjacent peg if the hole behind it is empty.  The goal is to
be left with one peg.  I fooled around with this for about 2
minutes and decided it was too hard by hand---a Lolli program
was called for.
*/

main :-
	write('Peg puzzle (N>=6 takes a long time...)'), nl,
	write('N = '),
	current_output(Out),
	flush_output(Out),
	read(N), integer(N),
	write('Position of the first empty hole'), nl,
	write('Row (1..'), write(N), write(') = '),
	flush_output(Out),
	read(I0), integer(I0),
	write('Col (1..'), write(I0), write(') = '),
	flush_output(Out),
	read(J0), integer(J0),
	statistics(runtime, _),
	peg_game(N, I0, J0, Solution),
	statistics(runtime, [_,T]),
	write(Solution), nl,
	write('CPU time = '), write(T), write(' msec'), nl.
main :-
	statistics(runtime, [_,T]),
	write('No solutions'), nl,
	write('CPU time = '), write(T), write(' msec'), nl.

peg_game(N, I0, J0, S) :-
	N >= 3,
	0 < I0, I0 =< N,
	0 < J0, J0 =< I0,
	Step is N*(N+1)//2 - 2,
	place_pegs(N, N, I0, J0, Board),
	jump(Step, Board, S).

place_pegs(N, N, I0, J0, Board) :-
	place_pegs(N, N, I0, J0, [], Board).

place_pegs(0, 0, I0, J0, B0, B) :-
	peg_delete(B0, peg(I0, J0), B1),!,
	B = [empty(I0, J0)|B1].
place_pegs(M, 0, I0, J0, B0, B) :-
	M > 0,
	M1 is M-1,
	place_pegs(M1, M1, I0, J0, B0, B).
place_pegs(M, N, I0, J0, B0, B) :-
	M > 0, N > 0,
	N1 is N-1,
	place_pegs(M, N1, I0, J0, [peg(M,N)|B0], B).

peg_delete([P|Ys], P, Ys) :- !.
peg_delete([X|Ys], P, [X|Zs]) :-
	peg_delete(Ys, P, Zs).

peg_select(X, [X|Xs], Xs).
peg_select(X, [Y|Ys], [Y|Zs]) :- peg_select(X, Ys, Zs).

jump(Step, Board0, [move(X,Y,DX,DY)|Ms]) :-
	Step > 0,
	peg_select(peg(X,Y), Board0, Board1),
	direction(DX, DY),
	X1 is X+DX, Y1 is Y+DY,
	peg_select(peg(X1,Y1), Board1, Board2),
	X2 is X1+DX, Y2 is Y1+DY,
	peg_select(empty(X2,Y2), Board2, Board3),
	Step1 is Step-1,
	Board = [empty(X,Y), empty(X1, Y1), peg(X2, Y2)|Board3],
	jump(Step1, Board, Ms).
jump(0, _, []).

direction( 1, 0).
direction( 1, 1).
direction( 0, 1).
direction(-1, 0).
direction(-1,-1).
direction( 0,-1).