3 ms·

Like Lights Out, this game can be solved using Gaussian elimination over Z/2 (integers modulo 2). This means the order of the tiles you press do not matter, and

by alxv 10y ago

Like Lights Out, this game can be solved using Gaussian elimination over Z/2 (integers modulo 2). This means the order of the tiles you press do not matter, and that you can solve the board by forming the desired pattern row by row.

memonkey 10y ago
This is interesting but I don't really understand because I've tried doing what you're saying. Maybe a side note: I'm very interested in learning algorithms but they are so inaccessible to me.
- tgb 10y ago
  Have you taken linear algebra? It gives a structure for solving systems of linear equations and the parent post is noting that the game state is a linear function of which squares you've pressed, when considering the states of a square as either one or zero and doing arithmetic mod 2. So the standard techniques of linear algebra can solve this system, such as Gaussian elimination. However, you still have to write down the large matrix that encodes what each square does (an n x n board will need an n^2 x n^2 matrix which shows how each square affects all the others once pressed). Then you solve that system. For this particular game there is probably a more intuitive way to directly solve it.
tgb 10y ago
Sorry how does it follow that you can form the pattern row by row? When you write this down as a linear algebra problem you kinda forget about the structure of the board, and the rows of the resulting matrix you apply Gauss elimination to don't correspond to the rows of the game board. So you must have meant something else that I'm missing, but I'm confused how you would solve just the bottom row without touching any others.
- 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 ago
    This 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 ago
      Sorry, 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 ago
        Gotcha, 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.

by alxv 10y ago

memonkey 10y ago

This is interesting but I don't really understand because I've tried doing what you're saying. Maybe a side note: I'm very interested in learning algorithms but they are so inaccessible to me.

tgb 10y ago
Have you taken linear algebra? It gives a structure for solving systems of linear equations and the parent post is noting that the game state is a linear function of which squares you've pressed, when considering the states of a square as either one or zero and doing arithmetic mod 2. So the standard techniques of linear algebra can solve this system, such as Gaussian elimination. However, you still have to write down the large matrix that encodes what each square does (an n x n board will need an n^2 x n^2 matrix which shows how each square affects all the others once pressed). Then you solve that system. For this particular game there is probably a more intuitive way to directly solve it.

tgb 10y ago

Sorry how does it follow that you can form the pattern row by row? When you write this down as a linear algebra problem you kinda forget about the structure of the board, and the rows of the resulting matrix you apply Gauss elimination to don't correspond to the rows of the game board. So you must have meant something else that I'm missing, but I'm confused how you would solve just the bottom row without touching any others.

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 ago
  This 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 ago
    Sorry, 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 ago
      Gotcha, 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.