View source for Tower of Hanoi (Dynamic Programming)

From wiki.visual-prolog.com
You do not have permission to edit this page, for the following reasons:
The action you have requested is limited to users in the group: emailconfirmed.
You must confirm your email address before editing pages. Please set and validate your email address through your user preferences.
You can view and copy the source of this page.
I am not sure what you can use this for, you can take it as "fun" (if you find that kind of things "fun"), trivia and/or some kind of inspiration.

I assume you know the [[wikipedia:Tower of Hanoi|Tower of Hanoi]] puzzle.

It takes 2^N-1 moves to solve the puzzle (optimally) when there are N discs.

I also assume that you know how to solve it using a normal recursive function/predicate, otherwise you can see a solution here [[wikipedia:Visual Prolog|Visual Prolog]].

Somewhere on the Internet I came across the argument since it will take 2^N-1 operations to write out the solution, you cannot solve the problem in less.

At first I completely agreed on that argument, it seems so obvious. And it is of course correct if solving the puzzle means actally moving the discs, or writing out each of the moves in sequence.

But what if we just mean finding and representing the solution in a computer as a "simple" data structure.

This little algorithm (complete program below):
<vip>
domains
    pole = a; b; c.
    solution =
        done;
        compound(solution SourceToTemp, pole Source, pole Destination, solution TempToDestination).

class facts
    memoization : mapM{tuple{unsigned Size, pole Source, pole Temp, pole Destination}, solution} := mapM_redBlack::new().

class predicates
    hanoi : (unsigned Size, pole Source, pole Temp, pole Destination) -> solution S.
clauses
    hanoi(Size, Source, Temp, Destination) =
        memoization:get_defaultLazy(tuple(Size, Source, Temp, Destination),
            {  =
                if Size = 0 then
                    done
                else
                    compound(hanoi(Size - 1, Source, Destination, Temp), Source, Destination, hanoi(Size - 1, Temp, Source, Destination))
                end if
            }).
</vip>
Solves the problem using [[wikipedia:Dynamic Programming|dynamic programming]]/[[wikipedia:Memoization|memoization]].

The structure of the solution is "special" for the way we intend to solve the problem, so that we avoid "concatenating" moves. So instead of creating a sequence of moves we create a tree containing the moves:

* <vp>done</vp> : don't do anything (disks are in the place they need to be).
* <vp>compound</vp> :
** First perform <vp>SourceToTemp</vp>
** then move Source to <vp>Destination</vp>
** and then perform <vp>TempToDestination</vp>

The basic idea of the algorithm is the one from the usual recursive solution.  However with the little difference that we memoize (it is spelled without an 'r' but it still means "remember") all results it the <vp>memoization</vp> map.

I.e. when/if we calculate <vp>hanoi(3, b, c, a)</vp> then we will insert the solution in the memorization map (using the key <vp>tuple(3, b, c, a)</vp>).

Should we later need that solution again (which we do; trust me) then instead of recalculating it we will retrieve the result from the map.

(You will notice that <vp>get_defaultLazy</vp> handles such memorization quite easily.)

The predicate above solves the problem for 10.000 discs in 0.2 seconds on my computer.  Given the 2^N-1 formula the solution contains ≈2e+3010 moves.

Clearly it is impossible to write all the steps. But the solution '''''is''''' in the created tree, and using "ordinary" tree algorithms it is for example (in less than 10.000 tree operations) possible to retrieve a certain step (except that Visual Prolog does not have arithmetic that covers numbers as large as 2e+3010).

Notice that it is only possible to create the solution tree because subtrees are reused/shared.  Without going too deep into complexity calculations, there are 6  permutations of tree poles, so the <vp>memoization</vp> map will contain (at most) (N +1) * 6 trees.  Each of these trees will either be <vp>done</vp> or a <vp>compound</vp> term whose children will be some of the other trees in the map, so the entire tree consist of less than 60006 nodes.  I.e. there are O(N) nodes, the algorithm have these stored in a  red-black-tree which will use O(N * log(N)) memory, so the calculation requires O(N * log(N) memory, but the result only requires O(N) memory (we can throw away the map after the calculation).

With nearly the same argumentation we can conclude that the algorithm will run in O(N * Log(N)): We need to create the O(N) nodes each of them are created by simple operations where the most complex ones are the look-up/insert into the red-black-tree which have O(log(N)) complexity.


Here is the entire program, which also write-out the solutions for N = 1, 2, 3 and 4 (so that we can convince ourselves that the trees are indeed correct):

<vip>
implement main
    open core, std, stdio

domains
    pole = a; b; c.
    solution =
        done;
        compound(solution SourceToTemp, pole Source, pole Destination, solution TemoToDestination).

class facts
    memoization : mapM{tuple{unsigned Size, pole Source, pole Temp, pole Destination}, solution} := mapM_redBlack::new().

class predicates
    hanoi : (unsigned Size, pole Source, pole Temp, pole Destination) -> solution S.
clauses
    hanoi(Size, Source, Temp, Destination) =
        memoization:get_defaultLazy(tuple(Size, Source, Temp, Destination),
            {  =
                if Size = 0 then
                    done
                else
                    compound(hanoi(Size - 1, Source, Destination, Temp), Source, Destination, hanoi(Size - 1, Temp, Source, Destination))
                end if
            }).

class predicates
    writeSolution : (solution Solution).
clauses
    writeSolution(done).
    writeSolution(compound(First, Source, Destination, Last)) :-
        writeSolution(First),
        writef("    % -> %\n", Source, Destination),
        writeSolution(Last).

class predicates
    profileSolve : (unsigned N).
clauses
    profileSolve(N) :-
        T1 = time::now(),
        _ = hanoi(N, a, b, c),
        T2 = time::now(),
        D = duration::new(T1, T2),
        writef("Tower of hanoi size % in %p\n", N, D).

clauses
    run() :-
        foreach I = std::fromTo(1, 4) do
            writef("Moving % discs from % to % using % as temporary\n", I, a, b, c),
            writeSolution(hanoi(I, a, b, c)),
            nl
        end foreach,
        profileSolve(64),
        profileSolve(1000),
        profileSolve(10000).

end implement main

goal
    console::runUtf8(main::run).
</vip>

[[Category:Examples]]
Return to Tower of Hanoi (Dynamic Programming).
Retrieved from "https://wiki.visual-prolog.com/index.php?title=Tower_of_Hanoi_(Dynamic_Programming)"
View source for Tower of Hanoi (Dynamic Programming)

Search

Navigation

external links

collaboration

Personal tools

Views
