Talk:Flipping bits game

References?

I doubt that this game is unique. If anyone has any links to the game elsewhere then please tell. Thanks.

Oh, I am also looking for strategies to finish the game. --Paddy3118 (talk) 12:19, 10 July 2013 (UTC)

I'm trying to work out if it is even possible to finish the game starting from an arbitrary position. I suspect it isn't. Consider a $2\times 2$ grid with an initial position with one cell set, and where the target position is where all cells are unset; all sequences of game operations either keep one cell set (equivalent by rotation) or transition the state to one with three cells set (equivalent to the one-cell-set case by a trivial negation and rotation). Now, it might be that I'm missing something and that larger grids are in fact always soluble, but I suspect not right now. (I can't work it out for the 3\times 3 case but my investigations do run into the sand in a telling way, and larger grids feel like more of the same.)

If my intuition is right, surely we should only be posing solvable games? And if that's true, what is the safety condition? (If it's some sort of parity, I'm not seeing it, but then I'm perhaps just being obtuse.) Or should we just do the creation of the starting position by construction (i.e., by generating a random sequence of moves from the target position — target/start are swappable of course as all moves are self-inverses)? –Donal Fellows (talk) 08:28, 11 July 2013 (UTC)

Hi Donal. I thought that a general target position might not be solvable from a given start position so although I generate the target randomly, I generate the start position by random legal flips which are reversible. Maybe I should add this strategy to the task description? --Paddy3118 (talk) 15:56, 11 July 2013 (UTC)