## Back From The Klondike

Back From The Klondike might be the first ever jump maze. It was created by the Victorian puzzle compiler Sam Loyd. Loyd allegedly designed this puzzle so that it could not be solved by a rule discovered by mathematician Leonhard Euler for solving mazes. With a modern computer it is possible to create a set of rules for generating similar puzzles for which there is exactly one solution. A Java applet containing the original puzzle is immediately below. Below that is a tutorial on how to generate similar puzzles followed by a Java applet implementing these rules.

Due to a typing error there are actually two solutions to Loyd's puzzle. This link contains a description of the typo, how it could have been corrected, as well as a solution to the puzzle.

### Rules

The original description published by Sam Loyd in the New York Journal and Advertiser, 24 April, 1898 is as follows:

Start from the heart in the center. Go three steps in a straight line in any one of the eight directions, north, south, east, west, northeast, northwest, southeast, or southwest. When you have gone three steps in a straight line you will reach a square with a number on it, which indicates the second day's journey, as many steps as it tells, in a straight line in any one of the eight directions. From this new point, march on again according to the number indicated, and continue on in this manner until you come upon a square with a number which will carry you just one step beyond the border, thus solving the puzzle.

### Java Source Code

BackFromTheKlondikeApplet.javaThis applet was created using Eclipse.

### Generating puzzles with exactly one solution

A starting location must be chosen. To be consistent with Loyd's puzzle we will always use the centre square.

We will randomly pick a finishing square. This could be any of the green squares on original puzzle above. To pick one will create a list of the co-ordinates of all of the green squares. We will then pick a random numer between zero and the number of green squares minus one and retrieve the square in this list with this random number as its index. Since there are 60 green squares we will pick a random number between zero and 59.

We will then work backwards from the finishing square picking squares to form the solution. The highest number in any of the squares in Loyd's puzzle is nine. If we are going to have this as one of the rules in the design of our maze then the square that leads to the finish must be nine or fewer squares from it. Furthermore, the distance between this square and the finish can not be the same as the distance between the square and any other green squares if there is only to be a single solution. There are eight possible directions, so 8 x 9 = 72 squares need to be evaluated against thes criteria. Since this is a small number a brute force approach will not be too expensive. Once we have picked this square we will then assign it a value of the number of squares from it to the finish.

We will then pick a series of other squares which provide a path from this one back to the start.