🚀 go-pugleaf

I might as well tell you what the interesting thing is about the
Triangle Puzzle program.  The puzzle is that you have a triangle
with holes for pegs in it, and 15 pegs.  The board looks like
			A
		      B   C
		    D   E   F
		  G   H   I   J
	        K   L   M   N   O
You start by removing any one of the pegs.  From then on a move
is to hop a peg over another peg into a hole, removing the peg
you hopped over:  (Peg)--(Peg)--(Hole) -> (Hole)--(Hole)--(Peg).
The goal is to remove all but one peg.

"Prolog Programming in Depth" contains the following predicate:

	legal_jump(OldBoard, NewBoard) :-
		peg(X, OldBoard),
		jump(X, Y, Z),
		not peg(Z, OldBoard),
		peg(Y, OldBoard),
		set_peg(0, X, OldBoard, W1),
		set_peg(0, Y, W1, W2),
		set_peg(1, Z, W2, NewBoard).

where jump/3 is a table containing entries like

	jump(1 /* =A */, 2 /* =B */, 4 /* =D */).

peg/2 is a table containing entries like

	peg(4, [_,_,_,1,_,_,_,_,_,_,_,_,_,_,_]).

and set_peg/4 is a table containing entries like

	set_peg(X, 4, [A,B,C,D,E,F,G,H,I,J,K,L,M,N,O],
		      [A,B,C,X,E,F,G,H,I,J,K,L,M,N,O]

It is easy to work out that there are 36 clauses in jump/3,
15 clauses in peg/2, and 15 clauses in set_peg/4.

There are lots of things wrong with this, starting with the use of a
list to represent the board.  Covington et al describe set_peg/4 as
"a very efficient way" of updating the board.  It is hardly that; I
haven't even mentioned the second thing wrong with it.  But one thing
really draws smashes its fist into the eye:  that 'not'.

Now, the program is such that when 'not peg(Z, OldBoard)' is called,
both Z and OldBoard are ground, and peg/2 is a base relation, so the
negation is sound.  That's not the problem.  The problem is that it
doesn't mean quite what you think it does.  Remember that we are
looking for the pattern (X:peg)--(Y:peg)--(Z:hole), where Covington
et al have chosen to represent "peg" by 1 and "hole" by 0 (that's
not such a wonderful idea itself, by the way).  What we want to
know is that there is a hole at Z.  'not peg(Z, OldBoard)' doesn't
mean that.  It means "it is not the case that there is a peg at Z
in OldBoard."  There are several ways it might succeed:
 o OldBoard might not be a list of 15 elements
 o Z might not be a position in the board
 o there might be something there other than a peg or a hole.
Isn't this nit-picking?  Well, when you consider that there is a typo
("21" for "12") in the jump/3 table, the possibility that Z might be
out of range is not so remote...

What's a clean way to do this?  Well, if we want to know whether there
is a hole at position Z, THAT's the thing to ask!  What should be done
is something like

	legal_jump(OldBoard, NewBoard) :-
		in_board(X, OldBoard, 1 /* peg */),
		jump(X, Y, Z),
		in_board(Z, OldBoard, 0 /* hole */),
		in_board(Y, OldBoard, 1 /* peg */),
		...

where in_board/3 is a table of clauses like

	in_board(4, [_,_,_,X,_,_,_,_,_,_,_,_,_,_,_], X).

But it's a bit of a pain to test the positions of the board one at
a time.  Why not just write patterns to match the possible jumps?
And again, the intermediate lists with the extremely odd names W1
and W2 are of no interest whatsoever.  What we want to know is the
effect of a particular jump on the board.  Pushing this to the
limit of cleanliness, I came up with

	legal_jump(OldBoard, NewBoard) :-
		jump(_, OldBoard, NewBoard).

where jump/3 was now a table of facts like

jump( 5, 	f(		A,
			      B,  +,
			    D,  +,  F,
			  G,  -,  I,  J,
		        K,  L,  M,  N,  Q	),
		f(		A,
			      B,  -,
			    D,  -,  F,
			  G,  +,  I,  J,
		        K,  L,  M,  N,  Q	)).

This looks like a lot more work to write than the Covington et al
version.  In fact it is less work.  To start with, we have replaced
36+30+30 = 66 clauses by 36.  Each clause of the new jump/3 is about
as complex as a clause of set_peg/3, which may be clearer if it is
written as

jump(5, f(A,B,+,D,+,F,G,-,I,J,K,L,M,N,Q),
        f(A,B,-,D,-,F,G,+,I,J,K,L,M,N,Q)).

I want to stress this, because at first blush just writing down the
legal jumps like this looks like cheating.  But the original jump/3
table was no less a table of jumps; I have merely chosen a more
natural coding than triples of integers.

Making the table was easy.  I typed one copy of the triangle into an
editor, made a second copy of it, and put the jump(xx,) wrapper around
it.  I made 36 copies of the resulting clause, and zipped through
drawing in the peg- present (+) and peg-absent (-) marks.  The "5" here
was an arbitrary label for the move.  I never once had to count things;
all I had to be able to do was see straight lines.  I am sure that
Covington et al proof-read their book carefully; I attribute the two
typos in their jump/3 table to the fact that their representation was
peculiarly hard to check.


There was another interesting point in the Covington et al program.
The top level of their program looks roughly like this:

triangle(N) :-
	make_first_board(N, FirstBoard),
	triangle_solver(14, [FirstBoard], Solution),
	fast_reverse(Solution, ReversedSolution),
	show_triangle(ReversedSolution).

triangle_solver(1, Solution, Solution).
triangle_solver(N, [OldBoard|PastBoards], Solution) :-
	legal_jump(OldBoard, NewBoard),
	M is N-1,
	triangle_solver(M, [NewBoard,OldBoard|PastBoards], Solution).

The predicate they call "fast_reverse/2" is in fact the usual
implementation of reverse/2 using accumulator passing.  It is a pity
that they gave it a name which make it look exceptional, instead of
being the only reverse one ever uses except in the NREV benchmark...
But why bother reversing the list at all?  Why not build it in the
right order from the start?

triangle(N) :-
	make_first_board(N, FirstBoard),
	triangle(14, FirstBoard, Solution),
	show_triangle(Solution).

triangle(1, LastBoard, [LastBoard]).
triangle(N, OldBoard, [OldBoard|FutureBoards]) :-
	legal_jump(OldBoard, NewBoard),
	M is N-1,
	triangle(M, NewBoard, FutureBoards).

The name "show_triangle/1" is unfortunate, as it does nothing of the
sort.  It prints a solution, which is a list of triangles.  A good
name would have been "print_solution/1".  As it is, the command which
*does* print a triangle had to be called "show_board/1".

There are a lot of other things I am unhappy with in the original
code, but I think that's enough for one message.  The basic problem
seems to be that the authors are still thinking in Pascal/C/Lisp terms.
For example, they appear to conceive legal_jump/2 as "finding a legal
jump and constructing a new board" rather than as an entirely static
relation between two boards.  This is an important point.  If you
think of legal_jump/2 as a static relation (not unlike a boolean
matrix), you might think of taking relational products.  For example,
it turns out that there are
	   882 solutions to jump(_,A,B) & jump(_,B,C)
	14,712 solutions to jump(_,A,B) & jump(_,C,D)
Now 882/(36*36) = 0.68+, and 14,712/(36*36*36) = 0.315+, which suggests
another approach to the problem:  we are asking about
	jump*jump*...*jump*jump*jump
and we could well try bracketing it as
	(jump*jump*jump)*...*(jump*jump)
instead.  I don't know whether this is a good idea for this particular
problem or not.  But at least thinking of a relation as something like
a boolean matrix lets me come up with such ideas; somehow one never
thinks of taking products of Pascal procedures...

The book is not bad value, nevertheless.