Method 1: Tree search

This seems to be the first algorithm which jumped into most people's minds. /u/LunarMist2 and /u/Synes7hesia suggested approaches like this, and I imagine many of the other people commenting also had similar ideas. The idea behind is a pretty similar to some of the algorithms used in AI for playing games like chess or checkers. Nobody suggested a concrete algorithm but the basic idea goes like this:

Start by picking any coin and flipping it. If this solves the game then you're done, otherwise pick another coin, flip it, and repeat the process. If at some point you decide that you've flipped enough coins, undo some of your previous choices and, continue again but with at least one of those choices done differently. Repeat this until you've either solved it or exhausted all possible choices.

How's it do?

This one is a bit hard to judge because there are many possible algorithms which would fit the rough outline I've given above. One challenge faced by approach of this type is how to know when to stop trying and undo some of your previous choices. Considering the problem description did not guarantee that every puzzle will be solvable, it's possible that you could flip forever and never get all the coins to be heads up. Even if you address this issue, you're still left with a pretty slow algorithm, particularly for larger grids of coins.

If you think a bit about the problem, you can come up with a much simpler and somewhat more efficient version of this algorithm:

Method 2: Unordered search

If you sit down and think about the problem for a bit, you'll probably realize a very important fact: it doesn't matter what order you makes you moves in. Furthermore, if you flip a coin twice, it's as if you didn't flip it at all. Thus all that matters is which of the coins you decide to flip, and which you decide not to flip.

The simplest way to translate this into an algorithm is to search over all possible subsets of the coins in the grid. If there are m rows and n columns in the grid, then there are 2^m*n such subsets. For each subset, try flipping only the coins in that subset. If this solves the problem then you're done. If it doesn't solve the problem then continue on with the next subset. If you've tried all the possible subsets and still not solved the problem, then you know it isn't possible to solve it.

Here's some Python code implementing this algorithm:

import itertools

def solution2(grid):
    coins = list(itertools.product(range(grid.nrows), range(grid.ncols)))
    ncoins = len(coins)
    for flips in itertools.product([True,False], repeat=ncoins):
        grid2 = grid.copy()
        coinFlips = [coins[i] for i,isFlip in enumerate(flips) if isFlip]
        grid2.flipAll(coinFlips)
        if grid2.isSolved():
            return coinFlips
    return None

How's it do?

On average, this solution method takes an amount of time which is exponential in the number of coins in the grid. This makes it pretty slow, but the Python version above is still able to solve 4x4 grids in a reasonable amount of time.

Despite the face that it's slow, it's still a totally legitimate and working solution. If anyone had submitted it, they would have been declared the only person to have solved the problem!

Still, if you think a bit more about the problem, you can come up with a somewhat more complex but much more efficient version of this algorithm:

Method 3: Unordered search on single row or column

If you sit and think even more about the problem, you'll realize another very useful thing: Since it only matters which subset of the coins you have to flip, you don't necessarily have to flip every coin in the grid to know that a candidate solution isn't going to pan out. For example, if you've flipped every coin in your subset that lies within the top two rows, but there's still a tails-up coin in the very top row, then you know that no matter which coins you flip in the remaining rows, that tails-up coin will never change.

There are multiple different ways to take advantage of this insight to speed up the previous method. With a bit more thought, however, you can come up one that also happens to be pretty simple to code. It goes like this:

First, search over all subsets of the coins just in the top row of the grid. There are 2ⁿ such subsets. For each such subset, flip just those coins in the top row. Now lock down the top row and don't flip any more coins in it. Since you're not allowed to flip any of the coins in the fop row. Now we'll go on to the next row (so the second row from the top). Since we're not allowed to flip any coins in the top row, there's exactly one way to fix any tails up coins in that top row: you have to flip each coin in the second-from-top row which is directly under a tails-up coin in the top row, and nothing else. If you do this, you're guaranteed an entirely heads-up top row. Now do the same thing with the third-from-top row to turn the second-from-top row all heads up. Continue down the rows in the grid until you get to the end.

After you've completed going down the rows like this, you're left with the last row. If you got lucky and the bottom row is entirely heads up, then you've solved the puzzle. Otherwise, pick another subset of coins in the top row and repeat the whole process again. If you haven't solved it even after trying all the possible subsets of coins in the top row, then you know it's impossible.

Here's some Python code implementing this algorithm:

import itertools

def solution2(grid):
    for topRowFlips in itertools.product([True,False], repeat=grid.nrows):
        grid2 = grid.copy()
        coinFlips = [(0,i) for i,isFlip in enumerate(topRowFlips) if isFlip]
        grid2.flipAll(coinFlips)
        for r in xrange(1, grid2.nrows):
            for c in xrange(grid2.ncols):
                if not grid2[r-1,c]:
                    coinFlips.append((r, c))
                    grid2.flip(r, c)
        if grid2.isSolved():
            return coinFlips
    return None

How's it do?

On average, this solution method takes an amount of time which is exponential in the square root of number of coins in the grid. This might still seem sort of slow, but actually it runs pretty quickly for any of the sizes of grids you'd be likely to bother trying to solve by hand. The unoptimized python implementation above can solve grids up to about 14x14 before it gets too slow.

Still, if you want an algorithm which can efficiently solve larger grids, you'll have to think about it a bit more: