Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Chessboardify – Make the grid a chessboard

chessboardifygame.xyz

Post reply on HN
Print view View original

31–37 of 37 posts

Re: Show HN: Chessboardify – Make the grid a chessboard

#31

Post by Diggsey »

BariumBlue wrote: post #28

Got an excel solver for the 3x3 I'd share i'd via google spreadsheet if I could do it anonymously without creating a throwaway account (All this in 3x3 grids, with the numbers mod 2) - 1. Add the current light up state to the desired light state (chessboard) - 2. Create a grid that's lit up as if from button presses from previous grid (using the game rules) - 3. Flip the positions of the previous grid across the cent…

I just created a solver for the 4x4 case, also in google sheets... Who would have though it could handle ~15,000 rows with decent performance!

Works by calculating via formulae the result of any sequence, 6 moves or less. The bit patterns of each individual move are XORed together for each possible combination of moves.

The difference between the current state and the target is calculated, again via XOR, and then looked up in this data sheet via the query functionality, to give the sequence of moves which resulted in that delta bit pattern.

Re: Show HN: Chessboardify – Make the grid a chessboard

#32

Post by alxv »

tgb wrote: post #23
alxv wrote: post #18

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.

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…

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/7452318c9e9b8dec637bc7c0...

Re: Show HN: Chessboardify – Make the grid a chessboard

#33

Post by tgb »

alxv wrote: post #32
tgb wrote: post #23

Earlier quoted context omitted.

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…

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…

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).

Re: Show HN: Chessboardify – Make the grid a chessboard

#35

Post by mapehe »

Grue3 wrote: post #30

Is it me, or bigger boards are much easier than 3x3? You can pretty much build those row by row.

I think it really depends on the size. Often the 5x5 feels like a breeze, but then 6x6 is a lot tougher. Probably there is some mathematical reason for this related to the divisibility of the grid side length.

Re: Show HN: Chessboardify – Make the grid a chessboard

#36

Post by alxv »

tgb wrote: post #33
alxv wrote: post #32

Earlier quoted context omitted.

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…

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).

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_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.

Re: Show HN: Chessboardify – Make the grid a chessboard

#37

Post by tgb »

alxv wrote: post #36
tgb wrote: post #33

Earlier quoted context omitted.

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).

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…

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.

Post reply on HN