Skip to main content

Solving Minesweeper

Many years ago I took a class in Artificial Intelligence, in which the final group project was to build a program that played Minesweeper (although this would hardly be considered AI today!). Like most group projects everybody prioritized other classes, me included. Eventually I tried to pull an all-nighter to implement it, in a language I had just "learned": C++. Never doing that again. But I've always wanted to actually finish it, so here it goes. This time I'm using Python, numpy, and other libraries which makes the task much easier. I'll try to do things without looking at other implementations, because where's the fun in that?

The Algorithm

The problem is how to deduce which squares have mines and which don't based on the neighboring constraints which tell us how many neighboring mines there are. Most of the closed squares don't have any explicit constraints on them, so unless we're left with no choice, we'll focus on the edges which do have constraints. If we have an edge region of N squares with interlocking constraints, there are $2^N$ mine configurations that could be considered. Brute-forcing this can start to get prohibitively slow real fast. Luckily, we can use the constraints to limit how many configurations we have to try.

Consider this partially solved board:

First, it would be helpful to display our updated constraints for this partially solved board. Let's do this by showing two pieces of information per square:

  1. The number of remaining neighboring mines, i.e. once we flag a square as a mine, we decrement this number
  2. The number of remaining closed and unflagged neighbors. Again, we decrement this number for the neighbors when we open a square.

Here is what that looks like:

In the right image squares, the upper left number is the number of remaining mine neighbors, and the lower right number is the number of remaining unopened neighbors.

We can now set up two simple rules:

  1. If a square says there are K neighboring mines left, and K closed and unflagged neighbors, we know that all those neighbors have to have mines
  2. If a square has no neighoring mines left, then we can safely open all closed neighbors

Applying these rules to the board above, we see that the square with the green box can be safely opened, and the square with the red box definitely has a mine:

Suprisingly, repeatedly applying these two simply rules and updating the constraints solves many beginner and intermediate boards all by itself, but sometimes (and more so for expert difficulty) we get stuck. Let's look at such a case that happens later on:

In this case, there is no simple rule we can apply. We have to try all possible configurations and then make a decision based on the result. This can be done by a constraint satifaction search. Essentially, we go through the squares in order one by one, and assigns it a mine or not mine. Then we check what happens with our constraints:

  1. If we assigned "mine" and a neigboring constraint now has -1 number of mines, the board is inconsistent
  2. If we assigned "not mine" and a neighboring constraint says there are more neigboring mines than there are closed squares, the board is also inconsistent.

If an assignment is consistent, we continue on to the next square.

If both possible assignments are inconsistent, we backtrack and try different assignments on the previous squares. Here's what this looks like in action:

The result of this search can give us many different consistent configurations, possibly with differing number of mines.

Since we have all possible configurations, we can look at each individual square and see how many times it was a mine versus not a mine. The search above yielded 3 possible solutions (starting from the top right corner):


If we average the result for each square, we get:


The same result shown on the board:

Each square shows the probability of having a mine in percentage points. Highlighted in green are the squares with zero probability, meaning we can safely open them.

This begs the question of what to do if there are no 0% squares. Then we simply have to take a chance on the lowest probability square. But at this point we also have to consider other squares that are not at the edge. They may also be worth opening. If you look at the bottom row, these squares have a 17% probability, how do we go about calculating this?

Well, we know how many mines there are in total and how many we've flagged, let's call those $M_t$ and $M_f$ respectively. Then we also have the probabilities for each edge square being a mine $P(S_i = mine)$. Then we have the number of "inner" closed squares, $N$.

The expected, or average number of mines in the edge is simply the sum of the probabilities: $\sum_{i} P(S_i = mine)$. Again, it's possible that some configurations have more mines than others, so this estimate doesn't have to be a round integer.

The final probability for the "inner" closed squares is then: $$\frac{max(M_t - M_f - \sum_{i} P(S_i = mine), 0)}{N}$$

Let's calculate it for the case above: $$\frac{10 - 4 - (6*0.33 + 4*0.67)}{8} = 0.1675$$

Using these inner probabilities, we can now pick the lowest probability square overall, not only those at the edge.

Advanced Strategies

What if we have many choices of lowest probability square? Here's where it gets a little bit complicated.

If we have multiple choices, we probably want to choose the one that gives us the most valuable information. One way to look at it is that we'd prefer if the square we pick has a higher chance of being a "zero", meaning it has no constraints at all. What happens in that case is that we automatically expand the whole area underneath. This gives us more information than if we hit a numbered square right away, in which case we probably have to make another risky choice for the next square.

What is the probability of a square being a "zero" then? Well, it depends on the mine probabilities of its neighbors. If a neighbor has a 90% chance of being a mine, then this square would have at least a 90% chance of having a constraint. So we want to combine the probabilites of the square and its neighbors. Since they are independent events, we can calculate that as the probability of the whole neighborhood being not mines: $$P(S_i = zero) = \prod_{j \in N(i)}{P(S_j = \neg mine)} $$ Where $N(i)$ is the neighborhood of square i.

Let's look at the starting board. The mine probabilities are uniform since we have no information:

But the probability of being a zero is higher along the edges, and highest in the corners, because they have fewer neighbors that could be mines:

This explains the common strategy of opening the corners first, since the difference is quite big for this beginner board: 22% vs 51% chance of being zero. This strategy of course also applies later in the game, but then incorporates the mine probabilities from the configuration search.

We can test the different strategies by running the solver on a large number of boards and comparing the win ratios:

def estimate_win_ratio(num_runs, **board_kwargs):
  wins, losses = 0, 0
  for i in range(num_runs):
    m = MinesweeperBoard(seed=i, **board_kwargs)
    step = m.solve()
    if m.dead and step == 0: # Lost on first guess
      if m.dead:
        losses += 1
        wins += 1
  return wins / (wins + losses)
num_runs = 10000
print(f'Win ratios for strategies over {num_runs} runs:')
print(f'Random lowest probability mine: {estimate_win_ratio(num_runs, difficulty="expert", max_solutions=2000, prob_pick_strategy="random")}')
print(f'Max zero probability: {estimate_win_ratio(num_runs, difficulty="expert", max_solutions=2000, prob_pick_strategy="prob_zero")}')
Win ratios for strategies over 10000 runs:
Random lowest probability mine: 0.4014
Max zero probability: 0.4945

Using the max zero probability strategy is clearly better, by almost 10 percentage points. Note that for these win rations I excluded runs that immediately hit mines.

Now, I don't think the algorithm is optimal quite yet. Have a look at this impasse, where we end up picking the corner square based on the reasoning above:

While opening the corner improves our chances of a zero square, perhaps we would get even more information by picking a square close to the edge, in order to loosen up the deadlock. Intuitively, we'd want to pick the square which reduces the uncertainty about the edge probabilities. We could use all the configurations produced by the search, and figure out if there is a square we can open to disambiguate between them.

We can also see that the difference in probability between the corner square and the 33% edge squares is 1%. This is such a small difference that it could make sense to pick one of those edge squares in order to split the edge region in half, divide and conquer style.

In the end, it will probably boil down to a tradeoff between minimizing mine probability and maximizing expected information gain. Exacly how to go about doing that I'll leave for a later time. For now, I'll leave you with the solving of an "expert" difficulty board:

m = MinesweeperBoard(difficulty='expert', seed=10,
                     visualize_constraints=False, visualize_lvl=1,
m.display_video(framerate=10, controls=True, autoplay=True, loop=True, max_width='100%')

And the code for the whole thing:

import os
import math
import glob
import random
import warnings
import subprocess
from time import time
from base64 import b64encode

import cv2
import numpy as np
import PIL.Image
from IPython.display import display, HTML
import IPython.display
from matplotlib.animation import FuncAnimation
import matplotlib.pyplot as plt
from skimage.measure import label
from scipy.ndimage.morphology import distance_transform_edt


# Load the minesweeper tiles
for name in list(range(9)) + ['bomb', 'facingDown', 'flagged']:
  img = cv2.imread(f'minesweeper/{name}.png')
  IMAGES[str(name)] = cv2.resize(img, (IMG_SQUARE_SIZE, IMG_SQUARE_SIZE))

def draw_text_centered(img, text, size, color, thickness=1):
  text_size = cv2.getTextSize(text, font, size, 2)[0]
  # get coords based on boundary
  text_x = (img.shape[1] - text_size[0]) // 2
  text_y = (img.shape[0] + text_size[1]) // 2
  return cv2.putText(img, text, (text_x, text_y), font, size, color,

def count_neighbors(board):
    For each square, counts the number of neighboring squares that are "on".
    Uses a sum convolution to count neighbors.
    board: a boolean matrix or numerical 0/1 matrix
  return cv2.filter2D(board.astype(float), -1, np.ones((3,3)),

class MinesweeperBoard:
  def __init__(self, width=None, height=None, num_mines=None, difficulty=None,
               seed=None, max_solutions=None, prob_pick_strategy='prob_zero_near_edge', 
               visualize_constraints=True, visualize_lvl=0, visualize_zero_probs=None,
               visualize_output='video', visualize_crop=None, visualize_frames=None,
               visualize_iterations=None, visualize_mask_text=None,
      width: width of the board
      height: height of the board
      num_mines: number of mines on the board
        'beginner', 'intermediate' or 'expert', if this is set, width/height/num_mines are not used
      seed: the seed for randomization
      max_solutions: stop the search once this many solutions have been found
        'random': pick one of the lowest probability mine squares randomly
        'prob_zero': pick the lowest probability mine with the
                     highest probability of being a zero-numbered square
        'prob_zero_near_edge': same as prob_zero, but pick the square nearest
                               an unresolved edge if there are multiple choices
        True: Displays number of neighboring mines and empty squares left
        False: Displays the number of neighboring mines
        0: no visualization
        1: visualize final square picks 
        2: visualize all search steps
        If True, will visualize the probability of a zero-numbered square
        'video': outputs video
        'image': outputs individual frames
        A tuple with (y, x, height, width) crop in squares to visualize
        A tuple with the range of frames to visualize
        A tuple with the range of iterations to visualize
        Masks out squares using text
        Font size of the text mask
    difficulties = {
      'beginner': (8, 8, 10),
      'intermediate': (16, 16, 40),
      'expert': (24, 24, 99)
    assert difficulty in [None, 'beginner', 'intermediate', 'expert'] # TODO: Use enum class?
    assert difficulty is not None or (width is not None and height is not None and num_mines is not None)
    if difficulty in difficulties:
      self.width, self.height, self.num_mines = difficulties[difficulty]
      self.width, self.height, self.num_mines = width, height, num_mines
    self.num_squares = self.width*self.height
    self.max_solutions = max_solutions
    assert prob_pick_strategy in ['random', 'prob_zero', 'prob_zero_near_edge'] # TODO: Use enum class?
    self.prob_pick_strategy = prob_pick_strategy
    assert self.num_mines < self.num_squares
    assert 0 <= visualize_lvl <= 2
    assert visualize_output in ['video', 'image']
    self.visualize_constraints = visualize_constraints
    self.visualize_lvl = visualize_lvl
    self.visualize_zero_probs = visualize_zero_probs
    self.visualize_output = visualize_output
    self.visualize_frames = visualize_frames
    self.visualize_iterations = visualize_iterations
    self.visualize_crop = visualize_crop
    self.visualize_mask_text = visualize_mask_text
    self.visualize_mask_text_size = visualize_mask_text_size

    # Generate the mine locations
    if seed is not None:
    self.mines = np.zeros((self.height, self.width), dtype=bool)
    # NOTE: sample indices without replacement
    mine_indices = random.sample(range(self.width*self.height), self.num_mines)
    self.mines.ravel()[mine_indices] = True
    assert self.mines.sum() == self.num_mines, (self.mines.sum(), self.num_mines)

    self.text_mask = None
    if self.visualize_mask_text is not None:
      # Add mines that look like the text
      mask = np.zeros_like(self.mines, dtype='uint8')
      mask = draw_text_centered(mask, self.visualize_mask_text, self.visualize_mask_text_size,
                                color=1, thickness=1)
      # Remove mines within 2 steps of the text, so that we can see the text better
      mask_dilated = cv2.dilate(mask.astype('uint8'),
                                np.ones((3, 3), 'uint8'), iterations=2) > 0
      self.mines[mask_dilated > 0] = False
      self.mines[mask > 0] = True
      self.text_mask = mask > 0

    # Pre-calculate a map of neighboring mine counts
    self.neighboring_mine_count = count_neighbors(self.mines)

    # Create an map of labeled empty regions
    self.empty_regions = label(self.neighboring_mine_count == 0, connectivity=1)

    # Create 2D arrays for keeping track of the state of the board and our belief about it
    self.opened = np.zeros((self.height, self.width), dtype=bool)
    self.flagged = np.zeros((self.height, self.width), dtype=bool)
    self.neighboring_mines_left = self.neighboring_mine_count.copy()
    self.neighboring_unresolved_left = 8*np.ones((self.height, self.width), dtype='uint8')
    self.prob_mine = 2*np.ones((self.height, self.width), dtype=float)
    self.dead = False # Set to true if we hit a mine
    # Variables used for visualization and debugging
    self.iteration = 0
    self.frame_idx = 0

  def solve(self):
    """ Solves the board or dies trying """
    self.t0 = time()
    self.visualize() # Draw once to see the empty board

    while not self.solved and not self.dead:
      # Get the next square index to open
      open_indices, mine_indices, *rest = self.solve_step()
      prev_opened = self.opened.copy()

      for open_idx in open_indices:
        # Check if there's an empty region under the square
        region = self.empty_regions[open_idx[0], open_idx[1]]
        if region > 0:
          # Dilate the region to open the neighboring squares with neighboring mine counts
          reveal = cv2.dilate((self.empty_regions == region).astype('uint8'),
                              np.ones((3, 3), 'uint8'), iterations=1)
          self.opened[reveal > 0] = True
          # There was no empty region underneath, just a mine count, so just reveal this square
          self.opened[open_idx[0], open_idx[1]] = True
        # Check if there is a mine there
        if self.mines[open_idx[0], open_idx[1]]:
            self.dead = True
      for mine_idx in mine_indices:
        # Remove the mine from neighboring mine counts
        ns = self.neighborhood_slice(mine_idx)

        self.neighboring_mines_left[ns] -= 1
        self.flagged[mine_idx[0], mine_idx[1]] = True

      # Recalculate closed and unflagged neighbors
      self.neighboring_unresolved_left = count_neighbors(self.unresolved)

      # Clear the cached probabilities in the regions where we made picks
      labels, unresolved_edges, unresolved_non_edge = rest
      self.prob_mine[unresolved_non_edge] = 2
      just_opened_dilated = cv2.dilate((self.opened & ~prev_opened).astype('uint8'),
                                       np.ones((3, 3), 'uint8'), iterations=1)
      for i in range(1, labels.max()+1):
        search_map = (labels == i) & unresolved_edges
        if (just_opened_dilated & search_map).any():
          self.prob_mine[search_map] = 2 # Reset
      # Reset open/mine_indices and display the new board

      self.iteration += 1
    self.t1 = time()

  def solve_step(self):
    """ Returns the next board square indices to open and the 
    squares we want to mark as mines"""

    # Now we're trying to find a configuration of mines/not mines that agrees with
    # the neighboring mine counts. We split up the problem by connected components in
    # the squares with non-zero neighbor count. For each component, we find the assignment
    # that agrees with neigboring unopened squares. If there are multiple possible assignments
    # we pick a square to open with the lowest probability of being a mine over all 
    # Get the neighbors of the numbered squares (i.e. the squares we want to 
    # find an assignment for)
    has_constraints = (self.neighboring_mines_left > 0) | (self.neighboring_unresolved_left > 0)
    numbered_dilated = cv2.dilate((has_constraints & self.opened).astype('uint8'),
                                  np.ones((3, 3), 'uint8'), iterations=1)
    unresolved_edges = self.unresolved & (numbered_dilated > 0)
    unresolved_non_edge = self.unresolved & (numbered_dilated == 0)
    # Find connected components of unresolved edges connected by constraints
    # Since that numbered square represents constraints on both components,
    # we have to join them in the optimization
    unresolved_edges_dilated = cv2.dilate(unresolved_edges.astype('uint8'),
                                          np.ones((3, 3), 'uint8'), iterations=1)
    joined_edges = unresolved_edges | (unresolved_edges_dilated & has_constraints & self.opened)
    labels, num_labels = label(joined_edges, connectivity=2, return_num=True)

    # Check for simple cases, where
    # 1. There are as many neighboring mines left as there are closed (unassigned) squares
    #    This means all neighbors are mines
    # 2. If there are no neighboring mines left, then all neighboring closed squares
    #    must be empty
    all_mines = (self.opened & (self.neighboring_mines_left > 0) &
                 (self.neighboring_mines_left == self.neighboring_unresolved_left))
    all_empty = (self.opened & (self.neighboring_mines_left == 0) &
                 (self.neighboring_unresolved_left > 0))
    if all_mines.any() or all_empty.any():
      all_mines_dilated = cv2.dilate(all_mines.astype('uint8'),
                                     np.ones((3, 3), 'uint8'), iterations=1) > 0
      mine_indices = np.vstack(np.where(all_mines_dilated & self.unresolved)).T

      all_empty_dilated = cv2.dilate(all_empty.astype('uint8'),
                                     np.ones((3, 3), 'uint8'), iterations=1) > 0
      empty_indices = np.vstack(np.where(all_empty_dilated & self.unresolved)).T
      self.visualize(open_indices=empty_indices, mine_indices=mine_indices)
      return empty_indices, mine_indices, labels, unresolved_edges, unresolved_non_edge

    for i in range(1, num_labels+1):
      search_map = (labels == i) & unresolved_edges
      if np.count_nonzero(search_map) == 0:

      if not (self.prob_mine[search_map] == 2).any():
        # Result is cached, so skip

      search_squares = self.visit_in_order(search_map)
      self.visualize(lvl=1, duplicate_num_frames=5, search_squares=search_squares)
      # Assignment map: -1 = no assignment, 0 = not mine, 1 = mine
      assignments = -1*np.ones((self.height, self.width), 'int')
      search_idx = 0
      solutions = [] # keeps track of all consistent solutions found
      num_search_squares = len(search_squares)
      while search_idx < num_search_squares:
        p = search_squares[search_idx]
        ns = self.neighborhood_slice(p)
        prev_assignment = assignments[p[0], p[1]]
        reached_max_solutions = (self.max_solutions is not None
                                 and len(solutions) >= self.max_solutions)
        if prev_assignment == 0 or reached_max_solutions:
          # We've cycled through mine/not mine assignemnts, so backtrack
          self.neighboring_unresolved_left[ns] += 1
          if prev_assignment == 1:
            self.neighboring_mines_left[ns] += 1

          assignments[p[0], p[1]] = -1
          search_idx -= 1
          if search_idx < 0:
            # We've checked all possible solutions, so exit loop
          self.visualize(lvl=2, assignments=assignments, search_squares=search_squares)
        # We cycle through mine -> not mine
        new_assignment = 1 if prev_assignment == -1 else 0
        if new_assignment == 0 and prev_assignment == 1:
          # Add back a mine
          self.neighboring_mines_left[ns] += 1
        assignments[p[0], p[1]] = new_assignment
        if new_assignment:
          # Decrement mines_left
          self.neighboring_mines_left[ns] -= 1
        # No matter whether we think there's a mine or not, we decrement number
        # of closed neighbors
        if prev_assignment == -1:
          self.neighboring_unresolved_left[ns] -= 1
        # If number of mines left is negative, we're in an inconsistent state
        inconsistent_mines = (self.neighboring_mines_left[ns] < 0) & self.opened[ns]
        inconsistent_mines_left = inconsistent_mines.any()
        # If number of closed squares is less than number of mines left, we're in an ainconsistent state
        inconsistent_closed = (self.neighboring_unresolved_left[ns] < self.neighboring_mines_left[ns]) & self.opened[ns]
        inconsistent_closed_left = inconsistent_closed.any()
        inconsistent = np.zeros((self.height, self.width), dtype=bool)
        inconsistent[ns] = inconsistent_mines | inconsistent_closed
        self.visualize(lvl=2, inconsistent=inconsistent, assigning_idx=p,
                       assignments=assignments, search_squares=search_squares)
        is_inconsistent = inconsistent_mines_left or inconsistent_closed_left
        if not is_inconsistent and search_idx == num_search_squares - 1:
          # We have a possible solution at the last search square, so save it
          solution = assignments[search_squares[:, 0], search_squares[:, 1]]
          self.visualize(lvl=2, duplicate_num_frames=5, solution=solution,
                         assignments=assignments, search_squares=search_squares)
        elif not is_inconsistent:
            # Not inconsistent, so progress to the next square
            search_idx += 1
      # Tally up the solutions and return the empty squares and mines we're 100% sure about
      # If we have no such squares, we return the lowest mine probability square to be opened.
      num_mine = np.zeros(len(search_squares), dtype=float)
      num_not_mine = np.zeros(len(search_squares), dtype=float)
      solutions_array = np.vstack(solutions)
      num_mine = (solutions_array == 1).sum(axis=0)
      num_not_mine = (solutions_array == 0).sum(axis=0)
      num_total = num_mine + num_not_mine
      sq = search_squares
      self.prob_mine[sq[:, 0], sq[:, 1]] = num_mine / num_total

    # Now calculate the mine probability not only the search squares, but also the
    # inside squares. First, we calculate how many mines there are in the edges of
    # all unresolved components, so we can subtract that (and the flagged mines) from
    # the mine count

    # NOTE: num_edge_mines doesn't have to be an integer, since it's possible
    # that different solutions have different number of mines. It's also possible
    # that some solutions have more mines than there are mines left on the board
    num_mines_left = self.mines.sum() - self.flagged.sum()
    num_edge_mines = min(self.prob_mine[(self.prob_mine < 2) & unresolved_edges].sum(),
    if unresolved_non_edge.any():
      self.prob_mine[unresolved_non_edge] = ((self.mines.sum() - num_edge_mines - self.flagged.sum())
                                              / unresolved_non_edge.sum())

    # If there are squares with 0 probability mine, we return those and the sure mines
    empty_indices = np.vstack(np.where(self.unresolved & (self.prob_mine == 0))).T
    mine_indices = np.vstack(np.where(self.unresolved & (self.prob_mine == 1))).T
    if len(empty_indices) == 0:
      # There are no obvious squares to open, so find the lowest mine probability square
      # and pick the one with the highest probability of being a zero-numbered square
      # NOTE: Although the mine probability would be the same, we prefer zero-numbered
      # squares because they open up 3-8+ new squares with constraints.

      # Calculate the probability that each unresolved square is has zero neighboring mines
      # This is calculated as the product of the probability of all squares in the neighorhood is _not_ a mine
      # NOTE: we do this by a convolution in the log space, since the sum of logs equals
      # the log of the product. Then we exponentiate to get the probability
      prob_zero = np.zeros((self.height, self.width), dtype=float)
      # NOTE: if 1-prob_mine is zero, then log(1-prob_mine) is NaN, and during the
      # convolution these NaNs will spread to the neighbors. We _want_ this to happen
      # so that we can set all NaNs to 0 probability of being a zero-numbered square, since
      # a NaN means there is a mine neighbor
      warnings.filterwarnings('ignore') # Ignore the NaN warning
      prob_zero = np.exp(cv2.filter2D(
          np.log(1 - self.prob_mine), -1, np.ones((3,3)), borderType=cv2.BORDER_CONSTANT))
      prob_zero[np.isnan(prob_zero)] = 0
      if self.visualize_zero_probs:
        self.visualize(lvl=1, duplicate_num_frames=5, prob_zero=prob_zero)

      # Now we pick the lowest probability mine to open, but with the highest
      # probability of a zero underneath (no neighboring mines)
      is_min_mine_prob = self.prob_mine == self.prob_mine[self.unresolved].min()
      is_max_zero_prob = prob_zero == prob_zero[is_min_mine_prob].max()
      is_min_mine_max_zero = is_min_mine_prob & is_max_zero_prob
      if self.prob_pick_strategy == 'random':
        best_choices = np.vstack(np.where(is_min_mine_prob)).T
      elif self.prob_pick_strategy == 'prob_zero': 
        best_choices = np.vstack(np.where(is_min_mine_max_zero)).T
      elif self.prob_pick_strategy == 'prob_zero_near_edge':
        distance_from_edge = distance_transform_edt(~unresolved_edges)
        is_one_square_away = distance_from_edge <= math.sqrt(2)
        if (is_min_mine_max_zero & is_one_square_away).any():
          best_choices = np.vstack(np.where(is_min_mine_max_zero & is_one_square_away)).T
          best_choices = np.vstack(np.where(is_min_mine_max_zero)).T
        #is_min_dist = distance_from_edge == distance_from_edge[is_min_mine_max_zero].min()
        #best_choices = np.vstack(np.where(is_min_mine_max_zero & is_min_dist)).T

      best_choice = random.choice(best_choices)
      empty_indices = np.array([best_choice])
      self.visualize(duplicate_num_frames=5, open_indices=empty_indices,
      self.visualize(duplicate_num_frames=10, open_indices=empty_indices,
    return empty_indices, mine_indices, labels, unresolved_edges, unresolved_non_edge

  def solved(self):
    return (np.array_equal(self.mines, self.flagged)
            and (self.opened | self.flagged).all())

  def visit_in_order(self, search_map):
    """ Returns the indices of `search_map > 0` in order, starting at the edges
    of the components if there are any, and then in a BFS fashion """
    left_to_visit = search_map.copy()
    ordered_search_squares = []
    while left_to_visit.any():
      search_squares = np.vstack(np.where(left_to_visit)).T
      queue = []
      for square in search_squares:
        ns = self.neighborhood_slice(square)
        num = search_map[ns].sum()
        # NOTE: if there <= 2 squares in this slice, then it has to be a start/end point
        # If there are 3 or more, it means `square` is in the center of a path
        if num <= 2:
      if len(queue) == 0:
        # There were no start/end points, so must be a loop. Pick any square
        # to start with

      while len(queue) > 0:
        s = queue.pop(0)
        left_to_visit[s[0], s[1]] = False
        ns, offset = self.neighborhood_slice(s, return_offset=True)
        neighbors = np.vstack(np.where(search_map[ns])).T + offset
        l1_neighbors, l2_neighbors = [], []
        for n in neighbors:
          if not left_to_visit[n[0], n[1]]: continue
          if np.linalg.norm(n - s) > 1: l2_neighbors.append(n)
          else: l1_neighbors.append(n)

          left_to_visit[n[0], n[1]] = False
        for n in l1_neighbors: queue.append(n)
        for n in l2_neighbors: queue.append(n)

    return np.array(ordered_search_squares)

  def draw_frame(self, **kwargs):
    """ Draw the current board / solver state as an image """
    if not self.visualize_constraints:
      return self._draw_board(**kwargs)

    # Draw normal board and constraints board side-by-side with a white space between
    normal = self._draw_board(**kwargs)
    constraints = self._draw_board(visualize_constraints=True, **kwargs)
    crop = self.visualize_crop or (0, 0, self.height, self.width)
    img = 255*np.ones((I*crop[2], I*(crop[3]*2+1), 3), dtype='uint8')
    img[:, :I*crop[3]] = normal
    img[:, I*(crop[3]+1):] = constraints
    return img

  def unresolved(self):
    """ Returns the unresolved squares, i.e. the ones that have neither been
    opened nor flagged as mines """
    return ~self.opened & ~self.flagged

  def neighborhood_slice(self, p, return_offset=False):
    Convenience function to get a numpy slice object for the neighborhood around a
    point `p` _within_ the board dimensions. Can return the offset to the board origin
    ns = np.s_[max(p[0]-1, 0):min(p[0]+2, self.height),
                max(p[1]-1, 0):min(p[1]+2, self.width)]
    if return_offset:
      offset = np.array([p[0]+(0 if p[0] == 0 else -1),
                          p[1]+(0 if p[1] == 0 else -1)])
      return ns, offset
    return ns

  def visualize(self, lvl=1, duplicate_num_frames=1, **kwargs):
    Visualizes current state of the solver and either outputs it as an HTML image
    element, or saves the frame for future video creation.
    if self.visualize_lvl < lvl:

    not_in_frame_range = (self.visualize_frames is not None and
                          (self.frame_idx < self.visualize_frames[0] or
                           self.frame_idx >= self.visualize_frames[1]))
    not_in_iteration_range = (self.visualize_iterations is not None and
                              (self.iteration < self.visualize_iterations[0] or
                               self.iteration >= self.visualize_iterations[1]))

    if not_in_frame_range or not_in_iteration_range:
      self.frame_idx += 1

    img = self.draw_frame(**kwargs)
    if self.visualize_output == 'image':
      if self.visualize_frames is None:
        print(f'Iteration {self.iteration} frame {self.frame_idx}')
      IPython.display.display(PIL.Image.fromarray(img[..., ::-1]))
      for i in range(duplicate_num_frames):
        cv2.imwrite(f'board{self.frame_idx:04}-{i:02}.png', img)

    self.frame_idx += 1

  def _draw_board(self, visualize_constraints=None, open_indices=[], mine_indices=[],
                  search_squares=[], solution=None, assignments=None, assigning_idx=None,
                  inconsistent=None, prob_zero=None):
    crop = self.visualize_crop or (0, 0, self.height, self.width)
    img = np.zeros((crop[2] * I, crop[3] * I, 3), 'uint8')

    def _highlight_square(y, x, color=0, thickness=2):
      y_crop = y - crop[0]
      x_crop = x - crop[1]
      s = np.s_[y_crop*I:(y_crop+1)*I, x_crop*I:(x_crop+1)*I]
      t = thickness
      smaller = np.s_[y_crop*I+t:(y_crop+1)*I-t, x_crop*I+t:(x_crop+1)*I-t]
      mask = np.zeros(img.shape[:2], dtype=bool)
      mask[s] = True
      mask[smaller] = False
      img[mask, :] = color

    def _mark_img(img, color=0):
      img = img.copy()
      img[I//3:I-I//3, I//3:I-I//3, :] = color
      return img

    for y in range(crop[0], crop[0]+crop[2]):
      for x in range(crop[1], crop[1]+crop[3]):
        y_crop = y - crop[0]
        x_crop = x - crop[1]
        s = np.s_[y_crop*I:(y_crop+1)*I,

        if self.opened[y, x]:
          if self.flagged[y, x]: img[s] = IMAGES['flagged']
          elif self.mines[y, x]: img[s] = IMAGES['bomb']
            # Display mines left in upper left corner, and closed left in lower right
            if visualize_constraints:
              square = IMAGES['0'].copy()
              if not (self.neighboring_mines_left[y, x] == 0 and
                      self.neighboring_unresolved_left[y, x] == 0):
                tl_crop = np.s_[:I//2, :I//2] 
                br_crop = np.s_[I//2:, I//2:] 
                mines_left = self.neighboring_mines_left[y, x]
                size = 0.2 if mines_left < 0 else 0.4 # make it smaller for -1 so it fits
                square[tl_crop] = draw_text_centered(
                    square[tl_crop], str(mines_left), size, color=(0, 0, 160))
                square[br_crop] = draw_text_centered(
                    square[br_crop], str(self.neighboring_unresolved_left[y, x]), 0.4, color=(255, 0, 0))
              img[s] = square
              img[s] = IMAGES[str(self.neighboring_mine_count[y, x])]

          if inconsistent is not None and inconsistent[y, x]:
            _highlight_square(y, x, color=(0, 0, 255))
          if self.flagged[y, x] or (assignments is not None and assignments[y, x] == 1):
            if self.text_mask is not None and self.text_mask[y, x]:
              # If it's a text mine, flip the channels so that the flags are blue
              # instead of red, to increase visual contrast
              img[s] = IMAGES['flagged'][..., ::-1]
              img[s] = IMAGES['flagged']
          elif assignments is not None and assignments[y, x] == 0:
            img[s] = _mark_img(IMAGES['facingDown'])
            if prob_zero is not None and prob_zero[y, x] != 0:
              text = str(int(round(100*prob_zero[y, x])))
              img[s] = draw_text_centered(IMAGES['facingDown'].copy(), text,
                                           size=0.3, color=0)
            elif self.prob_mine is not None and self.prob_mine[y, x] < 2:
              text = str(int(round(100*self.prob_mine[y, x])))
              img[s] = draw_text_centered(IMAGES['facingDown'].copy(), text,
                                           size=0.3, color=0)
              img[s] = IMAGES['facingDown']

    # Draw various highlights
    for open_idx in open_indices:
      _highlight_square(*open_idx, color=(0, 255, 0))

    for mine_idx in mine_indices:
      _highlight_square(*mine_idx, color=(0, 0, 255))

    for search_idx in search_squares:
      color = 255 if solution is None else (0, 255, 0)
      _highlight_square(*search_idx, color=color, thickness=2)

    if assigning_idx is not None:
      _highlight_square(*assigning_idx, color=0)

    return img

  def time(self):
    if None in [self.t0, self.t1]: return None
    return self.t1 - self.t0

  def display_video(self, framerate=2, autoplay=False, loop=False, controls=False,
                    width=None, max_width=None):
    Displays a video of the step by step board solution by using the images
    writted to disk and combining them with ffmpeg, finally displaying it as an HTML
    video element
    if self.visualize_output != 'video':

    # Call ffmpeg to create video
    command = [
      'ffmpeg', '-y', '-framerate', str(framerate), '-pattern_type', 'glob', '-i', '"board*.png"',
      '-c:v', 'libx264', '-r', '30', '-pix_fmt', 'yuv420p', 'tmp.mp4'
    ]' '.join(command), shell=True, stderr=subprocess.STDOUT)
    # Remove the images
    for filename in glob.glob('board*.png'):

    # Create a data url with the video data
    with open('tmp.mp4', 'rb') as f:
      data_url = "data:video/mp4;base64," + b64encode(
    # Remove the video

    width_str = 'width="'+width+'"' if width is not None else ""
    max_width_str = 'style="max-width:'+max_width+'"' if max_width is not None else ""
    # Display the video HTML element
    html = (f'<video {"controls" if controls else ""}'
            f'       {width_str}'
            f'       {max_width_str}'
            f'       {"autoplay" if autoplay else ""}'
            f'       {"loop" if loop else ""}>'
            f'   <source src="{data_url}" type="video/mp4">'