Take a square grid of size $a\times b$, with all squares being off. You can tap a square, to reverse the state of that square and all squares located in the same column and row as the tapped square. Your goal is to turn on all the squares.
What's the minimal amount of moves required to solve a given grid?
Can there be a general strategy to optimally solve any given grid?
Let $a,b\gt1$, since the grid is solved in one move otherwise.
Solution in $a\times b$ moves
If $a+b$ is even, then we can solve the grid by tapping each square exactly once, in any order; this works since each square gets triggered odd amount of times which means it will be turned on.
Solution in $a$ or $b$ moves
If $a$ is odd, we can solve a grid by tapping each square in a single row.
If $b$ is odd, we can solve a grid by tapping each square in a single column.
$5\times5$ solution example:
I believe the second solution is optimal when one of $a,b$ is odd, and that the first solution is optimal when both are even.
But I'm not sure if the first solution is optimal?
Can we solve a $2n\times2m$ grid in less than $4nm$ moves? (why not?)
Secondly; we can reach a checkerboard state in grids where $a,b$ are even by tapping each square in every second diagonal (either left or right diagonals only).
$4\times4$ example:
Can we reach a checkerboard state in any other grids? (why not?)
Answer
Here is a more straightforward proof than the one given by ffao, plus information about checkerboard patterns
This game is a version of Lights Out. Like all these games, they have the following properties:
The order of moves does not matter. If you look at the effect of a move sequence on a single square, all that matters to that square is how often it is toggled. It does not matter to that square what order the moves are performed, as all the moves that affect it will affect it in the same way.
Each square need not be tapped more than once. If you were to tap a square more than once during a solution, you can reorder the moves to make those two taps consecutive. But tapping a square twice has no net effect, so such repeated moves can be skipped.
This means that there are only $2^{a*b}$ possible move sequences that need to be considered - each square can either be tapped or not by the move sequence.
Boards with only even dimensions
Consider now an ideal situation in which it is possible by some sequence of taps to change the state of just a single square without affecting the rest.
By rearranging the rows and columns of that sequence of taps, any single square can be changed. Therefore every state combination can be achieved from the all-off state.
In this ideal situation, all $2^{a*b}$ state patterns can be achieved. Since there are only $2^{a*b}$ move sequences, every combination of states has a unique solution.
For $a\times b$ boards with both $a$ and $b$ even, we are in this ideal situation, because tapping a square together with all the squares in the same row or column changes only that single square (it toggles $a+b-1$ times, the column $a$ times, the row $b$ times, the rest $2$ times).
We know that tapping every square will change the all-off state to all-on (everything toggles $a+b-1$ times) and from the above we know that this is the unique solution so $a*b$ moves are necessary.
This also means that a checkerboard pattern is always possible, and that when you have found a solution, the solution will be unique. It is easy to see that tapping out a checkerboard pattern will create a checkerboard state pattern (untapped squares toggle $(a+b)/2$ times, tapped square $(a+b)/2-1$ times), so a total of $a*b/2$ taps are always needed.
Boards with odd dimensions
If $a$ is odd, then we are not in this ideal situation. This is easy to see because pressing the squares a single row toggles everything. So we can get from all-off to all-on by pressing either the first row, or the second row, etc. This pattern clearly does not have a unique solution.
This can allow for shorter solutions to those patterns that can be achieved. Because tapping all the squares of any two rows will have no effect on the state, any move sequence that uses more than $a$ taps on a pair of rows can be shortened - just exchange the tapped squares for the untapped ones on those rows.
Unfortunately it is not possible to create a checkerboard pattern starting from the all-off state. If you look at two rows of the board, every possible move changes the state of an even number of squares in those two rows. If you start from an all-off state, there will always be an even number of squares off and an even number on on those two rows. For a checkerboard pattern we want exactly $a$ of the squares on, which is therefore not possible.
Of course the same results hold if $b$ is odd, or if both $a$ and $b$ are odd.
No comments:
Post a Comment