CSPs - Part 1: How to (Almost) Always Win at Minesweeper

This article marks the beginning of a series dedicated to exploring a special class of problems: Constraint Satisfaction Problems (CSPs).

In general, a CSP consists of assigning values to a set of variables, chosen from a given domain, in such a way that all imposed constraints are satisfied. This is a highly generic theory, which allows us to apply it to countless challenges in computer science.

To demonstrate its versatility, throughout this series we will see how CSPs can be used to solve famous puzzles, such as Minesweeper, Sudoku, and the 8 Queens Problem, as well as practical applications like scheduling, resource allocation, and even formal proofs of algorithms.

However, before diving into more rigorous definitions, we’ll start with an intuitive approach: in the first articles, we’ll present some problems and develop initial modelings, without worrying too much about formalization. This will help us build the reasoning and intuition behind CSPs.

Minesweeper

We’ll begin with a classic problem—especially if you’ve ever used Windows and lost your internet connection—the Minesweeper game.

Minesweeper is a game where the player needs to reveal all the cells on a board without clicking on a mine. Each cell can be revealed by clicking on it, and if it contains a bomb, the game ends. If, on the other hand, the chosen cell is safe, one of two things can happen:

• A number appears, indicating the number of mines adjacent to the chosen cell.
• No number appears. In this case, there are no bombs adjacent to the cell, and the game will automatically reveal all neighboring cells until it reaches cells that do have adjacent bombs.

In practice, the player doesn’t need to guess every safe cell exactly, since revealing one safe region may uncover a large part of the board automatically. The interesting part is that, given the numbers on the revealed cells, we can combine this information to infer where new bombs may be located—or where cells are safe—even though there will always be an element of luck involved.

A Practical Example

Consider a Minesweeper puzzle with 4 rows, 4 columns, and 2 bombs. Initially, all its cells are hidden, so we have something like this:

4x4 board with two bombs. Green cells are unrevealed.

The player may choose any cell to start the game. Suppose we pick the cell (row=1, col=1), and the game continues to the following state:

4x4 board with two bombs. Green cells are unrevealed, while dark ones are revealed.
Those with numbers represent the number of adjacent bombs.

In this example, the first two rows had no adjacent bombs, so they are revealed with zeros. The third row is also revealed, but its cells have bombs nearby.

Now, let’s create a series of logical arguments that allow us to infer whether a cell is safe or contains a bomb, guiding our next moves.

To do this, we’ll enumerate all the statements we already know to be true.

We use (a,b) to represent the cell in row a and column b, indexed from one.

1. If there is one bomb adjacent to (3,1), then there must be one bomb between (4,1) and (4,2):

2. If there are two bombs adjacent to (3,2), then there must be two bombs among (4,1), (4,2), and (4,3):
   
   
   
   

3. If there is one bomb adjacent to (3,3), then there must be one bomb among (4,2), (4,3), and (4,4):
   
   

4. If there is one bomb adjacent to (3,4), then there must be one bomb among (4,3) and (4,4):
   
   
   

Now, let’s analyze each statement:

• (2) tells us there must be two bombs among (4,1), (4,2), and (4,3). But from (1), we know there’s one bomb between (4,1) and (4,2). Therefore, (4,3) must be a bomb.
• Next, (3) says there is one bomb among (4,2), (4,3), and (4,4). Since we already know (4,3) is a bomb, (4,2) and (4,4) must be safe.
• Finally, we know there are exactly two bombs on the board, and since (4,3) is one of them, only one bomb remains. The only possibility is (4,1).

With this reasoning, we could reveal the safe cells and, once no uncertainty remains, win the game!

An Initial Modeling

Our goal now is to try to create a formal treatment so that a computer program could replicate the kind of reasoning we just made. For this, let’s set some quick definitions:

Note: At this point, we’re not aiming for a rigorous formalization—we’ll get there later.

Given a Minesweeper board, we define:

Definition 1.1: Check if a cell is a bomb

For a cell $a_{ij}$ on a board $\mathcal{T}$ , we say:

$$isBomb(a_{ij}) = \begin{cases} 1, &\text{if } a_{ij} \text{ is a bomb} \\ 0, &\text{otherwise } \end{cases}$$

For instance, $isBomb(1,1) = 0$ , while $isBomb(4,3) = 1$ .

Definition 1.2: Neighborhood of a cell

Given a cell $a_{ij}$ on a board $\mathcal{T}$ , its neighborhood, denoted by $V_{a_{ij}}$ , is the set of all cells adjacent to $a_{ij}$ . Here, adjacency includes diagonals.

For example, in a 3x3 board, the neighborhood of (2,2) is:

$$V_{(2,2)} = {(1,1), (1,2), (2,1), (2,3), (3,1), (3,2), (3,3)}$$

We can then count the number of adjacent bombs:

Definition 1.3: Adjacent Bombs

For a cell $a_{ij}$ on a board $\mathcal{T}$ , we say $ADJ(a_{ij}) = p$ if $p$ is the number of bombs in the neighborhood of $a_{ij}$ . Formally,

$$ADJ(a_{ij}) = \sum_{(r,s) \in V_{a_{ij}}} isBomb(a_{rs})$$

If we represent the revealed board from the example in matrix form:

$$\mathcal{T} = \begin{bmatrix} 0&0&0&0\\ 0&0&0&0\\ 1&2&1&1\\ ?&?&?&?\\ \end{bmatrix}$$

Now, define $x_{ij} = isBomb(a_{ij})$ . Based on the state of the game, we can derive the following system of equations:

$$\begin{cases} x_{11} = 0\\ x_{12} = 0\\ ...\\ x_{41} + x_{42} = 1 &(i)\\ x_{41} + x_{42} + x_{43} = 2 &(ii)\\ x_{42} + x_{43} + x_{44} = 1 &(iii)\\ x_{43} + x_{44} = 1 &(iv)\\ x_{11} + x_{12} + ...+x_{44} = 2 &(v) \end{cases}$$

Equation (v) is the global constraint: it tells us the total number of bombs is 2.

By solving this system, we reach a unique solution:

$$\begin{matrix} x_{43} = 1\\ x_{41} = 1\\ x_{11} = x_{12} = ... = x_{42} = x_{44} = 0 \end{matrix}$$

In general, for a board $\mathcal{T}$ with $n$ rows, $m$ columns, and $k$ bombs, there are $\frac{(nm)!}{(nm-k)!k!}$ possible solutions. For instance, with a 4x4 board and 4 bombs, there are $\frac{16!}{12!4!} = 65,520$ solutions!

Revealing cells effectively means adding constraints to reduce the solution space. When we solve the system of equations above, we are essentially treating each cell as a variable $x_{ij}$ that can only take values 0 or 1, while each equation imposes a constraint on these variables. This process narrows down the possibilities until, in some cases, only a single consistent solution remains.

This is precisely why Minesweeper can be approached as a CSP: winning the game is nothing more than finding an assignment of values to the board’s variables that satisfies all imposed constraints simultaneously.

Conclusion

Minesweeper is a perfect example of how seemingly simple problems can be reformulated as Constraint Satisfaction Problems (CSPs). By translating the board into variables, domains, and constraints, we open the door to applying general techniques that go far beyond guessing or luck.

This perspective shift—from a casual game to a formal problem of optimization and search—allows us to draw connections with other classic challenges in computer science.

In this first article, we’ve only scratched the surface, structuring the problem and taking the first steps in modeling. In the upcoming posts, we’ll explore other examples before diving into how these problems can be solved in practice.

In the next article, we’ll explore another classic challenge—the Map Coloring Problem—and see how the same logic applies even more clearly.