Overview: Your challenge is to write a program that will play minesweeper optimally, giving the best move in any position. Moreover, you must do this on the largest board possible.

Game details: Minesweeper is a one player game, played on a rectangular board. At the beginning of the game, a specified number of mines are randomly distributed over the board, at most one to a cell. Each possible placement of the mines is equally likely. The mines' positions are hidden from the player.

On each of the player's turns, he or she chooses a square on the board to reveal. If the square contains a mine, the player loses the game. Otherwise, the number of mines in Moore neighborhood of the chosen square (orthogonally or diagonally adjacent) is revealed to the player.

The player repeats this until either a mine is revealed, or the number of unrevealed squares is equal to the number of mines. If the latter occurs, the player wins.

Program specification: Your program must take as input a board position, which should specify the locations and values of the revealed and unrevealed squares, as well as the number of mines on the board. It must return at least one move which has a maximal likelihood of winning if followed by optimal play. Returning more moves is allowed, as long as they all have the same, maximal, win rate.

In addition, the program must return the maximal number of possibilities that can be won under optimal play and the total number of possibilities for this revealed board state. From these values, the exact probability of winning under optimal play is known.


Input (in any format you prefer):

4 mines


Best moves are [(0, 1), (0, 2), (1, 0), (1, 3), (2, 0), (2, 3), (3, 1), (3, 2)].
961 wins out of 1820 possibilities.


5 mines


Best moves are [(0, 2)].
285 wins out of 360 possibilities.

Challenge specification: Your challenge is to run your program on the initial position of a board of one of the following types:

  • n x n board, n mines.
  • n x n+1 board, n mines.
  • n x n+1 board, n+1 mines.

Your program must find an optimal move on your machine at least as fast as the reference implementation solves the 4x5 board, 5 mines case on your machine. That case takes 6 minutes on my computer, for reference.

To run that instance of the reference implementation with timing, run python3 Minesweeper-challenge.py <<< "(4,5), 5, '____________________'"

The program that correctly identifies the optimal moves and exact number of possibilities that can be won with perfect play, on the initial position of the largest board of the above type, tiebreaker most mines, in the given time limit, wins the contest.

I will select a winner in two weeks, on July 24th.

Since writing a program like this is a big task, I will be awarding a bounty of 150 reputation, starting tomorrow and ending on the 18th.

Edit/bump: Well, that was a waste of 250 rep.

  • 1
    \$\begingroup\$ I think that this is almost a duplicate of codegolf.stackexchange.com/questions/24118/minesweeper-solver - at least the only solution there shows what you are asking for. \$\endgroup\$
    – Howard
    Jul 10 '14 at 7:18
  • \$\begingroup\$ @Howard I disagree. That's a code golf, this is a code challenge. That's a very important difference. In addition, that challenge merely specified minimal likelihood of immediately hitting a mine, instead of the maximal probability of winning the game, which is a much different challenge. \$\endgroup\$
    – isaacg
    Jul 10 '14 at 7:37
  • \$\begingroup\$ If you're asking for the perfect solution, why should you have any say in who the winner is? "Oh, Ye110wD*ck solution is more perfect than Howard..." Ludicrous. \$\endgroup\$
    – AndoDaan
    Jul 10 '14 at 7:43
  • 1
    \$\begingroup\$ @AndoDaan Have you noticed the tags? It's fastest code. I'm a sure that many people will get the optimal solution, it's who can do that faster that matters. I will edit the intro paragraph to make that more clear. \$\endgroup\$
    – isaacg
    Jul 10 '14 at 7:59
  • \$\begingroup\$ Downvoters: Please comment on what you think is wrong, if you think it can be improved. \$\endgroup\$
    – isaacg
    Jul 10 '14 at 18:43

Python, 4x5 board, 5 mines.

This is the reference implementation, I just thought I'd put it here to help give people ideas.

This implementation uses dynamic programming to prevent duplication of work, exploits mirror symmetries, and maintains a fist of all possible boards with a given revealed square status to check for guaranteed safe squares.

# Minesweeper solver
# Class just contains partially revealed boards that all look the same
# from the outside

# This is a branch, that uses strings.

# Boards have every cell revealed.
# Revealed is partially revealed. Boards must match revealed on every
# cell that is revealed.

# Meanings:
# '0'-'8': Safe square with that # of surrounding mines
# '*'    : Mine
# '_'    : Unrevealed
import copy
import itertools
import time
import pickle
import random
import math
import cProfile
import sys

class Position:
    def __init__(self, dimensions, revealed, boards):
        assert len(revealed)==self.dim_r*self.dim_c

    def click(self,loc):
        # Takes a location, returns all possible revealed positions, with boards
        # split up accordingly
            assert self.rev[loc]=='_'
        except AssertionError:
            assert self.rev[loc]=='_'
        # Create all possible new boards, split up by revealed item.
        for board in self.boards:
            if clicked_cell in board_dict:
        for rev_cell in board_dict.keys():
            # Make the new board without copying
        return new_positions

    def someBestClick(self):
        # Set of boards is all we know when outputting, may be smaller than
        # complete set
        # If we've clicked on a bomb, no way to win, no best click.
        if '*' in self.rev:
            return 0,[]
        unrevealed = [loc for loc in range(len(self.rev)) if self.rev[loc]=='_']
        # If there is only 1 possible board, you're done. The click list is every
        # unrevealed square on the board without a bomb under it.
        if len(self.boards)==1:
            return 1,[loc for loc in unrevealed if self.boards[0][loc]!='*']

        # If there is an unrevaled locaiton on the board that is bomb free in
        # every sub-board, use it.
        for loc in unrevealed:
            if all(board[loc]!='*' for board in self.boards):
                return sum(pos.memoBestClick()[0] for pos in self.click(loc)),[loc]

        # The broadest test - try everywhere.
        for loc in unrevealed:
            wins=sum(pos.memoBestClick()[0] for pos in self.click(loc) if pos.rev[loc]!='*')
            if wins>=most_wins:
                if wins>most_wins:
        return most_wins,click_list

    def memoBestClick(self):
        global memo
        global memo_counter
        memo_counter +=1
        if not self.rev in memo:
            # These lines check for mirror images of the board being in the memo table

            vert_reversed_memo_str=                                         \
                     for y in range(self.dim_r)][::-1])

            if vert_reversed_memo_str in memo:
                return vert_reversed_output[0],                             \
                         for loc in vert_reversed_output[1]]

            horiz_reversed_memo_str=                                        \
                    for y in range(self.dim_r))

            if horiz_reversed_memo_str in memo:
                return horiz_reversed_output[0],                            \
            if both_reversed_memo_str in memo:
                return both_reversed_output[0],                             \
                         for loc in both_reversed_output[1]]

            global restart_counter
            global restart_memo

            if len(self.rev)-self.rev.count('_') <= restart_max:
                return restart_memo[self.rev]
            # Needed because of memory issues
            if len(memo)>5*10**6:
        return memo[self.rev]

def makeBlankPosition(dimensions,mines):
    # Makes all locations on the board
    # Makes all possible distributions of mines
    for mine_layout in all_mine_layouts:
    return Position(dimensions, '_'*dim_c*dim_r, boards)

def makeBoardFromMines(dimensions,mine_layout):
    def mineNum(loc):
        if (loc%dim_c,loc//dim_c) in mine_layout:
            return '*'
        return str(sum(((loc%dim_c+dif[0],loc//dim_c+dif[1]) in mine_layout) for dif in
    return ''.join(map(mineNum,(loc for loc in range(dim_r*dim_c))))

def makePosition(dimensions,mines,revealed):
    for board in blank_pos.boards:
        if all(revealed[cell_num]==board[cell_num] or revealed[cell_num]=='_' for cell_num in range(len(board))):
    return Position(dimensions, revealed, boards_subset)

def winRate(dimensions,mines,revealed):
    global memo
    return wins[0],len(pos.boards),wins[1],memo

global memo_counter
global restart_counter
global restart_memo
global restart_max
dimensions, mines, revealed = eval(input())
wins, total_boards, moves, memo = winRate(dimensions, mines, revealed)
move_points=[(move//dimensions[1],move%dimensions[1]) for move in moves]
print("""Best moves are %s.\n%i wins out of %i boards. Ratio of %f. %i 
positions searched.\n%f seconds taken."""%(move_points, wins, total_boards, 
wins/total_boards, len(memo),time.clock()-start_time))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.