January 2002 Programmer's Challenge

Those of you that spend time on the Dark Side have certainly encountered that enemy of time well spent packaged with the OS for the masses, the game MineSweeper. For those of you who haven’t wasted hours on this pastime, the object of the game is to discover which cells in a rectangular grid contain bombs and which do not. You find the bombs by selecting one cell after another and specifying whether you think the cell contains a bomb. If you guess the cell to be safe and it actually contains a bomb, well, as they say, "game over". If the cell is safe, the game tells you how many of the 8 adjacent cells contain bombs. The skilled player uses this information to guess intelligently the next time.

Now, the standard MineSweeper game is probably too familiar to make an interesting Challenge. However, there are a couple of variants that are less well known. One of these variants is played on a board of hexagonal cells, where each cell has six neighbors instead of the standard eight. The variant for this Challenge uses triangular cells, with twelve neighbors for each cell, as depicted below.

The prototype for the code you should write is:

typedef void (*MinesweeperMoveProc) (
  int row,
  int col,
    /* row and column to be checked or marked */
    /* MinesweeperMoveProc updates contents of board variable provided to PlayMinesweeper */
  int *bombsRemaining,
    /* number of bombs remaining to be discovered */
  Boolean checkOrMark,
    /* FALSE to play the triangle (row,col), TRUE to mark it as a bomb */
  Boolean *youLose,
    /* returns TRUE if the location you played is a bomb */
  Boolean *youWin
    /* returns TRUE if you have marked all positions without losing */
);

#define kUnknown ((char)0x80)
#define kBomb ((char)0xFF)

void PlayMinesweeper (
  int boardSize,
    /* number of rows/columns in board */
  int numberOfBombs,
    /* number of bombs in board */
  const char *board,
    /* board[row*boardSize + col] is board element (row,col) */
  MinesweeperMoveProc MakeMove
    /* procedure for reporting moves */
    /* MakeMove updates elements of board */
);

Your PlayMinesweeper routine will be called with four parameters: the size of the game being played (boardSize), the number of bombs on the board (numberOfBombs), a pointer to the game board, and a callback procedure that you must use for each move. The board will be square, and boardSize indicates both the number of triangles in each row and the number of rows in the board. The example above shows a board with 4 rows and 10 columns — in the Challenge those values will be the same. Initially, you don’t know anything about the values of the board cells, so they will all be marked as kUnknown.

The third parameter is the MakeMove callback procedure. To make a move, you must call the MakeMove procedure with the location of a cell (row, col). If you think the cell is safe, you should set checkOrMark to FALSE. To mark the cell as a bomb, set checkOrMark to TRUE. MakeMove will update the values in the board originally provided to PlayMinesweeper. If the cell is a bomb, the corresponding board value will be set to kBomb. If the cell is empty, its value will be set to the number of bombs in the 12 neighboring cells. If you move to a cell containing a bomb without marking it as such, youLose will be set to TRUE and the game is over. If you mark a cell as a bomb that does not actually contain a bomb, you will also lose. And if you correctly mark all cells in the board, youWin will be set to TRUE, and you win the game.

Many versions of the minesweeper game will reveal more than one board cell when logic indicates that multiple cells are safe, as when the cell played has no neighbors that contain bombs. The Challenge callback updates only one board value for each move, allowing you the privilege of marking each cell yourself. Other versions of the game also allow you to tentatively mark a cell as a bomb, possibly changing your mind later. In the Challenge, you have only one chance to mark a cell correctly — mark a cell as a bomb incorrectly and it is Game Over.

The winner will be the player that wins the most games, weighted by size, in the minimum amount of time. You will earn one point per board cell for every game you win. One point will be deducted for each millisecond of execution time used in all games, including both games won and games lost. The execution time used by the callback procedure will be included.

This Challenge will use the CodeWarrior Pro 7 development environment. Solutions may be coded in C, C++, or Pascal (using the available-but-no-longer-supported Pascal compiler).

Oh, and just one more thing. ;-) Someone interested in the theory of computation is certain to write and tell me that MineSweeper is NP-complete. I know. If you are interested in this sort of thing, you can check out this link for some interesting work done by Richard Kaye.

Test code for this Challenge is available.

You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 12th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".