Minesweeper is known as a bonus game that came with the computer, but it has also been a topic in math and computer science research. The keyword is ”NP-complete.”

Minesweeper Is NP-Complete

Around the year 2000, the mathematician Richard Kaye is said to have shown that the following problem about Minesweeper belongs to a family of hard problems called “NP-complete.”

Given a board with numbers on it, is there even one way to place mines that does not contradict those numbers?

The question we think about when we play, “Is this square safe?”, is closely connected to this problem.

What NP-Complete Means

Put simply, NP-complete describes a problem with these properties.

  • Checking whether an answer is right is easy: if someone shows you one way to place the mines, you can quickly check whether it matches all the numbers.
  • Finding an answer is hard (we believe): as the board gets bigger, the number of candidate layouts grows very fast. No known method can find an answer quickly for every possible board.

It is also known that NP-complete problems can be turned into one another. If someone found a method that quickly solves even one of them in every case, all the other NP-complete problems could be solved quickly too. Whether such a fast method exists is a famous unsolved problem called the “P versus NP problem,” and it is one of the problems with a million-dollar prize.

The Number of Layouts Gets Huge Fast

Checking layouts is hard because the number of candidates becomes very large.

  • The number of ways to place 8 mines on a 9×7 board is the number of ways to choose 8 squares out of 63, about 3.9 billion.
  • The number of ways to place 75 mines on a 26×15 board is the number of ways to choose 75 squares out of 390, a number with more than 80 digits.

Of course, when you actually play, you do not need to check them all. Squares that touch no number can be considered together, and many situations are settled by looking at just one or two numbers. Even so, in places where numbers are tangled up in complicated ways, reaching a certain answer can be hard.

The App Picks Only Boards That People Can Solve by Logic

When the Minesweeper app builds a board, it checks whether the board can be solved from start to finish using only the following three rules that people use.

  1. What you can tell from a single number
  2. What you can tell by combining two numbers
  3. What you can tell from the mines left on the whole board

Each rule looks at only a small area and can be checked quickly. If a board cannot be solved with these three, the app moves the mines and builds it again. That is why you can always solve a board to the end without the heavy kind of thinking that checks every layout.

The boards you can play in the articles on this site are made the same way. When we timed how long it takes to build a board the size of Level 5 on a computer, it averaged a few milliseconds per board.

Puzzles and Math

Many other pencil puzzles, such as Number Place (Sudoku), are also known to be NP-complete in their general form when the board gets bigger. Many puzzles that people enjoy solving are made so that you can solve them step by step without checking everything. The no-guess boards in the Minesweeper app are one of them.

We cover how to calculate probabilities in Minesweeper Probability.