Tower of Hanoi pattern for backup
Regular backups are vital to protect ourselves against failures of the
software, the hardware, or even of the users. There is always a conflict
between the need to have frequent backups and the cost of keeping such
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 start with three pegs on
a piece of board. The object is to move a pile of discs from one peg
to another by moving one disc at a time and never putting a larger
disc on a smaller one. The game in turn comes from 19th century myth
about an Eastern temple where the priests are 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:
 Move the smallest disc clockwise
 Make the only other legal move not involving the smallest disc
It generates the following pattern of moves on a tower of three discs
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 is
ABACABADABACABA.
If there are five discs then the solution is to use this pattern to
move the top four, then move the bottom one, and then move the four
back again:
ABACABADABACABAEABACABADABACABA
We can also go the other way. The original threedisc pattern of moves
is made up of an "ABA" pattern to move two discs off of the largest disc,
"C" to move that largest disc, 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. In practice
we make a full backup every week and use six CDs.
How do I do it in practice?
The easiest way to lay out a month's Tower of Hanoi pattern is 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.
