Number puzzle solver
There is a number puzzle (game, if you will) where one has an empty 10x10 grid in which one has to enter all the numbers from 1 to 100. The idea is to fill the grid by starting with number 1, then entering number 2, and so on, always using the number that indicates the "round". The cells in which the current number can be entered are very limited, though.
One can start filling the grid (with "1") from any cell. However, after this the following number can only be entered in a cell that is three (3) cells away from the last entered number's position in the four main directions (up, right, down, left) or two (2) cells away in any diagonal direction. One cannot move outside of the grid or enter a number in any cell that already has a number.
A progress of one simple puzzle game is demonstrated in the images below. The first picture shows the situation after the first move. The number "1" is inserted near the middle of the grid, and all of the eight possible directions to advance are available.
The second picture shows the situation after the second move. The chosen direction was northeast, so the number "2" was inserted two cells away from the previous cell diagonally. Now only five of the possible directions are available; the three choices going straight or diagonally up are not available because the move would be out of the grid bounds, and going southwest is an invalid move because that cell is already filled.
The third picture shows the situation after eight moves (the game could still be continued to six different directions). The moves that got the game to this state are (after inserting the number "1" in a freely chosen cell): NE, S, S, W, W, N, SE.
As I was unable to find a solution to the puzzle on paper, I decided to write a program that would find a valid solution. Since the search space is rather big, I chose to use a genetic algorithm in the search.
My first attempt was using chromosomes of a random starting point and 99 random moves (chosen with equal probabilities from {N, NE, E, SE, S, SW, W, NW}). I tried this with a few different combinations of the initial and total population size and mutation probability. The chromosomes to survive each round were selected with roulette wheel selection. The breeding used one point crossover, and mutation changed one of the moves randomly to some other value. The rounds of the algorithm were limited to 100 000 (or a solution being found). The fitness of each chromosome was determined by the number of moves it went on without failing. When a move clashed with an existing value in the target cell or went out of bounds, it was deemed a failure.
This approach proved to be inadequate. It never found a complete solution, and only produced move combinations reaching 80 to 90 valid moves at best. My colleagues at work had already reached 98 or 99 with pen and paper, so the solutions my program found were in no way giving us extra information.
However, I then made a small but rather significant change to the chromosome structure. Instead of having a list of 99 moves, they now have a list of 99 permutations of all eight possible moves. When determining the fitness of each chromosome, the list is used as in the earlier implementation (taking the first move from the permuted list of possible moves), but when a move fails, the next move from the permuted list is tried. If that allows the game to continue, that one is chosen.
So, let's for example consider a chromosome with the first three moves being the following permutations of possible moves: (N, E, SW, SE, W, NE, S, NW) - (S, W, NE, N, SE, E, SW, NW) - (NE, SW, N, E, SE, W, NW, S) - ...
Now, if the starting point was (randomly) chosen not too near of the top border of the grid, the first possible move ("N") of the first permutation set ("N, E, SW, SE, W, NE, S, NW") is valid, and so that is used. The permutation set of the second move now offers "S" as the next move. However, that is an invalid move, since it would take us back to the previous cell and thus clashes with the previous entered number. So, the next possible move from the set ("W") is tried, and if that doesn't fail, it is chosen as the second move and the search proceeds to the third permutation set to select the third move, and so on. Only if none of the eight moves in the permutation succeed, this candidate solution has reached its final potential and is deemed a failure (in finding a complete solution).
This was the only change made to the algorithm. It now finds a reasonably good candidates (95+ steps) very soon and can also find a complete solution (of which there seem to be many) to the problem in the 100 000 rounds that it runs before quitting. If a result is found, it is printed. The current best result is also shown every 100 rounds, so that the progress of the algorithm can be monitored.
The source code can be found here.
Note: I used EasyMock when writing the tests, and the corresponding .jar file (and the license file, of course) is also included here for your convenience. It is not needed to run the actual program, only with the tests.