Minesweeper Cascade Algorithm
A cascade in Minesweeper (Windows version) occurs when a single click uncovers many adjacent squares. A cascade can expand and uncover large portions of the board. Understanding the cascade algorithm is not only interesting from a programming point of view but can also provide a slight advantage when playing the game.
Inferring the behavior of the cascade algorithm just by playing Minesweeper is fairly difficult. However, it should be obvious that a cascade occurs only when all adjacent squares (next to the square clicked) do not contain mines. An interesting situation occurs when all the mines adjacent to the square clicked are marked as mines. One would expect a cascade to occur under this situation but this is not the case and can be verified.
Intuitively it seems that a cascade expands by uncovering adjacent mine-free blocks of 3x3 squares. To verify this conjecture I disassembled Minesweeper executable. The functions, StepBox, StepXY, and CountBombs were found to be relevant to the cascade algorithm. The cascade algorithm is summarized below:
- Initialize a queue
- If current square is non-mine uncover it and add to queue, otherwise gameover
- Remove a square from queue
- Count mines adjacent to it
- If adjacent mine count is zero, add any adjacent covered squares to queue and uncover them
- Go to step 3 if queue is not empty, otherwise finish
The description above is very high level and slightly simplified as compared to the actual algorithm. The actual data-structure used in the algorithm is a circular queue, implemented using an array, with a capacity of 100. Of course this assumes that there will never be more than a 100 elements in the queue. To justify this assumption Windows Minesweeper forces a maximum board size.
In the algorithm, step 5 looks to be fairly complex. The number of adjacent squares differs from place to place on the Minesweeper board. A corner square has only three adjacent squares, a square next to an edge of the board has five adjacent squares, and every other square has eight adjacent squares. It seems Minesweeper needs three cases dealing with each of these scenarios. Even counting the number of adjacent squares seems like quite a lot of code, so what does Minesweeper do?
The solution is quite clever. The visible Minesweeper board is the center of a larger board. For example, the 9x9 board is the center of an 11x11 board. The extra squares in the 11x11 board form a border around the 9x9 board. This allows every square of the visible board to have 8 adjacent squares, and therefore no special cases result. The cascade algorithm would break down if a non-visible square was put in the queue. This is avoided by initializing the extra squares as non-mine and uncovered. Now, these squares can never be put in the queue as step 5 of the algorithm only puts squares in the queue which are covered.
Another interesting detail is the iterative nature of the cascade algorithm. It is clear that the queue data-structure can be replaced with any container data-structure. A stack is an obvious choice. Which begs the question: why the implementors did not use recursion to implement the algorithm? The use of recursion in this case would have considerably simplified the algorithm as it would obviate the need for the queue data-structure. The recursive algorithm would work as follows:
- If current square is a mine gameover, otherwise uncover square
- Count mines adjacent to current square
- If adjacent mine count is zero, uncover all adjacent covered squares and make a recursive call for every one of them (steps 2-3)
Understanding the cascade algorithm yields some hints for gameplay as well. A cascade is more likely when the square clicked has fewer adjacent squares. This is true of the corners and edges. On the flip side, the cascade will have less room to expand when there are fewer adjacent blocks. Consequently the area uncovered by the cascade will be smaller.
by Usman Latif [Nov 24, 2003]