# Difference between revisions of "Tower of Hanoi (Dynamic Programming)"

(initial) |
(review) |
||

Line 7: | Line 7: | ||

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]]. | 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 | + | 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 | + | 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. | But what if we just mean finding and representing the solution in a computer as a "simple" data structure. | ||

Line 37: | Line 37: | ||

}). | }). | ||

</vip> | </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: | 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: | ||

Line 47: | Line 48: | ||

** and then perform <vp>TempToDestination</vp> | ** and then perform <vp>TempToDestination</vp> | ||

− | The basic idea of the algorithm is | + | 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 <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>). | 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 | + | Should we later need that solution again then instead of recalculating it, we will retrieve the result from the map. |

− | + | You will notice that <vp>get_defaultLazy</vp> 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. | 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 | + | 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 <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 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): | 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): |

## Revision as of 10:03, 27 October 2017

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**

- First perform

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