7
$\begingroup$

A counter flip game is played in the following way:

  • In each move, you can flip an entire row or column
  • Flipping a row or column inverts all the counters on that row or column from $X$ to $O$ or vice versa

For example,

\begin{gather*} XOX\\OXO\\XOX \end{gather*} can be converted to \begin{gather*} OOO\\OOO\\OOO \end{gather*} by three moves:

  1. Flip first row: \begin{gather*} OXO\\OXO\\XOX \end{gather*}
  2. Flip third row: \begin{gather*} OXO\\OXO\\OXO \end{gather*}
  3. Flip middle column: \begin{gather*} OOO\\OOO\\OOO \end{gather*}

If you start with \begin{gather*} OOO\\XOX\\OOO, \end{gather*} prove whether or not it is possible to finish with: \begin{gather*} XOO\\OXX\\OOX \end{gather*}

Improve this question
$\endgroup$

6 Answers 6

Reset to default
13
$\begingroup$

Consider only the first two cells of the top row and the first two of the bottom row. Every move that changes them flips exactly two. They start off all O, so after every move 0, 2, or 4 of them will be an O. The goal has three O's so is not possible.

Edit: Now that I have a bit more time, and my answer is already the accepted one, I'll add a short summary of the theory of this type of game which most of the other answers have touched on.

  • This is a variant of the Lights Out game.
  • There are 9 lights, which can be on (O) or off (X).
  • There are 6 moves available - flipping any column or any row.
  • Applying any move twice is the same as doing nothing.
  • You can switch the order the moves, and they still have the same effect.

These last two facts mean that you will have to apply any move at most once, since if you did it more often you can rearrange the moves so that the repeated moves happen successively, after which pairs of them cancel leaving at most one of each.

In this particular puzzle, there are $2^9$ potential states that the 9 lights can have.

The 6 moves are not independent: Flipping all three rows is the same as flipping all three columns. Therefore, we need never use one of the six moves. For example, instead of flipping the first row, you could instead flip all the columns and the other two rows.

That leaves only 5 types of move to play with. Therefore there can only ever be $2^5$ states that we can reach with these moves (as each is applied at most once in any order).

With these 5 available moves we can set the first row and column to any state we like. Use the three column moves to set the states of the first row, and then moves on the bottom two rows to set the rest of the first column. The state of the other four lights cannot be changed independently of the top row and left column.

Consider any of the following sets of four lights:

  x x .    x . x    x x .    x . x
  x x .    x . x    . . .    . . .
  . . .    . . .    x x .    x . x

Every move toggles exactly two of the lights (or none at all). Therefore, the number of lights that are on (of the four you are looking at) can only change by an even number by any move, or by any sequence of moves. If your starting position has an even number of the four lights on, then so will the end position. If it is odd at the start, then it's odd at the end. From this you can deduce what the state of the bottom-right 2x2 square of lights will have to be after you have set the top row and left column to the states you want.

There is a large amount of mathematical literature on the subject of Lights Out games. It can be solved and analysed using Linear Algebra. You can find an explanation of those techniques on my web page here.

Improve this answer
$\endgroup$
4
$\begingroup$

I'll show how solve this puzzle in general. First some things to notice

Firstly, the order of moves doesn't matter. Same moves in different order gives the same result. Secondly, Doing the same move twice reverses it back again.
Combined this means that there are two states for each row/column, flipped or not flipped.

From any stating position we can at most reach $2^6$ = 64 positions. (Actually only half of that, since the opposite set of moves gives the same result.)
there are $2^9$ = 512 different positions, so we cannot reach them all.

To show whether a specific puzzle is solvable

First we look at which positions have to be (D)ifferent, and which has to stay the (S)ame. If they have to stay the same, we have to flip both its column and row, or none.

Image an S, and we decide to flip it's row and column. Any other S in the same row (or column) would need to have it column (or row) flipped as well. The same applies if you decide to not flip any.

An example

The example in terms of S and D is
\begin{gather*}DSD\\SDS\\DSD\end{gather*}
The top-middle and bottom-middle share share a row/column, and the left-center and right-center share a row column. This means top, bottom, and middle(vertical) has to be the same move. Also left, right, and center(horizontal), is the same.
This reduces the possible moves from 6 down to 2 and $2^2$ = 4 different combination of moves, which is trivial (Again, opposite moves gives the same result so we can only reach 2 states, our start and end position).

the Actual puzzle

In terms of S and D
\begin{gather*}DSS\\DDS\\SSD\end{gather*}
The bottom-left share a row/column with bottom-middle, which shares with top-middle, which shares with top-right, which shares with right-center. This covers every row and column.
To make these cells all stay the same, we have to flip everything or nothing. Neither of those moves will solve the puzzle, and it's therefore not possible.

Improve this answer
$\endgroup$
2
$\begingroup$

No, it's not possible. Consider the upper right four square corner of the puzzle.

OO   ->   OO
OX   ->    XX

In order to make this transformation we would need to flip the row or column containing the lower left O, say we swap the bottom row.

OO
XO

Now we need to swap the lower right O back to an X, but if we make the same move as before we will have accomplished nothing, so the only option for that is to swap the right column.

OX
XX

Now we need to swap back the top right X, only way to do that is to swap the top row. Then we would need to swap back the top left X but the only move that wouldn't undo a move we made previously would reset the puzzle back to its original configuration. The same thing happens if you start by swapping the left column.
Since this subset of the puzzle isn't solvable it's impossible to solve the entire puzzle.

Improve this answer
$\endgroup$
2
$\begingroup$

I am posting a generalized way to do this. It's similar to one of Simon Tatham's puzzle, which I worked on long time ago.

enter image description here

A few things to note:

Taking O as 0, and X as 1, you can easily understand that (I am defining switch as [a,..,f], which does O<->X change) taking a switch changes the row/coloumn's stuff +1 mod 2, i.e P -> P+1 mod 2.

And

The order of switches doesn't matters.

Your problem may be rewritten as changing: \begin{gather*} OOO\\OOO\\OOO \end{gather*} to \begin{gather*} XOO\\XXO\\OOX \end{gather*}

Now, because of TO #2, the total possible reachable endstates are (number of ways of taking any/few/all of a,b,c)*(number of ways of taking any/few/all of d,e,f) = $2^{3+3}$ = $2^{6}$ = $64$

And the all possible endstates are

$2^9$ = $512$

(I am busy now, so I will write the remaining answer later)

Improve this answer
$\endgroup$
2
  • $\begingroup$ note $r_1r_2r_3=c_1c_2c_3$, so there at most 62 possible endstates $\endgroup$
    – JMP
    Mar 15, 2017 at 15:10
  • $\begingroup$ @JonMarkPerry: You mean 32 possible endstates. The six moves are linearly dependent, so you can eliminate one of them. The other 5 are linearly independent, so they give rise to $2^5=32$ reachable endstates out of the $2^9=512$ states. $\endgroup$
    – Jaap Scherphuis
    Mar 15, 2017 at 15:32
0
$\begingroup$

The six XOR operations are $r_1, r_2, r_3, c_1, c_2$ and $c_3$. We have $o_i^2=I$, or $o_i=o_i^{-1}$. This means that as $r_1r_2r_3c_1c_2c_3=I$, then for example $c_3$ is linearly dependant, and so $c_3=r_1r_2r_3c_1c_2$. This means that there are only effectively $5$ operations, and so $2^5=32$ possible combinations from an equivalence class, and so $\frac{512}{32}=16$ equivalence classes. We can enumerate the possible moves using the combinations of $r1_,r_2,r_3$ and $c_1, c_2$.

The equivalence classes are formed from any combination of a row and a column, plus the 'parity square' left behind, which has been shown to be parity dependant (see Jaap Scherphuis' answer). There are $32$ variations of row/column bit patterns, reducible by a factor of $4$ by using the corresponding row/column operations, to leave $8$, and the parity square to give $16$.

Going back to the original problem, both squares have a similar parity square (4679 in square 1 and 6947 in square 2). However the resultant 'T' shapes are not compatible, hence the two squares are in different equivalence classes, and hence we cannot get from one square to the other.

Improve this answer
$\endgroup$
-2
$\begingroup$

Turning a symmetrical pattern into a mixed symmetry pattern seems like it should not be possible since only 1 or 3 bits can be changed at a time.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.