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