Some months ago I started to write my own little minesweeper game to practice clojure a bit. After I had my first working solution ready, I started to discuss the underlying data structure with a friend of mine and since then the code has undergone several rewrites. This post provides a fully playable version on top of blog post 1 including a simple swing UI. To checkout the source code this blog post relies on:
If you want to sweep some mines, simply hit
on the commandline or alternatively
to start the REPL with all discussed sources included.
Placing the mines on the board
Choosing a nice mine placement is actually a hard problem, as Richard Kaye pointed out in his paper "Minesweeper is NP-complete". The ultimate goal is to have a configuration that is challenging while it is still possible to solve the game without the need to guess. In this blog post though, I'll distribute the mines randomly on the board, thus:
- create an indexed sequence in the size of the board
- remove the index of the first cell explored
- shuffle the elements of the sequence
- take the first n elements
- set the mines using the given indexes
as demonstrated in the following code snippet:
Another way to approach this problem is to have a fixed set of nicely fashioned boards (the most famous one is called "Dream Board") and to shift and rotate them around on the grid on every new game. This may be something for another blog post though.
Choose your neighbours wisely
In order to find out how many mines reside in the adjacent fields, we need a function that provides the surrounding indexes for a given cell. Assuming that the given cell is the center, the surrounding cells can be expressed like this:
The following higher-order function takes a vector of coordinates and applies them to the current coordinates, taking the boards dimension into account. By specifying a pattern, we are able to project any given shape on the board.
In case only the north, east, south, west neighbours are required instead, a different set of coordinates will do the trick:
Since we are able to separate good neighbours from the bad ones, the next step is to place some warnings on the board.
First of all, the neighbours of all mined cells are gathered, using the previously described functions. As a second step, the frequencies of all these cell indexes are calculated and assigned to the warnings vector using reduce.
Unfolding areas without mines
Whenever a new cell is explored, all adjacent areas that do not contain any mines should be automatically unfolded. The basic procedure is a variant of the flood fill algorithm:
- mark the current cell as explored
- collect all surrounding cells if none of them contains a mine and unveil them
- recursively repeat the procedure until no cells remain that satisfy 2.
Although the JVM currently does not support tail recursion, it's important that the recursive function call is the last statement in order to profit from the a tail-call optimization.
To find out which areas are suitable to auto-clear, we again use the neighbours function.
Wiring everything together
The core game mechanics (randomly set mines, place warnings, auto-clear fields) are done, now the last missing step is to add a function that puts together the discussed pieces and leaves us with a nicely prepared board.
Three more helper functions to do some condition checking on the board
and the minesweeper game is ready! In order to try out the game, we can start the clojure REPL from the commandline by executing lein repl and play around on your own
or alternatively type lein run and start sweeping mines in the swing application.
As I am quite lazy from time to time, a logical next step would be to implement an algorithm that solves the game automatically by either referring to well-known solving patterns or to try out some machine learning mechanics instead.
As long as there is nothing to solve it automatically, have fun playing or digging around in the code!