A fun little puzzle

I ran into this interesting puzzle over at techInterview.org, which is a site dedicated to the kind of mental puzzles interviewers at certain companies love to ask job candidates. The puzzle is:

A 5*5 array is initialized to all 1s. Each cell can be either 0 or 1. When you flip a cell (m,n) (say from 1 to 0) all its four neighbors(left, right, up and down) flip. You need to change the array into all ZEROs by flipping the cells. How many minimum flips are required?

If I was really clever, I'd insert a Javascript widget here that let you play the game (assuming that Blogger even allows that), but I think the description is probably clear enough.

What was fun about the puzzle to me is that there are a huge number of states that the puzzle can be in, but it's obvious that there just has to be a better way to find a solution than just thrashing around blindly.

I was out sick from work yesterday, and in between naps, I tried working on the puzzle. Unfortunately, I just wasn't able to get much traction on the problem by trying to figure it out logically. Once I got frustrated enough, I resorted to a brute-force search of the solution space, which found 4 solutions, all of which were reflections and rotations of the same moves.

Leaving aside whether it's really very fair to ask for a "minimal" solution to a puzzle that only has one solution, it wasn't until I was copying the solution out of the terminal window that I saw the symmetry trick that makes it work.

Normally, when I'm trying to solve something like this, which just "has" to have a simple solution, I start by solviung a much simpler version, then try to scale up to the original problem as stated. For some reason, that process simply didn't occur to me yesterday. Had I tried starting with a 2x2 matrix and working my way up, I probably would have seen a pattern in the solutions pretty easily, and solved the puzzle by hand in a few minutes.

What did occur to me was that the total number of states, while large, was still well within the range where an exhaustive search would be reasonable. Once I had the program written to search for solutions, I ran it, and it finished suspiciously quickly. It turned out I had a bug, along the lines of using 2^25 instead of 2^26-1 in a critical place. I fixed that, re-ran it, and it still took less than 10 seconds. What the heck?

I tend to forget that the computers we have these days are so darn fast. Despite the fact that I'd done nothing to optimize that algorithm I was using, the PC was cranking along at 1 or 2 billion instructions a second, evaluating the 33,554,431 possible solutions at a speed of a few million iterations a second.

It's easy to think "this computer is so slow", when you're waiting multiple seconds for it to wake from sleep, or for some crazy Java applet to load, but when I see the results of the machine just cranking on some simple calculation, I'm just amazed at the power there.

If you want to see my thought process while I was working on this puzzle, you can read the techInterview discussion here, though my solution is there, so don't read it if you don't want to be spoiled. I'll probably post my code here later, so you can see what kind of C code I write when nobody's watching, and while I'm sick to my stomach :-)