I've started doing the puzzle-solving algorithm optimizations that I outlined in the previous post. I started with the one expected to give the best performance improvements, i.e. what I called "limiting the size of the search space with domain knowledge".
Quite quickly after starting to think about possible optimizations I realized the puzzle has some interesting characteristics due to the shape of the board and how all its starting points are considered equal. As the board is a square and the same moving rules apply wherever one starts the game, it follows that any valid solution from a particular cell means there are three "identical" solutions in other quadrants of the board also.
These can be found simply by rotating the solution on the board 90, 180 and 270 degrees. Actually, if the starting cell isn't on either of the diagonal axes, one can also mirror the solution in relation to the diagonal axis running through the quadrant the cell is in, and that solution can be rotated to three new solutions also. This means that any solution found proves there are four or even eight solutions to the puzzle.
This means that one only needs to find solutions from a rather small subset of board cells, and then just mirror and rotate the found solutions to deduce all the solutions the board has. For a 10×10 grid, only 15 cells of 100 need to be handled separately, and some of those only partly. These unique starting point cells are shown in the image below. An example starting point for which solutions are found is marked in the image with S.
As shown, only about one half of a board quadrant needs to be checked. And when starting from a cell on the diagonal axis of the board, only 5 of the possible 8 first moves – in directions NW, N, NE, E, SE – need to be considered, as the other directions can be handled as mirror images of these. E.g. if the player starts in the cell (2,2) and first moves right (E), and eventually finds a solution, this means that a mirrored solution exists that starts from the same cell and takes a first move down (S).
I changed my algorithm so that it starts deducing these other solutions by first mirroring the ones found diagonally. This is enough to cover one quadrant of the board as starting cells. This is shown in the image below. All solutions starting from the example starting point S are now mirrored as solutions starting from S'.
After all possible solutions for this one quadrant are now known, it's really straightforward to find all solutions for the other quadrants by rotating the solutions 90, 180 and 270 degrees. (The algorithm actually does this by first rotating the original quadrant 90 degrees, then rotating the result of that operation 90 degrees, and once again using the result of that operation and rotating it 90 degrees. But this is just an implementation detail.) The example starting point and its mirror equivalent are shown rotated to each of the other board quadrants.
After this all the existing solutions for the whole board are known.
Considering different board sizes
This same logic works for different sizes of the board but there are some small adjustments needed for boards of an odd size, e.g. a 5×5 board. The percentage of unique starting cells needed from all board cells is a bit higher as the middle horizontal and vertical axes go through a column and a row of cells, and the cells on those need to be included. The unique starting cells for a 5×5 board are shown below.
The mirroring logic is exactly the same as it is for an even-sized board. However, the result naturally covers more than a quadrant of the board because of the shape.
Due to this difference, rotating the solutions works a bit differently. Only part of the first set of solutions is rotated to avoid duplicating solutions.
For a 5×5 board, only two rows of the 3-row first quadrant are rotated to avoid doubling the solutions in the middle column. These same solutions can be rotated again to the next quadrant to get more solutions. But in the last rotation the solution set must be made smaller again, to a 2×2 group of starting cells, to avoid duplication solutions on the middle row.
The results
This rather simple optimization makes the search space significantly smaller. As mentioned above, on a full 10×10 board, only 15% of the starting cells need to be used to search for solutions, and some of those only partly. This shows also in the running time of the application.
As I wrote in the previous post, a test run with a 6×6 board took 25 minutes and 59 seconds with the naive implementation. With this improved version all solutions were found in 3 minutes and 44 seconds. Using the actual millisecond values returned by the algorithm's own timers, this optimization shaved off 85.65% of the original duration.
I'm not finished with the algorithm yet, but I'd say it's a decent start.
