Tower of Hanoi (Dynamic Programming) - Revision history

Thomas Linder Puls: formatting

2021-07-21T15:06:19Z

formatting

← Older revision		Revision as of 17:06, 21 July 2021
Line 89:		Line 89:
	done		done
	else		else
	compound(hanoi(Size - 1, Source, Destination, Temp), Source, Destination, hanoi(Size - 1, Temp, Source, Destination))		compound(hanoi(Size - 1, Source, Destination, Temp), Source, Destination,
			hanoi(Size - 1, Temp, Source, Destination))
	end if		end if
	}).		}).

Thomas Linder Puls: formatting

2021-07-21T15:05:42Z

formatting

← Older revision		Revision as of 17:05, 21 July 2021
Line 33:		Line 33:
	done		done
	else		else
	compound(hanoi(Size - 1, Source, Destination, Temp), Source, Destination, hanoi(Size - 1, Temp, Source, Destination))		compound(hanoi(Size - 1, Source, Destination, Temp), Source, Destination,
			hanoi(Size - 1, Temp, Source, Destination))
	end if		end if
	}).		}).

Thomas Linder Puls: token color

2018-10-19T14:55:36Z

token color

← Older revision		Revision as of 16:55, 19 October 2018
Line 45:		Line 45:
	* <vp>compound</vp> :		* <vp>compound</vp> :
	** First perform <vp>SourceToTemp</vp>		** First perform <vp>SourceToTemp</vp>
	** then move Source to <vp>Destination</vp>		** then move <vp>Source</vp> to <vp>Destination</vp>
	** and then perform <vp>TempToDestination</vp>		** and then perform <vp>TempToDestination</vp>

Thomas Linder Puls: review

2017-10-27T09:03:44Z

review

← Older revision		Revision as of 11:03, 27 October 2017
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 ~~since~~ it will take 2^N-1 operations to write out the solution, you cannot solve the problem in less.		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.		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]].
			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 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.		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 ~~(which we do; trust me)~~ then instead of recalculating it we will retrieve the result from the map.		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 ~~memorization~~ quite easily.)		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 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~~.		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):

Thomas Linder Puls: initial

2017-10-27T08:53:44Z

initial

New 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]]