Gridflip
I received and invitation facebook.com site, so i registed. I have to
say that it’s a great site, you can share photos and a lot of other
stuff with your friends. It’s very cool.
But … the history begins when i clicked in the “jobs” bottom link,
then puzzles and … my obsession begins 
The grid flip puzzle disturbs me for several days.
Then i began to think in the algorithm. First i wanted to isolate the
row and columns operations in others, something like flip a single cell.
Later i can transform the complete mask, previously calculated with
flip_cell(x,y), into row and columns operations.
At this moments i’m not absolutly sure if this is possible at all,
so … i thougt another way.
With an small array i thought in the all possible combinations with
columns and rows flips.
This is the formula:
2^(colums+rows) = number of mask combinatios
so in a 5 x 5 array, the program have to test 2^10 = 1024
The next step is to make all the masks combinations. I was a very easy
task. I only had to iterate from 0 to 2^columns and in this loop iterate
from 0 to 2^rows.
Maybe i can explain with an example. Let’s take a look to a 3×3 array,
and start with columns:
loop from 0 to 2^3 = 8
0 -> 000
1 -> 001
2 -> 010
3 -> 011
4 -> 100
5 -> 101
6 -> 110
7 -> 111
In binary notation i have all combination for the columns like:
000
000
000
001
001
001
010
010
010
…
then the rows time:
000
000
000
100
100
100
010
010
010
…
and the combination of each other with
for i in 0 .. 2^columns
for j in 0 .. 2^rows
mask(i,j)
Then i can test the mask with the data. This process is very slow and
tooks me several hours to get the fist success combination, but the
solution is simple and the number of column and rows flips is very low.
I used java to implement the program, but probably in c or c++ it would
be faster.
I’ve enjoyed a lot with this puzzle, thanks to the facebook group for
this personal challenge.
My next step is trying to optimize the proccess to get a solution in
less time. Maybe i can infer row and column flips from cell operations
or with minimax, or perhaps … with something different, in don’t know.