(If I'm trying not to spoil anything, do I even post? Maybe I can encourage someone else to have fun giving it more thought.) At least one elegant and efficient answer is within reach for many. The person who first pointed it out to me didn't need to know the relevant branch of mathematics to do so; he intuited the shape of it without the formal terminology.
I'll be particularly curious to hear the pattern(s) in how many solutions there are, and/or the probability of a random board being solvable.
The haptic feedback on mobile is really on point in this implementation.
Regarding the number of solvable boards. It is actually possible to calculate the exact number. The solvable boards correspond to the image of the matrix of moves. It will be a vector (sub)space over Z/2Z, so it will always be a power of 2, and its size will be determined by the rank of the matrix. For example for 5x5, there are 2^22 valid boards.
And regarding the number of solutions to a given board, (assuming you ignore the order of moves, because it doesn't matter) it will always be the exact same number, and in the case of 5x5 it will be 2^8. 8 is the nullity of the matrix of moves.
Note that 22+8=30, which is 44+33+22+11, which is the number of possible moves.
Tangentially related, have you heard of Bombe? It's a hexagonal minesweeper where you write rules to solve every possible scenario. It even checks your rules' satisfiability via SMT.
penwielder|3 months ago
I'll be particularly curious to hear the pattern(s) in how many solutions there are, and/or the probability of a random board being solvable.
The haptic feedback on mobile is really on point in this implementation.
bogdanoff_2|3 months ago
Regarding the number of solvable boards. It is actually possible to calculate the exact number. The solvable boards correspond to the image of the matrix of moves. It will be a vector (sub)space over Z/2Z, so it will always be a power of 2, and its size will be determined by the rank of the matrix. For example for 5x5, there are 2^22 valid boards.
And regarding the number of solutions to a given board, (assuming you ignore the order of moves, because it doesn't matter) it will always be the exact same number, and in the case of 5x5 it will be 2^8. 8 is the nullity of the matrix of moves.
Note that 22+8=30, which is 44+33+22+11, which is the number of possible moves.
NatKarmios|3 months ago
bogdanoff_2|3 months ago