Solving the Tower of Hanoi in Rust.

The Tower of Hanoi is a well-known combinatorial game. If you don’t know it yet, it doesn’t mind! In this post we are going to look at a mathematically defined version and write an algorithm that solves it in Rust.

Some basic knowledge of Rust is required to understand the code. You may find an easy introduction here.

Definition:

Initially, we are given a tuple that holds three tuples. The first of these tuples contains integers from 1 to n in rising order, and the other two are empty:

((1,2,3, ...n), (), ())

We are allowed to remove the first element of any of those tuples and push it as first element to any other tuple, but only if each of these three tuples remain sorted all the time. We are allowed to do these moves arbitrary often and the goal is to move all elements from the first tuple towards the last one. So the final picture should look like:

((), (), (1,2,3, ...n))

Example:

We consider the case of n = 3:

((1,2,3), (), ())
((2,3), (), (1))
((3), (2), (1))
((3), (1,2), ())
((), (1,2), (3))
((1), (2), (3))
((1), (), (2,3))
((), (), (1,2,3))

Existence of a solution:

Before writing an algorithm for a problem of this sort, it is wise to first proof that there exists a solution always. Of course, some problems in practice turn out to be so complex that not even this task is feasible.

We proof by induction on n the following assertion:

The initial setup of the form

((1,2,...,n, a...), b, c)

where a,b and c contain integers all being greater than n, can be transformed by using only the permitted moves to any of the following:

(a, (1,2,...,n, b...), c)
(a, b, (1,2,...,n, c...))

The same applies for any re-ordering of the outer tuple.

This states that we are able to move the ordered tuple (1,2, …, n) onto the top of any other…