dcg - Solving Tower of Hanoi declaratively (Prolog) -

my professor gave this example of prolog. program solves tower of hanoi puzzle, have move stack of disks peg moving 1 disk after other, without putting bigger disk on top of smaller disk.

now, don't program. told prolog meant declarative programming. don't want program how solve problem, want write down using prolog problem is. let prolog solve it.

my effort far can found below. there 2 types of lists employ, sequence of actions represented this: [[1,2],[3,1]]; "move top disk peg 1 peg 2, move disk peg 3 peg 1". second type of list state, example, if there 3 pegs [[1,2,3], [], []] mean there 3 disks on first peg. smaller disks have smaller numbers, front of inner list top of stack.

% sequence of actions (first argument) solution if leads % begin state (second argument) end state (third argument).  solution([], x, x).  solution([[fromidx | toidx] | t], begin, end) :-     moved(fromidx, toidx, begin, x),     solution(t, x, end).  % moved true when result resulting state after moving % disk fromidx toidx starting @ state start  moved(fromidx, toidx, start, result) :-      allowedmove(fromidx, toidx, start),     nth1(fromidx, start, [disk|otherdisks]),     nth1(toidx, start, tostack),     nth1(fromidx, result, otherdisks),     nth1(toidx, result, [disk|tostack]).  allowedmove(fromidx, toidx, state) :-      number(fromidx), number(toidx),     nth1(fromidx, state, [fromdisk|_]),     nth1(toidx, state, [todisk|_]),     todisk > fromdisk.  allowedmove(_, toidx, state) :- nth1(toidx, state, []). 

the above program seems work, slow reasonably complex. asking solve classic tower of hanoi problem, moving 3 disks first peg third , last, go this:

?- solution(seq, [[1,2,3], [], []], [[], [], [1,2,3]]). 

i make modifications program works query. how go doing that? when profiling can see nth1 uses lot of time, should rid of it? bothers me moved deterministic , should have 1 result. how can speed bottleneck?

the prolog solution hanoi 1 typically finds looks this. solution writes moves out screen encounters them , doesn't collect moves in list:

move_one(p1, p2) :-     format("move disk ~k ~k", [p1, p2]), nl.  move(1, p1, p2, _) :-     move_one(p1, p2). move(n, p1, p2, p3) :-     n > 1,     n1 n - 1,     move(n1, p1, p3, p2),     move(1, p1, p2, p3),     move(n1, p3, p2, p1).  hanoi(n) :-     move(n, left, center, right). 

this modified collect moves in list instead adding list argument throughout , using append/3:

move(0, _, _, _, []). move(n, p1, p2, p3, moves) :-     n > 0,     n1 n - 1,     move(n1, p1, p3, p2, m1),     append(m1, [p1-to-p2], m2),     move(n1, p3, p2, p1, m3),     append(m2, m3, moves).  hanoi(n, moves) :-     move(n, left, center, right, moves). 

we able make base case simpler without write. append/3 job, it's bit clunky. also, is/2 in particular makes non-relational.

by using dcg , clp(fd), append/3 can eliminated , can made more relational. here's i'd call initial "naive" approach, , more readable:

hanoi_dcg(n, moves) :-     n in 0..1000,     phrase(move(n, left, center, right), moves).  move(0, _, _, _) --> []. move(n, p1, p2, p3) -->     { n #> 0, n #= n1 + 1 },     move(n1, p1, p3, p2),     [p1-to-p2],     move(n1, p3, p2, p1). 

this results in:

| ?- hanoi_dcg(3, moves).  moves = [left-to-center,left-to-right,center-to-right,left-to-center,right-to-left,right-to-center,left-to-center] ?  no | ?- hanoi_dcg(n,  [left-to-center,left-to-right,center-to-right,left-to-center,right-to-left,right-to-center,left-to-center]).  n = 3 ? ;  (205 ms) no | ?- 

although it's relational, have couple of issues:

• useless choice points in "both directions"
• termination issues unless constrained n in 0..1000

i sense there's way around these 2 issues, haven't worked out yet. (i'm sure if smarter prologers i, such @mat, @false, or @repeat see this, they'll have answer right off.)