Path: utzoo!utgpu!water!watmath!clyde!rutgers!sri-spam!sri-unix!quintus!ok From: ok@quintus.UUCP (Richard A. O'Keefe) Newsgroups: comp.lang.prolog Subject: Triangle Puzzle Keywords: representation, tutorial Message-ID: <652@cresswell.quintus.UUCP> Date: 15 Feb 88 07:55:12 GMT Organization: Quintus Computer Systems, Mountain View, CA Lines: 186 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.