The variables are the board squares, which each contain either a mine or a constant between 0 and 8. A set of values that can be assigned to the variables.A set of constraints on these variables that must be satisfied.Minesweeper constraintsĪ constraint satisfaction problem has a few parts: Using these algorithms - constraint propagation in particular - we can mimic the logic human players would use to play Minesweeper.Īfter getting as far as we can with logic, we will use depth-first search with backtracking to guess new squares to uncover. The animation that you just saw is an intermediate puzzle with a 16x16 board and 40 mines. Expert - the board is 30x16, with 99 mines.Intermediate - the board ranges from 13x15 to 16x16, with 40 mines.Beginner - the board ranges from 8x8 to 10x10, with 10 mines.With more difficult puzzles, you will sometimes have to resort to guessing if you find yourself left with covered squares that are equally likely to be mines or safe squares. It is often possible to solve easier puzzles simply by using logic to determine where the mines are located and which squares are safe to uncover. So the goal is to figure out where the mines are and avoid uncovering them.
If you uncover all of the squares except for any mines, you win the game. It is a numbered square between 0 (zero) and 8 - we'll call this number the square's constant.The square contains a mine, and the game ends because you lost.Two possibilities when you uncover a square: The goal is to not uncover a square that contains a mine, so if you've identified a square that likely contains a mine, you can flag it so that you remember to avoid uncovering it. In the last post, we generated random Minesweeper boards in Python - check that out here if you haven't yet.Īs you can see in the animation, it starts out with all of the squares covered, and you play the game by uncovering squares. Minesweeper is a single-player puzzle game that you may have played on a computer at some point. We're going to solve Minesweeper as a constraint satisfaction problem. The animation was created with Matplotlib. You can find the code for this post here.
0 kommentar(er)
