Minesweeper. Do I need to say more?
The most interesting part is how to efficiently and randomly create the board.
There are
many,
many,
many (and more) ways of doing so, I'll describe my idea here:
- the board size for an average game will not be so big that I can't afford to store an additional O(N^2) piece of information. This is the key point, without this assumption, the rest is not applicable!
- if I do store that piece of information, then I can acceptably randomize it in O(N)
- since the random distribution is from 1 to board_size (all the valid spots for a mine, N^2 spots) but the board is actually a matrix and therefore has 2 indices, I need a way to convert from the random spot to the matrix spot reliably
- if we have too many mines, it's best to randomly place empty spots instead
- after the initial placement, we need a pass on the matrix to fill the remaining spots with the correct count of the neighbouring mines
The randomization can be done with a call to
Collections.shuffle, while the conversion from board spot to the matrix spot can be done easily after some considerations. Consider this sample matrix:
1 2 3
4 5 6
7 8 9
Given any of those numbers, can you determine the exact matrix location? Meaning can you return a i and j that indicate where that number would be placed in the matrix? For example 1 would be 0,0 and 8 would be 2,1.
Yes, but
rows and columns have to be treated differently AND, since we do care about randomness but not precision, we can even avoid adjusting the result to reflect the exact position - we can't get the same position twice anyway.
For
columns we can simply use the
modulus operator, this way the last column is 0 and not 2, but since we are going for random spots we don't care to correct it. Basically we are
flipping the matrix over on the Y axis :)
For
rows instead, we can simply use
division and then
round the values UP to get something in range 1 .. board_length which we
convert to 0-based.
The method looks like this (can be reduced to fewer lines, but debugging is easier this way!):
private int decodeCoordinate(int value, boolean is_column){
//column we can find with modulus
//last column is 0 if we do this calculation, but we are going for random spots so we don't care to correct it
if(is_column) return value % fieldLength;
//rows we can find with a normal division and then picking the ceiling of it, converting to 0-based!
double a = (double) value, b = (double) fieldLength;
int c = (int) Math.ceil(a / b);
return c - 1;
}
You can check the implementation on my
Gist alongside some test cases in
MinesweeperJTests. I plan to pick this up again to finish it, so some parts are extra and do not yet tie in to the final code :)
