Tower of Hanoi pattern for backup
Regular backups are vital to protect ourselves and our data against failures of the
software, the hardware, or even of the users themselves. There is always a conflict
between the need to have frequent backups and the cost of keeping the
media for these backups for a long time. The Tower of Hanoi pattern is a useful
compromise.
Where does the name come from?
The name comes from the children's game where you have three pegs on a piece of board with a pile
of discs on one of them. The object of the game is to move the discs from one peg to another by
moving one disc at a time and always following the rule that you never put a larger disc on top of
a smaller one. The game in turn comes from 19th century myth about an Eastern temple where the
priests were supposed to be engaged in moving 64 gold disks from one diamond needle to another.
They have been doing this day and night since the beginning of time. When they complete
their task the temple will crumble and the universe will end.
What's the connection?
This algorithm is the fastest solution to the Tower of Hanoi game. Just repeat the following two
steps until the entire pile has moved:
 Move the smallest disc clockwise
 Make the only other legal move not involving the smallest disc
These rules generate the following pattern of moves on a tower of three discs labelled
A, B & C:
 Move A
 Move B
 Move A
 Move C
 Move A
 Move B
 Move A
The solution is recursive and can easily be extended. If there were
four discs then you would use the threedisc solution to move the top
three discs off of disc D, move disc D, then use the threedisc
solution again to put the three discs back onto disc D. The threedisc
solution is:
ABACABA
so the fourdisc solution will be
ABACABADABACABA.
It's easy to extend this to any number of discs. For five discs the solution is to use the
fourdisk pattern and clear all four off of the fifth disc, then move the fifth disc and move
the four back on top of it again:
ABACABADABACABAEABACABADABACABA
We can also go the other way. The original threedisc pattern of moves
is made up of an "ABA" pattern which moves two discs off of the largest disc,
"C" so that that largest disc can be moved, and then "ABA" to move the two discs back onto
the largest one. And you can analyse the "ABA" pattern in the same way 
Move "A", then move "B", then move "A" back again.
How does this help with backups?
The fivedisc solution above is a string of 31 characters which
consists of five different letters. You could use it as a schedule to
give you a month of backups by using five tapes labelled "A" to "E".
It won't give you a backup for every day of the month but at the end
of the month you would have a very good spread of data on your five
tapes:
 One day old
 Two days old
 Four days old
 Eight days old
 Sixteen days old
This binary pattern extends very quickly. A sixth tape would be used
every 64 days, a seventh every 128 days, and the eight, ninth and
tenth tapes would come up every 256, 512, and 1024 days. A box of ten
tapes (or CDs or DVDs) would last for nearly three years. We don't bother going that far.
We back up once a week to a box of five DVDs and the fifth DVD only gets used twice a year.
How do I do lay out a schedule?
The easiest way to lay out a month's Tower of Hanoi pattern is to take a grid of days (or weeks)
like this:
 Mark every alternate day as "A"
 Mark every alternate blank day as "B"
 Mark every alternate blank day as "C"
 Mark every alternate blank day as "D"
 Mark every alternate blank day as "E"
01 
02 
03 
04 
05 
06 
07 
08 
09 
10 
11 
12 
13 
14 
15 
16 
A 

A 

A 

A 

A 

A 

A 

A 


B 



B 



B 



B 





C 







C 











D 























E 
Generating the schedule in code
This FoxPro procedure will print the sequence for five disks:
lnNumDisks = 5
lnLen = (2 ^ lnNumDisks)  1
For
lnDay = 1
To
lnLen
For
n = 0
To
lnNumDisks
If Bittest
(lnDay, n)
?n + 1
Exit
Endif
Next
lnPos
Next
lnDay
The code relies on the link between the Tower of Hanoi and the digits
of binary numbers. If you write the binary numbers from 1 to 31 you'll
see that the final digit is '1' on every alternate row. Looking at the
remaining rows you'll see that the penultimate digit is '1' on every
alternate row.
