Solving Towers of Hanoi and Related Puzzles

摘要

Starting with the well-known Towers of Hanoi, we create a new sequence of puzzles which can essentially be solved in the same way. Since graphs and puzzles are intimately connected, we define a sequence of graphs, the iterated complete graphs, for our puzzles. To create puzzles for all these graphs, we need to generalize another puzzle, Spin-Out, and cross the generalized Towers puzzles with the the generalized Spin-Out puzzles. We show how to solve these combined puzzles. We also show how to compute distances between puzzle configurations. We show that our graphs have Hamiltonian paths and perfect one-error-correcting codes. (Properties that are NP-complete for general graphs.) We also discuss computational complexity and show that many properties of our graphs and puzzles can be calculated by finite state machines.