Explorations in 4-Peg
Tower of Hanoi
A distributed Tower of Hanoi solver
This distributed solution is theoretically scalable to any number of computers - allowing one to postpone the point at which memory problems overwhelm the solver.
We estimate that, given a dozen computers with at least 1 GB of RAM each, one could figure out up to ToH(4,22) in a week or so of processing time. As a proof of concept, we implemented a prototype distributed solver, which can run on 3 machines at once. (For decent speed it requires at least 100Mbit Ethernet, and preferably gigabit Ethernet.)
Algorithm for Three Machines
Given three machines, we assign each one a distinct role: an Sn-1 client, an Sn client and an Sn+1 client.
The operation of the cluster is as follows:
Startup The Sn client will be initially seeded with the starting state. Both the Sn-1 and the Sn+1 clients will have their stores empty.
Step 1 The Sn client generates all the adjacent states to the states in its store and sends those new states to the Sn-1 client. The Sn-1 client compares all the states it receives from the Sn client against its store and only sends the ones that are not present in its store to the Sn+1 client. The Sn+1 client adds the states it receives from the Sn-1 client to its store if the states are not already present.
Step 2 After
the Sn client has send all adjacent states to the Sn-1
client, the Sn-1 client has sent its last state to
the Sn+1 client and the Sn+1
client has processed the final state from Sn-1, the
clients will rename themselves using the following mapping: Sn+1
→ Sn, Sn
→ Sn-1, Sn-1
For more information please see: