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:
github:87452cde61bb50164b93
If you want to sweep some mines, simply hit
lein run
on the commandline or alternatively
lein repl
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:
github:edb1b0e72586251c1ed6
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:
github:7172382b21feb79ef240
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.
github:6e676eefd982d2afd110
In case only the north, east, south, west neighbours are required instead, a different set of coordinates will do the trick:
github:2711d06963943a9792b9
Since we are able to separate good neighbours from the bad ones, the next step is to place some warnings on the board.
github:307cc090f41afa613f2a
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.
github:fb778a2e78870c84857d
github:aeeec66e3783beefe0ba
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.
github:502d0140fa7295f2cb70
Three more helper functions to do some condition checking on the board
github:279dddeb75ff9096c661
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
github:196de64861117fc9dc65
or alternatively type lein run and start sweeping mines in the swing application.
What's next?
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!