From: "Guy Haworth" <g.haworth@reading.ac.uk> [asked about numbering states]
From: Dan Asimov <dasimov@earthlink.net> what is an algorithm for using the fewest moves [between two states]?
From: "Andy Latto" <andy.latto@pobox.com> [proof that all states are connected, by induction adding the smallest disk to a solution for the others]
From: "Fred lunnon" <fred.lunnon@gmail.com> [obvious base-3 numbering, optimized base-2 numbering based on the standard solution]
Call the biggest disk 1, the next smallest 2, etc. The state diagram for one disk is a triangle: 1.. .1. ..1 The state diagram for n+1 disks replaces each vertex in the diagram for n disks with a triangle. For instance, for two disks: 21 . . 1 2 . 1 . 2 | \ . 2 1 . 1 2 . . 21 2.1 -- 2 1 . . 21 . Notice that the position of disk 2 is rotated in each of the three sub-triangles. This is like a Gray code, which you can construct from binary by exoring each bit with all the previous bits. So, each state can be assigned an (x,y) by going from the biggest to smallest disk (maybe a right rather than an equilateral triangle?). Also pretty easy to find the three (or two) states reachable from here and their (x,y) positions. Here's an algorithm for finding one of the shortest paths from where you are to target state T: while you're not at T: move to (one of) the reachable state(s) closest (in space) to T Pretty easy to encode the x and y numbers within a single base-three number if you like. You can also just skip the (x,y), let each digit stand for one of three directions, and choose the best move based on the most-significant different digit between the reachable positions. Giving the states (x,y) positions shows ties sometimes, and breaks what are really ties other times, You might say Gray code is a simplified Towers of Hanoi problem. --Steve -- My apples and oranges are beyond compare!