# 5x5 Puzzle

I have modified Dave Pearson's 5x5.el to include a faster deterministic cracking algorithm after becoming frustrated with the existing cracking algorithms. I'm yet to see any of the existing algorithms manage to crack the 5x5 case before Emacs crashed. Even in the 3x3 case the best cracking routing appears to be the 'random' one.

My algorithm is based on the following:

• the order in which moves are made is irrelevant

• repeated moves cancel each other out

• the choice of which moves to make on the top row completely determines the success or failure of the attempt, as the 2nd row is confined by having to finish the top row, the 3rd row is confined by having to finish the 2nd row, and so on

• each move on the top row has a specific and discoverable effect on the eventual state of the bottom row

• considering each square on the bottom row in turn can generate an equation which relates the moves made to the top row

• solving the resulting set of simultaneous equations gives the possible values for the top row

Some other things:

• game.c : C source code for a 5x5 game.

• game.exe : MSDOS executable of the above.

• solve.c : C source code for a (slow) 5x5 solver (will be updated to much faster version soon).

• solve.exe : MSDOS executable of the above.

I am afraid that I wrote the new 'crack-quickly()' function pretty much as a stand-alone function. It's a single operation - give it a size and it gives you a 'solution' grid back, suitable for passing to 5x5-play-solution(). It's not an iterative cracker like all of the existing ones are - there's not really anything to see when it runs, either.

I am quite interested to learn more about how the game works. For example, there is only one solution for most sizes of grids (there is a unique solution for sizes 1, 2, 3, 6, 7, 8, 10, 12, 13, 15, 18 and 20), whereas some have considerably more solutions:

 size # solutions 4x4 16 (24) 5x5 4 (22) 9x9 256 (28) 11x11 64 (26) 14x14 16 (24) 16x16 256 (28) 17x17 4 (22) 19x19 65,536 (216) 23x23 16,384 (214) 24x24 16 (24) 29x29 1,024 (210) 30x30 1,048,576 (220) 32x32 1,048,576 (220) 33x33 65,536 (216) 34x34 16 (24) 35x35 64 (26) 39x39 4,294,967,296 (232) 41x41 4 (22) 44x44 16 (24) 47x47 1,073,741,824 (230) 49x49 256 (28) 50x50 256 (28) 53x53 4 (22) 54x54 16 (24) 59x59 4,194,304 (222) 61x61 1,099,511,627,776 (240) 62x62 16,777,216 (224) 64x64 268,435,456 (228) 65x65 4,398,046,511,104 (242) 67x67 4,294,967,296 (232) 69x69 256 (28) 71x71 16,384 (214) 74x74 16 (24) 77x77 4 (22) 79x79 18,446,744,073,709,551,616 (264) 83x83 64 (26) 84x84 4,096 (212) 89x89 1,024 (210) 92x92 1,048,576 (220) 94x94 16 (24) 95x95 4,611,686,018,427,387,904 (262) 98x98 1,048,576 (220) 99x99 65,536 (216)

I'm curious whether there's a pattern there.

It appears that:

• there are always 2n solutions for some n.

• there is only one solution for each 2n-1x2n-1 board.

Here's the (only) solution to 20x20. Click on each square shown as a #:

```    +--------------------+
|#.#..##########..#.#|
|.#...#........#...#.|
|#.##.##......##.##.#|
|..###.#.####.#.###..|
|...##.###..###.##...|
|###..#...##...#..###|
|#.###.#.####.#.###.#|
|#...#..######..#...#|
|#..##.########.##..#|
|#..#.##########.#..#|
|#..#.##########.#..#|
|#..##.########.##..#|
|#...#..######..#...#|
|#.###.#.####.#.###.#|
|###..#...##...#..###|
|...##.###..###.##...|
|..###.#.####.#.###..|
|#.##.##......##.##.#|
|.#...#........#...#.|
|#.#..##########..#.#|
+--------------------+
```

As you can see, it's perfectly symmetrical.

This is the only solution of the 63x63 puzzle, coloured in an unpleasant manner:

To understand my algorithm a little better, try this in 5x5:

Start with a clear board. 'click' the top left square, and the square immediately to its left. That gives us a 'winning' top line.

Move down to the second line, and only click on the 2nd line until the top line is complete (basically, just click directly underneath each 'hole' on the top line).

Move down to the 3rd line, and only click on the 3rd line until the 2nd line is complete.

Continue like this, and you will solve 5x5, without having made any decisions about where to click since the first line - so the first line completely determines whether or not you will 'win'.

There are 4 winning top lines for 5x5, as follows (# is 'click', '.' is don't):

```    "##..."    "...##"    ".##.#"    "#.##."
```

all 4 give the same solution, just rotated:

```    +-----+    +-----+    +-----+    +-----+
|##...|    |...##|    |.##.#|    |#.##.|
|##.##|    |##.##|    |.###.|    |.###.|
|..###|    |###..|    |..###|    |###..|
|.###.|    |.###.|    |##.##|    |##.##|
|.##.#|    |#.##.|    |##...|    |...##|
+-----+    +-----+    +-----+    +-----+
```

In the 4x4 puzzle, there are 16 different ways to pick the first row. All 16 of these lead to a solution. I think this is only true of the 4x4 puzzle.

In the 9x9 puzzle, there are 512 ways to pick the first row. Of these exactly half lead to a solution. Which half? Apparently it's the half which have an even number of hashes in the odd-numbered positions of the first row. Count the number of hashes in positions 1, 3, 5, 7 and 9. If it's even, you've got a solution, regardless of whether you put hashes in the even positions.

Chris Moore -- chris(dot)moore(at)mail(dot)com -- Friday the 13th of July, 2001