8 ms·
For every boards are two chessboard patterns we can solve for. For example, for a 3x3 board we can have: 101 010 010 or 101 101 010 wh
by alxv 10y ago
For every boards are two chessboard patterns we can solve for. For example, for a 3x3 board we can have:
101 010
010 or 101
101 010
where 1 is a white square and 0 is a black square.
We can represent any N×N board as a N² vector. So, we can represent one of the chessboard pattern as:
010
101 = 010101010 = y
010
At the beginning of the game, the board is at some random initial pattern.
110
111 = 110111010 = y0
010
The goal of the game is to find the necessary moves to form the chessboard pattern. Hence, we want to solve the equation
(y - y0) = Mx
where M is a N²×N² matrix representing the effect of every possible moves. Pressing on a tile is equation to addition by 1 modulo 2.
1 + 1 = 0 (mod 2)
0 + 1 = 1 (mod 2)
For example, pressing the top left tile is the same as adding this effect vector to the board vector:
110110000
If we do this for all 9 tiles of the 3x3 board, we find the matrix M to be:
110110000
111111000
011011000
110110110
111111111 = M
011011011
000110110
000111111
000011011
where the i-th row is the effect of pressing the i-th tile. Now, we can just solve for x (assuming M is not singular). Re-using our above example, we find
(y - y0) = Mx
(010101010 - 110111010) = Mx
100010000 = Mx
111100100 = x (by Gaussian elimination)
This means we can press the following tiles (in any order) on the board to solve it:
111
100
100
If you are interested, I wrote some quick demo code that shows how this could be implemented in Python: https://gist.github.com/avassalotti/7452318c9e9b8dec637bc7c0fac32951 https://gist.github.com/avassalotti/7452318c9e9b8dec637bc7c0...
- tgb 10y agoThis is a very nice exposition of the strategy, but I still don't see how it answers my more specific question, about whether you can solve the problem row by row (is the grid).
- alxv 10y agoSorry, it turns that was misunderstanding from my part. It turns out we cannot solve a board row by row without revisiting the previous rows. The board below is a counterexample: 101 010 100 The first and second rows are solved. However we cannot solve the last row without re-doing the first and second rows. The two solutions of this board shows this: solution #1: 110 100 000 solution #2: 110 110 000 Actually, seeing my mistake made me challenge my assumption that a singular matrix over the reals might not be over integers modulo 2. This is likely wrong too. I don't know much about abstract algebra (and I am not a mathematician). Wikipedia (https://en.wikipedia.org/wiki/Determinant#Square_matrices_over_commutative_rings_and_abstract_properties https://en.wikipedia.org/wiki/Determinant#Square_matrices_ov...) states "the reduction modulo m of the determinant of such a matrix is equal to the determinant of the matrix reduced modulo m." The move matrix M for all boards of size 3n + 2 appears to be singular. This means these boards may have no solution or a large number of solutions.
- tgb 10y agoGotcha, thanks. FYI, a singular matrix taking values in {0,1} that is singular over R if and only if it is also singular over Z/2, for exactly the reason you provide, that the determinant commutes with modding by 2.