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 version is available for download here.

My algorithm is based on the following:


Some other things:

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
4x416 (24)
5x54 (22)
9x9256 (28)
11x1164 (26)
14x1416 (24)
16x16256 (28)
17x174 (22)
19x1965,536 (216)
23x2316,384 (214)
24x2416 (24)
29x291,024 (210)
30x301,048,576 (220)
32x321,048,576 (220)
33x3365,536 (216)
34x3416 (24)
35x3564 (26)
39x394,294,967,296 (232)
41x414 (22)
44x4416 (24)
47x471,073,741,824 (230)
49x49256 (28)
50x50256 (28)
53x534 (22)
54x5416 (24)
59x594,194,304 (222)
61x611,099,511,627,776 (240)
62x6216,777,216 (224)
64x64268,435,456 (228)
65x654,398,046,511,104 (242)
67x674,294,967,296 (232)
69x69256 (28)
71x7116,384 (214)
74x7416 (24)
77x774 (22)
79x7918,446,744,073,709,551,616 (264)
83x8364 (26)
84x844,096 (212)
89x891,024 (210)
92x921,048,576 (220)
94x9416 (24)
95x954,611,686,018,427,387,904 (262)
98x981,048,576 (220)
99x9965,536 (216)

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

It appears that:

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