Tower of Hanoi (Dynamic Programming)

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 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 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 actually 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):

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
            }).

solves the problem using dynamic programming/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:

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

The basic idea of the algorithm is that of 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 memoization map.

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

Should we later need that solution again then instead of recalculating it, we will retrieve the result from the map.

You will notice that get_defaultLazy handles such memoization 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 there; 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 memoization map will contain (at most) (N +1) * 6 trees. Each of these trees will either be done or a compound 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 memoization 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. So all in all O(N * log(N)).

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):

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).