Algorithms Explained : Minesweeper Game

This blog post explains most critical algorithms for well-known windows oriented game, minesweeper:

Game Rules:

1. The board is a two dimensional space, which has a predetermined number of mines.
2. Cells has two states, opened and closed.
3. If you left-click on a closed cell:
1. Cell is empty and opened. 
1. If neighbour cell(s) have mine(s), this opened cell shows neighbour mine count.
2. If neighbour cells have no mine, all neighbour cells are opened automatically.
2. Cell has a mine, game ends with FAIL.
4. If you right-click on a closed cell, you put a flag which shows that "I know that cell has a mine".
5. If you multiclick (both right and left click) on a cell which is opened and has at least one mine on its neighbours:
1. If neighbour cells' total flag count equals to this multi-clicked cell's count and predicted mine locations are true, all closed and unflagged neighbour cells are opened automatically.
2. If neighbour cells' total flag count equals to this multi-clicked cell's count and at least one predicted mine location is wrong, game ends with FAIL.
6. If all cells (without mines) are opened using left clicks and/or multi-clicks, game ends with SUCCESS.

Data Structures:

We may think each cell as a UI structure (e.g. button), which has following attributes:

• colCoord = 0 to colCount
• rowCoord = 0 to rowCount
• isOpened = true / false   (default false)
• hasFlag    = true / false    (default false)
• hasMine  = true / false    (default false)
• neighbourMineCount  0 to 8  (default 0, count of total of mines on neighbour cells)

So, we have a two dimensional "Button[][] cells" data structure to handle game actions.

Algorithms:

Before Start:

1. Assign mines to cells randomly (set hasMine=true) .
2. Calculate neighbourMineCount values for each cell, which have hasMine=false. (this step may be done for each clicked cell while game continues but it may be inefficient)

Note1: Neighbour cells should be accessed with {(colCoord-1, rowCoord-1),(colCoord-1, rowCoord),(colCoord-1, rowCoord+1),(colCoord, rowCoord-1),(colCoord, rowCoord+1),(colCoord+1, rowCoord-1),(colCoord+1, rowCoord),(colCoord+1, rowCoord+1)} coordinates. And don't forget that, neighbour cell counts may be 3 (for corner cells), 5 (for edge cells) or 8 (for middle cells).

Note2: It's recommended to handle mouse clicks with "mouse release" actions instead of "mouse pressed/click" actions, otherwise left or right click may be understood as multi-clicks or vice versa.

Right Click on a Cell:

• If cell isOpened=true, do nothing.
• If cell isOpened=false, set cell hasFlag=true and show a flag on the cell. 

Left Click on a Cell:

• If cell isOpened=true, do nothing.
• If cell isOpened=false:
• If cell hasMine=true, game over.
• If cell hasMine=false:
• If cell has neighbourMineCount > 0, set isOpened=true, show neighbourMineCount on the cell. If all cells which hasMine=false are opened, end game with SUCCESS.
• If cell has neighbourMineCount == 0, set isOpened=true, call Left Click on a Cell for all neighbour cells, which hasFlag=false and isOpened=false.

Note: Last step may be implemented with recursive call or using a stack data structure.

Multi Click (both Left and Righ Click) on a Cell:

• If cell isOpened=false, do nothing.
• If cell isOpened=true:
• If cell neighbourMineCount == 0, no nothing.
• If cell neighbourMineCount > 0:
• If cell neighbourMineCount != "neighbour hasFlag=true cell count", do nothing.
• If cell neighbourMineCount == "neighbour hasFlag=true cell count":
• If all neighbour hasFlag=true cells are not hasMine=true, game over.
• If all neighbour hasFlag=true cells are hasMine=true (every flag is put on correct cell), call Left Click on a Cell for all neighbour cells, which hasFlag=false and isOpened=false.

Note: Last step may be implemented with recursive call or using a stack data structure.