Solve Towers of Hanoi by counting
Added 2016-11-19 01:21:08 +0000 UTCHey fours! See if you can figure out what this represents, and why it works.
Comments
Notice that because 0 moves every other move, the following move is somewhat "forced". This is because when you move 0, you have only two other possible layers to move. Naturally, one layer will be smaller than the other (or the other is empty), so, if we take that into consideration, if we move 0, then the smallest of the two remaining gets moved. As for the movements of 0, notice that if we assign the values of A B C to 0, 1, and 2 respectively that 0 starts on tower 0, then it next moves to tower 1, then 2, then 0 again for each successive movement. This is equivalent to each move being associated with the number of the tower it is currently on x_n plus 1 mod 3 (so, x_n+1 = (x_n + 1) mod 3). More simply, we always move 0 to the right, and cycle back to the first tower at the end. Finally, this only works if we have an even number of layers that we intend to move to tower C. An odd number of layers will move the tower to B. To fix this, we can add and extra hop for 0 at the beginning before continuing with layer 1 and so on.
2016-11-20 21:23:24 +0000 UTCI think it works because piece 0 needs to move every other move, piece 1 every fourth move, piece 2 every eighth move, and so one. Counting in binary tracks that nicely, because the most significant bit to be updated follows the same pattern. (The 0s bit updates every increment, but it's only the most significant bit to update every other time.) I don't see any relationship between the current number or values of bits and where to place the next layer to move, just which one that is.
Max Goldstein
2016-11-20 00:13:15 +0000 UTC
