Crucial Statement of the Hanoi Tower (Prologue)

Question

My professor gave this as an example of Prolog. This is a program that solves the Tower of Hanoi puzzle, where you need to move a stack of discs to another binding, moving one disc after another without placing a larger disc on top of the smaller disc.

Now I do not like this program. I was told that the Prolog is for declarative programming. I do not want to program how to solve the problem, I want to write using Prolog what the problem is. Then let Prolog solve it.

My efforts so far can be found below. There are two types of lists that I use: the sequence of actions is as follows: [[1,2],[3,1]] ; this would be "move the top drive from binding 1 to pin 2, move the drive from binding 3 to peg 1". My second type of list is state for example, if there are three bindings [[1,2,3], [], []] , this means that there are three disks on the first binding. Smaller drives have lower numbers, so the front of the internal list is the top of the stack.

 % A sequence of actions (first argument) is a solution if it leads % from the begin state (second argument) to the End state (third argument). solution([], X, X). solution([[FromIdx | ToIdx] | T], Begin, End) :- moved(FromIdx, ToIdx, Begin, X), solution(T, X, End). % moved is true when Result is the resulting state after moving % a disk from FromIdx to ToIdx starting at 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 works, but it's too slow for anything complicated enough. By asking him to solve the classic Hanoi Tower problem, moving three disks from the first binding to the third and last, will look like this:

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

I would like to make some changes to the program so that it works for this request. How should I do it? When profiling, I see that nth1 uses a lot of time, should I get rid of it? My concern is that moved completely deterministic and should only have one result. How can I speed up this bottleneck?

Answer 1

The Prolog solution for Hanoi usually looks something like this. The solution writes the exits to the screen when it meets them and does not collect the moves in the list:

 move_one(P1, P2) :- format("Move disk from ~k to ~k", [P1, P2]), nl. move(1, P1, P2, _) :- move_one(P1, P2). move(N, P1, P2, P3) :- N > 1, N1 is 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 can be changed to collect the moves in the list instead, adding the list argument everywhere and using append/3 :

 move(0, _, _, _, []). move(N, P1, P2, P3, Moves) :- N > 0, N1 is 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 were able to make the basic example simpler without write . append/3 does the job, but it's a bit awkward. In addition, is/2 , in particular, makes it non-relational.

Using DCG and CLP (FD), append/3 can be eliminated and made more relational. Here I would call the initial "naive" approach, and this is also 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 leads to:

 | ?- 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] ? a 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 is relational, it has several problems:

• Useless selection points in both directions
• Problems with termination, if not limited to something like N in 0..1000

I feel that there is a way around these two questions, but it hasn’t worked yet. (I'm sure if some smarter Prologers than me, like @mat, @false or @repeat, look, they will have a good answer right away.)

Answer 2

I looked at your decision, and here are some thoughts that I had about it:

When you move , what you do is taken from one tower and put on another. There is a SWI-Predicate that replaces the item in the list, select/4 . But you also want to have an index in which you replaced it. so switch_nth1 it a bit and name it switch_nth1 because it no longer needs to do with select .

 % switch_nth1(Element, FromList, Replacement, ToList, Index1) switch_nth1(Elem, [Elem|L], Repl, [Repl|L], 1). switch_nth1(Elem, [A|B], D, [A|E], M) :- switch_nth1(Elem, B, D, E, N), M is N+1. 

Since we are working on a list of lists, we will need two calls to switch_nth1 : one to replace the tower we are taking from, and one to place it on the new tower.

The predicate A move might look like this (sorry, I changed the arguments a bit). (It should be called allowed_move , because it does not make moves that are not allowed).

 move((FromX - ToX), BeginState, NewState):- % take a disk from one tower switch_nth1([Disk| FromTowerRest], BeginState, FromTowerRest, DiskMissing, FromX), % put the disk on another tower. switch_nth1(ToTower, DiskMissing, [Disk|ToTower], NewState, ToX), % there are two ways how the ToTower can look like: (ToTower = []; % it empty ToTower = [DiskBelow | _], % it already has some elements on it. DiskBelow > Disk). 

If you connect this to a solution , you will sadly encounter some problems with completion, since no one said that the state that has already been reached should not be the right step on the way. Thus, we need to track where we have already been and prohibit continuation when a certain state is reached.

 solution(A,B,C):-solution_(A,B,C,[B]). solution_([], X, X,_). solution_([Move | R], BeginState, EndState, KnownStates):- move(Move, BeginState, IntermediateState), \+ memberchk(IntermediateState, KnownStates), % don't go further, we've been here. solution_(R, IntermediateState, EndState, [IntermediateState | KnownStates]). 

However, this solution is still very important - there should be better solutions where you really use recursion .

Answer 3

By “declarative,” I assume that you mean something close to the old slogan “in Prolog,” to write down a question in order to answer it. “Let Prolog find the answer in my place, just by coding in Prolog the answer I have to was to find out by myself.

A simple definition of the legal_move predicate, which indicates the initial and final conditions and the standard search for any variety, leads to an extremely inefficient solution that will completely back off.

Creating a computer for an effective solution here seems to be a very difficult problem for me. For us, however, people, although they think a little that the solution is obvious, also eliminate all redundancy, making all comparisons and checking the validity of positions completely unnecessary - the solution is effective, and every movement is legal in construction.

If we can move N = M + K disks, we can move M of them the same way - the other two pegs are empty, and we pretend that there are no lower K-disks.

But, moving the M-disks, we are faced with the rest of K. Wherever M-disks go, we cannot move any of the K, because by design the K-disks are all “bigger” than any of M (“bigger” simply because they were under them at the beginning at the source binding).

But the third pin is empty. One disk easily moves there. Wouldn't that just be smooth if K were equal? Moving the remaining K = 1 drive to the empty target binding, we can again pretend that it is not (because it is the "largest") and move the M disks on top of it.

An important addition: since M-disks must be transferred to the target in the second phase, initially they must be moved to the spare .

All this means that if we knew how to move M-disks, we could easily move M + 1. Induction, recursion, DONE !

If you already know all this, apologize for downloading the literature. The code:

 hanoi(Disks, Moves):- phrase( hanoi(Disks, [source,target,spare]), Moves). hanoi( Disks, [S,T,R]) --> { append( M, [One], Disks) }, hanoi( M, [S,R,T]), [ moving( One, from(S), to(T)) ], hanoi( M, [R,T,S]). hanoi( [], _) --> [ ]. 

Testing:

4? - hanoi ([1,2,3], _X), maplist (writeln, _X).

moving (1, from (source), to (target))
movement (2, from (source) to (spare))
movement (1, from (target), to (stock))
moving (3, from (source), to (target))
movement (1, from (spare)) to (source))
movement (2, from (spare) to (target))
moving (1, from (source), to (target)) ;
<b> false.