My version is available for download here.

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 (2^{4}) |

5x5 | 4 (2^{2}) |

9x9 | 256 (2^{8}) |

11x11 | 64 (2^{6}) |

14x14 | 16 (2^{4}) |

16x16 | 256 (2^{8}) |

17x17 | 4 (2^{2}) |

19x19 | 65,536 (2^{16}) |

23x23 | 16,384 (2^{14}) |

24x24 | 16 (2^{4}) |

29x29 | 1,024 (2^{10}) |

30x30 | 1,048,576 (2^{20}) |

32x32 | 1,048,576 (2^{20}) |

33x33 | 65,536 (2^{16}) |

34x34 | 16 (2^{4}) |

35x35 | 64 (2^{6}) |

39x39 | 4,294,967,296 (2^{32}) |

41x41 | 4 (2^{2}) |

44x44 | 16 (2^{4}) |

47x47 | 1,073,741,824 (2^{30}) |

49x49 | 256 (2^{8}) |

50x50 | 256 (2^{8}) |

53x53 | 4 (2^{2}) |

54x54 | 16 (2^{4}) |

59x59 | 4,194,304 (2^{22}) |

61x61 | 1,099,511,627,776 (2^{40}) |

62x62 | 16,777,216 (2^{24}) |

64x64 | 268,435,456 (2^{28}) |

65x65 | 4,398,046,511,104 (2^{42}) |

67x67 | 4,294,967,296 (2^{32}) |

69x69 | 256 (2^{8}) |

71x71 | 16,384 (2^{14}) |

74x74 | 16 (2^{4}) |

77x77 | 4 (2^{2}) |

79x79 | 18,446,744,073,709,551,616 (2^{64}) |

83x83 | 64 (2^{6}) |

84x84 | 4,096 (2^{12}) |

89x89 | 1,024 (2^{10}) |

92x92 | 1,048,576 (2^{20}) |

94x94 | 16 (2^{4}) |

95x95 | 4,611,686,018,427,387,904 (2^{62}) |

98x98 | 1,048,576 (2^{20}) |

99x99 | 65,536 (2^{16}) |

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

It appears that:

- there are always
*2*solutions for some^{n}*n*. - there is only one solution for each
*2*x^{n}-1*2*board.^{n}-1

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