Homework: Towers of Hanoi

This puzzle was popularised in Europe by French mathematician Edouard Lucas. There are three poles, 64 disks of different sizes and number of monks trying to move those disks from first to third pole, respecting the following rules:
1) You can move only one disk at the time.
2) You can pick only top disk and place it on top of other disks on different pole.
3) You can place disk only on bigger disk.
When monks finish moving those 64 disks and puzzle is solved, end of the world will come. According to Lucas all that takes place in Vietnam. Now, this puzzle is known in India as Towers of Brahma and there could be other versions of it, for example Chinese, over last seven thousands years they invented many puzzles. One may be under impression that end of the world is near but to solve 64 disk puzzle, 2^64-1 moves are required and that is quite big number 18446744073709551615. Though end of the world may come before puzzle is solved for many other reasons.
Puzzle is quite interesting because it allows to develop simple algorithm. Now we will name poles start, aux and end. With single disk, we take it from start and place on end. With two disks, we take small to aux, big to end and finally smal from aux to end. Now with three disks we already see that we should move top two to aux, big disk to end and after that top two to end. So, moving top two to aux is like previous case, but aux and end are swapping places. Moving top two from aux to end is again the same as previous case, but start and aux are swapping places. We can even write moves, so it is easy to see what is going on:

One disk: start to end
Two disks: start to aux, start to end, aux to end
Three disks: (start to end, start to aux, end to aux), start to end, (aux to start, aux to end, start to end)

We can generalize and say that solution is moving n-1 disks to aux, moving bottom disk to end and moving n-1 disks from aux to end. So we got self algorithm for solving puzzle. Turning it into code is more than simple:

def towers(n, start, aux, end): if n>1 : towers(n-1, start, end, aux) print 'moving disk {} from {} to {}'.format( n, start, end ) towers(n-1, aux, start, end) elif n==1 : print 'moving disk {} from {} to {}'.format( n, start, end )

That was Python implementation. If you do not know Python, here is Java implementation:

public class Towers { public static void main(String[] args) { towers(5,1,2,3); } static void towers(int n, int start, int aux, int end){ if(n>1){ towers(n-1, start, end, aux); System.out.println("moving disk "+n+" from "+start+" to "+end); towers(n-1, aux, start, end); }else System.out.println("moving disk "+n+" from "+start+" to "+end); } }

Very simple. There are many other ways to solve this puzzle but recursion is simplest and most logical. Also excellent interview question, if candidate is not capable of developing simple algorithm and understanding recursion, then candidate is not really programmer.