Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!mailrus!tut.cis.ohio-state.edu!bloom-beacon!mit-eddie!uw-beaver!ubc-vision!ubc-cs!voda From: voda@ubc-cs (Paul Voda) Newsgroups: comp.lang.prolog Subject: Re: Triangle Puzzle Message-ID: <1863@ubc-cs.UUCP> Date: 29 Feb 88 21:32:42 GMT References: <652@cresswell.quintus.UUCP> Sender: nobody@ubc-cs.UUCP Reply-To: voda@ubc-cs.UUCP (Paul Voda) Organization: UBC Department of Computer Science, Vancouver, B.C., Canada Lines: 229 Keywords: Modifiable Variables, State Transition, TRILOGY. This contribution was inspired by the recent discussion of the Triangle Puzzle by Richard O'Keefe. A wide class of problems, the triangle puzzle is one of them (see below), calls for a natural solution in the form of a sequence of complex data structures describing the successive states of the problem being solved by a series of steps. The general situation is as follows: Problem(initparams,Solution) <- Initialstate(initparams,State), Path(params,State,Solution). Path(params,State,[]) <- Endstate(params,State). Path(params,Oldstate,[onestep,Tail]) <- Onestep(params,Oldstate,Newstate), Path(params,Newstate,Tail). Basically we deal with a class of graph traversal problems. The adjacent nodes are described by the predicate "Onestep". The states of the problem are usually described by complex lists which are copied over and over with only slight changes. A state for the triangle puzzle was given by a description of the board giving the empty and occupied holes. The declarative languages (Prolog and Lisp) are clearly at disadvantage for two reasons: i) the new state must be obtained from the old one by creating a fresh copy of the old state. ii) A state must be described by a complicated list even if the problem naturally calls for arrays. The solution of such a problem in a procedural language will modify the state data structure in place. Clever Prolog programmers have discovered long ago that certain degree of in-place-modification can be obtained directly in Prolog by the employment of the "var" predicate. There is only one list describing a state. The list consists initially of unbound variables. As the solution progresses the unbound variables are bound to values describing the new states. If a part of the state, usually denoting a "not visited" situation, is found unbound by a call to the "var" predicate, the part can be marked by a value signifying the "visited" situation. This technique applies only to such problems (maze traversal, tiling problems, constraint satisfaction problems, etc.) where the state changes exactly once for each of its parts. I will mention here two examples, both of which appeared in the Prolog digest: T. Evans's solution of the Cube Packing Problem and the Baage's solution of the Christmas Puzzle. During the solution of the Triangle Puzzle a hole in the board changes the state from occupied to empty and back many times. This means that "var" cannot be used. I would like to stress here that a logically clean solution of the Cube packing and Christmas puzzles logically calls for the encoding of the situation by the old state/new state technique. Needless to say this would be terribly inefficient. The reduction of the declarative Prolog to the procedural Pascal by the use of "var" seems to be a lesser evil questioned only by the purists. The majority of Prolog programmers grew up with the procedural languages and they simply do not care about the logic. Ironically, quite often one hears the same programmers to praise the declarative style "of specifying only what and not how" just as they specify the "how" by the use of "var" and "assert". Is it possible to have both the cake and eat it? The answer is yes if one allows modifiable variables in a declarative setting. A natural, and logically elegant, solution is to have the language processor recognize the copying situation: the old state will never be used after the new state has been obtained. The processor can reuse the storage in such a case. There is a large amount of research going on in this direction. The problem is a difficult one with no acceptable solution in sight. Alternatively, and admittedly as a slightly less elegant solution, one can employ the declarative reading of procedural programs as proposed by Rick Hehner and Tony Hoare. (See for instance the two 84 CACM papers on the "Predicative Programming" by Hehner). Certain arguments can be designated as being 'input/output'. They will be modified in place whereas logically they are a pair of arguments: one 'input' and one 'output'. For instance the following predicate Incr(x) iff x := x + 1 Is only an abbreviation for the predicate Incr(x_in,x_out) iff x_out = x_in + 1. The formula x := 6 & Incr(x) & Incr(x) & P(x) is only an abreviation for the formula x1 = 6 & Incr(x1,x2) & Incr(x2,x3) & P(x3) Of course, only a madman would employ this style of programming with short values such as integers, but with the list-typed arguments the technique is certainly faster than copying and it is logically cleaner than the use of the "var" predicate. An implementation of reassignable variables calls for the specification of modes for the arguments. I have employed this in the programming language Trilogy. The arguments of Trilogy have four modes: 'input' (x:T) where the argument x obtains a full value before the predicate call is exited, 'input/output' (x:.T) which is logically a pair of variables, and finally the 'symbolic' or 'logical' mode (x::T) where x is specified by constraints (of which "no constraint" yields the "unbound" variable). Following is the implementation of the Triangle Puzzle in Trilogy. I briefly explain the constructs employed after the text of the program. { TRIANGLE PUZZLE IN TRILOGY } { Triangle Puzzle: A triangle-shaped board has 15 holes numbered 0 to 14. There is a peg in each hole. Remove arbitrary peg and perform 13 jumps by jumping with a peg over another peg into a hole and removing the peg jumped over. At the end there will be only one peg on the board. 0 1 2 3 4 5 the query: 6 7 8 9 one Triangle(0,p) 10 11 12 13 14 finds a solution starting with the hole 0 empty } Hole = [0..14] {Interval type describing the holes} {Array type describing a state of the board:} Board = Hole->I { b(i) is 0 if i-th hole empty; 1 if there is a peg} {Constant array of lists describing the legal jumps} { "(o,t) in Jumprom(f)" holds if it is possible to jump from the hole f over the hole o to the hole t} Jumpfrom :< Hole->list (I,I) = [ ((1,3),(2,5),Nil), {from 0} ((3,6),(4,8),Nil), {from 1} ((4,7),(5,9),Nil), {from 2} ((1,0),(4,5),(7,12),(6,10),Nil), {from 3} ((7,11),(8,13),Nil), {from 4} ((2,0),(4,3),(8,12),(9,14),Nil), {from 5} ((3,1),(7,8),Nil), {from 6} ((4,2),(8,9),Nil), {from 7} ((7,6),(4,1),Nil), {from 8} ((8,7),(5,2),Nil), {from 9} ((6,3),(11,12),Nil), {from 10} ((7,4),(12,13),Nil), {from 11} ((11,10),(7,3),(8,5),(13,14),Nil), {from 12} ((12,11),(8,4),Nil), {from 13} ((13,12),(9,5),Nil) ] {from 14} pred Triangle(h:list(I,I,I)) iff { h is the starting hole and p solves the puzzle by giving a list of 13 triples of the form (from,over,to) } b:.Board & b := [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] & {all pegs in} b(h) := 0 & {the starting hole is removed} Jumps(13,b,p) {13 jumps are performed yielding p} pred Jumps(i:list (I,I,I)) iff { i jumps given by p from the board in state b_in lead to b_out} if i > 0 then {there are jumps to be performed} b(from) = 1 & {from is a hole with a peg in it} (over,to) in Jumpfrom(from) & {over,to is a jump from the hole from} b(over) = 1 & b(to) = 0 & {the hole over contains a peg, to is empty} b(from) := 0 & b(over) := 0 & b(to) := 1 & {new situation on the board} Jumps(i-1,b,t) & {t solves the puzzle from the board pos b} p = (from,over,to),t {thus p is a solution for i-jumps} else {no jumps to be performed} p = Nil end Explanation: i) The variables of Trilogy start with small letters. Predicates, types and constants, being identified by proper names, are capitalized. ii) "Hole" and "Board" are type declarations. Hole is an interval type whereas the type Board = Hole->I is an array (finite mapping) of integer values indexed by the holes. iii) The constant array "Jumpfrom" of the type "Hole->list (I,I)" can be visualized as a set of indexed Prolog facts describing the possible jumps. The formula (over,to) in Jumpfrom(from) used in the predicate "Jumps" is to be read as follows: The array subscription "Jumpfrom(from)" denotes the list of possible jumps from the hole "from". Each element of the list is a pair "(over,to)" giving the jumped over and the destination holes. "in" is the infix list membership relation primitive in Trilogy. Thus the formula holds iff it is possible to jump from the hole "from" over the hole "over" to the hole "to". iv) A state of the board is described by the 'input/output' array "b:.Board", where "b(i) = 1" if the i-th hole contains a peg, "b(i) = 0" otherwise. v) A solution to the puzzle is found by the query one Triangle(0,p) which constructs the path "p" describing the solution of the puzzle as a list. The input argument "0" indicates that initially the hole zero is empty. The first solution is found on an 8MHz AT in 0.8 seconds as follows: p = (3,1,0),(5,4,3),(0,2,5),(6,3,1),(9,5,2),(11,7,4),(12,8,5), (1,4,8),(2,5,9),(14,9,5),(5,8,12),(13,12,11),(10,11,12),Nil vi) The predicate "Jumps" has an input/output argument "b" describing the states. It has the following declarative reading: Jumps(i,(b_in,b_out),p) holds iff the board b_out is obtained from the board b_in by performing i jumps given by the list p. The procedural reading is that given the number i and the state b the predicate will return the path p. vii) The reader will note that the arrays of Trilogy allow fast indexing as opposed to the list traversal of Prolog.