Blank-fill + random guess

Nobody submitted this algorithm, probably because it sucks. I mention it since it gives us something concrete to start with. The idea is if you have a visible square which has no mines around it, it's safe to click on every square around it. If you reach a point where you can't make any more progress this way, just guess randomly.

Here's some code implementing this algorithm:

def solveWithBlankFill(grid):
    while not grid.isSolved():
        needToGuessRandomly = True
        for r,c in grid.iterVisible():
            if grid.nMinesAround(r,c) == 0:
                for r2,c2 in grid.iterNeighbors(r,c):
                    if not grid.isVisible(r2,c2):
                        needToGuessRandomly = False
                        grid.guess(r2,c2)

        if needToGuessRandomly:
            r, c = random.choice([(r,c) for r,c in grid.iterHidden()])
            grid.guess(r,c)

Many Minesweeper implementations will implement an algorithm like this automatically to save the player from pointless tedium, so this really is not a very sophisticated algorithm. Still it does almost as well as the example AI I included. This algorithm also has the advantage that it's very easy to implement, and provides a starting point for more sophisticated methods.

Using flags + random guessing

Many implementations of Minesweeper also provide the ability to make a square with a flag, indicating that you have determined that it contains a mine. It turns out that this technique is also really handy in writing Minesweeper algorithms. Algorithms of this nature were the first ones suggested, for instance by /u/Flutterwry in this comment and by /u/Kodiologist in this comment.

These algorithms are based on repeatedly using following the following rules for each visible square:

1. If the number of hidden squares is equal to the number of mines around the current square, mark all of the hidden squares with flags.
2. If the number of mines is equal to the number of flagged squares around the current square, it's safe to guess all of the non-flagged squares.

If you keep repeating these rules it's sometimes enough to solve the game, particularly on the easier difficulty levels. If you reach a point where you can't make any more progress by using the above rules, just guess randomly. Here's some source code implementing this algorithm:

def solveWithFlags(grid):
    marked = Array2D(grid.nRows(), grid.nCols(), False)
    grid.guess(grid.nRows()/2, grid.nCols()/2)
    while not grid.isSolved():
        needToGuessRandomly = True
        for r,c in grid.iterVisible():
            nmines = grid.nMinesAround(r,c)
            nmarked = sum(1 for r,c in grid.iterNeighbors(r,c) if marked[r,c])
            nhidden = grid.nHiddenAround(r,c)

            if nhidden == nmarked:
                continue
            if nmines == nhidden:
                for r2,c2 in grid.iterNeighbors(r,c):
                    if not grid.isVisible(r2,c2):
                        marked[r2,c2] = True
                        needToGuessRandomly = False
            if nmines == nmarked:
                for r2,c2 in grid.iterNeighbors(r,c):
                    if (not grid.isVisible(r2,c2)) and (not marked[r2,c2]):
                        grid.guess(r2,c2)
                        needToGuessRandomly = False

        if needToGuessRandomly:
            r, c = random.choice([(r,c) for r,c in grid.iterHidden() if not marked[r,c]])
            grid.guess(r,c)

This is still a relatively easy algorithm to implement, and it's a lot better than the previous one and the example AI. It's also has the advantage that it runs pretty quickly and that the main part of it doesn't involve any guessing. This makes it a handy method to use to solve the "easy" parts of a game of Minesweeper, and you only need to fall back to a more sophisticated algorithm when it gets stuck.

/u/Kodiologist : Using flags + heuristic guessing

This one is by /u/Kodiologist. You can find a like to the source code in this comment

/u/Kodiologist was the first person to post a solution. His method combined the flag-based solves described previously with a heuristic to make educated guesses when the flag-based solver can't make any more progress. I'll just copy in /u/Kodiologist's description of the algorithm from this comment.

We start off by estimating probabilities of squares containing mines. The probability for an interior square is estimated naively as the number of unseen mines divided by the number of uncleared squares not known to contain mines. The probability for a frontier (i.e., hidden but non-interior) square is estimated as the maximum of the probabilities implied by neighboring cleared squares (I think your original dumb solver did this). So if we have a frontier square with a lower probability of having a mine than the interior squares, we pick that. Otherwise, we pick an interior square, and since we've computed only one probability for all the interior squares, we choose the interior square with the least sum of taxicab distances from the frontier squares (on the hopes that such an interior square will be most useful to have cleared).

As you can see from the scores, this smarter method of guessing improves over just guessing randomly, and gives an algorithm which is almost three times as likely to solve the game on expert difficulty than the previous one.