The Tower of Hanoi can be played using paper and pen only. The following is a solution of the game with 6 disks represented by the numbers 1,2,3,4,5,6 where disk i is smaller than disk i+1, i=1,2,3,4,5. The poles are represented by the letters A, B, C.
Explanation : In step (01), disk 1 is transferred from pole A to pole B.
(00) (123456,,)
(01) (23456,1,) (AB)
(02) (3456,1,2) (AC)
(03) (3456,,12) (BC)
(04) (456,3,12) (AB)
(05) (1456,3,2) (CA)
(06) (1456,23,) (CB)
(07) (456,123,) (AB)
(08) (56,123,4) (AC)
(09) (56,23,14) (BC)
(10) (256,3,14) (BA)
(11) (1256,3,4) (CA)
(12) (1256,,34) (BC)
(13) (256,1,34) (AB)
(14) (56,1,234) (AC)
(15) (56,,1234) (BC)
(16) (6,5,1234) (AB)
(17) (16,5,234) (CA)
(18) (16,25,34) (CB)
(19) (6,125,34) (AB)
(20) (36,125,4) (CA)
(21) (36,25,14) (BC)
(22) (236,5,14) (BA)
(23) (1236,5,4) (CA)
(24) (1236,45,) (CB)
(25) (236,145,) (AB)
(26) (36,145,2) (AC)
(27) (36,45,12) (BC)
(28) (6,345,12) (AB)
(29) (16,345,2) (CA)
(30) (16,2345,) (CB)
(31) (6,12345,) (AB)
(32) (,12345,6) (AC)
(33) (,2345,16) (BC)
(34) (2,345,16) (BA)
(35) (12,345,6) (CA)
(36) (12,45,36) (BC)
(37) (2,145,36) (AB)
(38) (,145,236) (AC)
(39) (,45,1236) (BC)
(40) (4,5,1236) (BA)
(41) (14,5,236) (CA)
(42) (14,25,36) (CB)
(43) (4,125,36) (AB)
(44) (34,125,6) (CA)
(45) (34,25,16) (BC)
(46) (234,5,16) (BA)
(47) (1234,5,6) (CA)
(48) (1234,,56) (BC)
(49) (234,1,56) (AB)
(50) (34,1,256) (AC)
(51) (34,,1256) (BC)
(52) (4,3,1256) (AB)
(53) (14,3,256) (CA)
(54) (14,23,56) (CB)
(55) (4,123,56) (AB)
(56) (,123,456) (AC)
(57) (,23,1456) (BC)
(58) (2,3,1456) (BA)
(59) (12,3,456) (CA)
(60) (12,,3456) (BC)
(61) (2,1,3456) (AB)
(62) (,1,23456) (AC)
(63) (,,123456) (BC)
The number of steps required to solve the game of Tower of Hanoi of n disks is 2^n-1 where n is the number of disks.
In the example above, note that the number of steps taken = 63 = 2^6-1.
Strategy : When transferring the disks, make sure that the numbers representing the adjacent disks differ by an odd number.
Friday, May 20, 2011
Friday, May 13, 2011
Subscribe to:
Posts (Atom)