I used Wave Function Collapse to solve minesweeper. Here is how I approached it
What if we have this puzzle?
? ? ? ? ?
? 1 2 1 ?
? ? ? ? ?
Can we correctly make this progress?
? ? ? ? ? . ? . ? .
? 1 2 1 ? ==> . 1 2 1 .
? ? ? ? ? . ? . ? .
First calculate all the valid possibilities
. b . b . . . . . . . b . . . . . . b .
. 1 2 1 . . 1 2 1 . . 1 2 1 . . 1 2 1 .
. . . . . . b . b . . . . b . . b . . .
There are common areas that are always safe
Encode BOMB(b) = 1 , SAFE(.) = 2 , UNKNOWN(?) = BOMB | SAFE
For each possibility you just boolean ‘OR’ the
corresponding squares together and you get
. ? . ? .
. 1 2 1 .
. ? . ? .
Only modify the unknown squares.
This is expandable up to any size board but it grows
exponentially in runtime with size. Instead use a
smaller size, such as 3x3, 4x4, 5x5 and sample parts
of a larger board. When sampling part of a board
only use the non-perimeter squares for constraining
possibilities.
? . ? . . .
? 1 3 => . 1 3
. b ? . b .
For this 3x3 patch, the “3” is on the perimeter
and so it is not part of the constraints.
Similarly, the 3 does not help the 2 reduce
any unknowns because we lack information about
what is to the right of the 3.
? . ? ? . ?
? 2 3 => ? 2 3
. b ? . b ?
This follows a concept call Wave Function Collapse that you can also find here Coding Games and Programming Challenges to Code Better
405 non blank lines of code, 245 of it is the solver, 160 of it is unit tests