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:
- The number of remaining neighboring mines, i.e. once we flag a square as a mine, we decrement this number
- 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:
- 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
- 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:
- If we assigned "mine" and a neigboring constraint now has -1 number of mines, the board is inconsistent
- 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):
|1|0|0|1|0|0|1|0|0|1|0|0|1|0|
|1|0|0|1|0|0|0|1|0|0|1|0|0|1|
|0|1|0|0|1|0|0|0|0|1|0|0|1|0|
If we average the result for each square, we get:
|$\frac{2}{3}$|$\frac{1}{3}$|$\frac{0}{3}$|$\frac{2}{3}$|$\frac{1}{3}$|$\frac{0}{3}$|$\frac{1}{3}$|$\frac{1}{3}$|$\frac{0}{3}$|$\frac{2}{3}$|$\frac{1}{3}$|$\frac{0}{3}$|$\frac{2}{3}$|$\frac{1}{3}$|
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
continue
else:
if m.dead:
losses += 1
else:
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")}')
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,
visualize_output='video')
m.solve()
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
np.set_printoptions(precision=2)
# Load the minesweeper tiles
IMG_SQUARE_SIZE = 20
IMAGES = {}
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):
font = cv2.FONT_HERSHEY_SIMPLEX
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,
thickness=thickness)
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)),
borderType=cv2.BORDER_CONSTANT).astype(int)
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,
visualize_mask_text_size=0.7):
"""
width: width of the board
height: height of the board
num_mines: number of mines on the board
difficulty:
'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
prob_pick_strategy:
'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
visualize_constraints:
True: Displays number of neighboring mines and empty squares left
False: Displays the number of neighboring mines
visualize_lvl:
0: no visualization
1: visualize final square picks
2: visualize all search steps
visualize_zero_probs:
If True, will visualize the probability of a zero-numbered square
visualize_output:
'video': outputs video
'image': outputs individual frames
visualize_crop:
A tuple with (y, x, height, width) crop in squares to visualize
visualize_frames:
A tuple with the range of frames to visualize
visualize_iterations:
A tuple with the range of iterations to visualize
visualize_mask_text:
Masks out squares using text
visualize_mask_text_size:
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]
else:
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:
np.random.seed(seed)
random.seed(seed)
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
else:
# 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
break
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.visualize()
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:
continue
if not (self.prob_mine[search_map] == 2).any():
# Result is cached, so skip
continue
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
break
self.visualize(lvl=2, assignments=assignments, search_squares=search_squares)
continue
# 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)
solutions.append(solution)
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(),
num_mines_left)
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))
warnings.resetwarnings()
prob_zero[np.isnan(prob_zero)] = 0
self.visualize(duplicate_num_frames=5)
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
print('Here')
else:
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,
mine_indices=mine_indices)
else:
self.visualize(duplicate_num_frames=10, open_indices=empty_indices,
mine_indices=mine_indices)
return empty_indices, mine_indices, labels, unresolved_edges, unresolved_non_edge
@property
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:
queue.append(square)
break
if len(queue) == 0:
# There were no start/end points, so must be a loop. Pick any square
# to start with
queue.append(search_squares[0])
while len(queue) > 0:
s = queue.pop(0)
left_to_visit[s[0], s[1]] = False
ordered_search_squares.append(s)
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)
I = IMG_SQUARE_SIZE
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
@property
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:
return
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
return
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]))
else:
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):
I = IMG_SQUARE_SIZE
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,
x_crop*I:(x_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']
else:
# 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
else:
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))
else:
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]
else:
img[s] = IMAGES['flagged']
elif assignments is not None and assignments[y, x] == 0:
img[s] = _mark_img(IMAGES['facingDown'])
else:
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)
else:
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
@property
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':
return
# 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'
]
subprocess.call(' '.join(command), shell=True, stderr=subprocess.STDOUT)
# Remove the images
for filename in glob.glob('board*.png'):
os.remove(filename)
# Create a data url with the video data
with open('tmp.mp4', 'rb') as f:
data_url = "data:video/mp4;base64," + b64encode(f.read()).decode()
# Remove the video
os.remove('tmp.mp4')
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">'
f'</video>')
display(HTML(html))
Comments
Comments powered by Disqus