Here you can play and see the state graph at the same time. That makes the journey much easier and safer. In the If the boat is empty, the vertex of the state graph corresponding to the present state is surrounded by a green circle. the target state is always surrounded by a yellow circle. A state with encoding (x0,x1, x2, ..., xn) will be represented by the number x1 * 2n-1 + x2 * 2n-2+ ...+ xn-1*2 + xn. Since the graph is bipartite, we don't need x0--- it follows from the surrounding. Conversely, you can find the encoding (except x0) by taking the binary representation of the number shown in the state graph.
Note that you can modify the drawing of the state graph. Click close to a vertex, the vertex will be colred red. Then click on the white area where you want this vertex to be. The applet uses part of a Java program called GO I wrote during a DFG project for dealing with graph operators.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Erich Prisner, 2002-2004