Solving the Flipping Game

My friend David Klein has the following to say about the flipping game that I mentioned in the Monkey post (my comments in italics):

Assume the game is laid out as follows:

ABC
DEF
GHI
JKL

Each location is either flipped up or down. Each move consists of selecting a location (e.g. B) and flipping both that location as well as all orthogonally adjacent locations (for B, this would mean locations B as well as A, C, and E). Your job is to flip them all up (or down) in the least number of moves.

The game is always solvable. Indeed, working from the bottom row upwards, it is trivial to bring all of them face up, except for the top row, which leaves only 2^3 possible "games". There are 12 "operators" corresponding to selecting one of the 12 positions to flip. It is trivial to see that these operators are commutative and idempotent (i.e. doing an operator twice is the identity and has no effect). Thus any sequence of moves is equivalent to choosing for each of the 12 operators to apply it either zero or one times, i.e. there are 2^12 different move sequences. If none of them repeat, then we can reach all 2^12 different board positions. If one board position repeats, then applying the two sequences one after another gives the identity position. I.e. there is a non-trivial sequence which is the identity. Performing Gaussian elimination on the transformation matrix shows that this can't occur. Indeed, the sequence to flip only A is

ABDFHIL

only B is

ABCGHIK

and only C is

BCDFGHJ

In other words, In any sequence of flips to solve the game, no piece ever has to be chosen twice, because a twice-chosen piece simply undoes what the first flip series did. You will never have ...B....B... to solve this puzzle. That means that any board can be completely solved in 12 moves or less!

To understand why you only need to know how to solve A, B, and C, consider the following:

To solve the bottom three pieces J, K, and L, you only have to flip some from the third row of pieces G, H, and I. To solve the third row, flip the second row. To solve the second row, flip the first row. That means that you will always be left with some combination of A, B, and C to finish up. Add the corresponding sequences to the flips, and you finish the puzzle.

Now, to get the smallest number of steps, add all of these flips together in a row, sort, cancel all even pairs, and the result is your solution.

Let me show you how to solve the case where only L is flipped and I think the rest will be clear:

ABC
DEF
GHI
JKl

On the bottom (4th) row, only L is flipped. Flip I to get it right:

ABC
DEf
Ghi
JKL

On the 3rd row, H&I are flipped. Flip E&F to get them right.

Abc
dEf
GHI
JKL

On the 2nd row D&F are flipped, flip A&C to get them right

abC
DEF
GHI
JKL

The sequence so far is IEFAC

That leaves only A&B flipped. The sequences to fix them were given previously as

ABDFHIL and ABCGHIK

The full sequence is then

IEFACABDFHILABCGHIK

sorting and cancelling even pairs we get

ADEGIKL

I also asked about the solution for an NxM board:

As to an NxM board: The matrix is (NxM) on (NxM) and solving the matrix equation for any right hand side (i.e. original configuration) takes about (NxM)^3/3 operations (This can probably be done much more efficiently as the matrix is sparse). Note: I haven't proved yet that the matrix is non-singular for all N and M. In any case, if it is singular, the Gaussian elimination process will detect it and generate the configuration which is not solvable.

Yehuda

Update: fixed math logic. I originally wrote that you should apply "uniq" after sorting moves, but the correct function is to include a move once if there are an odd number of those moves in the sequence and not include it at all if there are an even number.

Technorati tags: board games, board game, abstract game, abstract games