Toads And Frogs Puzzle in 2D

Here's a 2-dimensional variant of the Toads and Frogs puzzle. The rules are virtually identical. Frogs only move rightward or downward, toads can only move leftward and upward. A piece can jump over another piece of a different kind, provided the square on which it lands is empty. The goal of the puzzle of course is to cause frogs and toads to swap their positions.

(Click on a piece you wish to move.)

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

Buy this applet
What if applet does not run?

Solution

References

W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, Dover, 1987

The puzzle is solved by the following observation. The middle vertical column may be looked at as a simple 1-dimensional puzzle. In the course of a successful solution of that puzzle, the empty square will eventually move over all squares in that column. (This is because all pieces will have to be moved from their original positions.) The row in which the empty square is located may be looked at as another 1-dimensional puzzle, this time horizontal. The process of solution of the vertical puzzle serves as an index into a sequence of horizontal puzzles that are solved successively.

40617997