How to randomly distribute mines for a Minesweeper program

Question

I've gotten up to Test 9/10 of the autochecker and have made my programming now 333 lines of Java code, as per the course requirement (being written in Java, not over XXX amount of lines). Basically, we need to draw a Minesweeper board with the mines shown as "*"s and the other cells showing a count of mines in the surrounding 1 cell areas around them. Here is my code:

public class Minesweeper {

    public static void main( String[] args ) {

        int m = Integer.parseInt( args[0] );
        int n = Integer.parseInt( args[1] );
        int k = Integer.parseInt( args[2] );
        int[][] gridArray = new int[m][n];
        int[][] mineArray = new int[m][n];
        int[][] placedMines = new int[k][2];
        int totalCells = m * n;
        int randomRow = (int) (Math.random() * m);
        int randomColumn = (int) (Math.random() * n);

        //Place mines...
        for (int i = 0; i <= k - 1; i++) {

            int pos = 0;

            while (true) {

                if (pos <= k - 1) {

                    if ((randomRow == placedMines[pos][0]) && (randomColumn == placedMines[pos][1])) {

                        if( ( k == totalCells ) && ( pos == k - 1 ) ) {

                            break;

                        } else {

                            randomRow = (int) (Math.random() * m);
                            randomColumn = (int) (Math.random() * n);
                            pos = 0;

                        }

                    } else {

                        pos++;

                    }

                    //System.out.println( "Gotten " + pos + "!" );

                } else {

                    break;

                }

            }

            mineArray[randomRow][randomColumn] = 1;
            placedMines[i][0] = randomRow;
            placedMines[i][1] = randomColumn;

        }

        //Place Kth mine...
        if( k == totalCells ) {

            for( int y = 0; y <= m - 1; y++ ) {

                for( int x = 0; x <= n - 1; x++ ) {

                    if( mineArray[y][x] == 0 ) {

                        mineArray[y][x] = 1;
                        placedMines[placedMines.length - 1][0] = y;
                        placedMines[placedMines.length - 1][1] = x;
                        break;

                    }

                }

            }

        }

        //Get numbers...
        for( int y = 0; y <= m - 1; y++ ) {

            for (int x = 0; x <= n - 1; x++) {

                if (mineArray[y][x] == 1) {

                    if ( y == 0 ) {

                        if (x == 0) {

                            if( n > 1 ) {

                                gridArray[y][x + 1]++;

                            }

                            if( m > 1 ) {

                                gridArray[y + 1][x]++;

                                if( n > 1 ) {

                                    gridArray[y + 1][x + 1]++;

                                }

                            }

                        } else if ((x > 0) && (x <= n - 2)) {

                            if( m > 1 ) {

                                gridArray[y + 1][x]++;

                                if( n > 1 ) {

                                    gridArray[y + 1][x + 1]++;
                                    gridArray[y + 1][x - 1]++;

                                }

                            }

                            if( n > 1 ) {

                                gridArray[y][x - 1]++;
                                gridArray[y][x + 1]++;

                            }

                        } else if (x == n - 1) {

                            if( n > 1 ) {

                                gridArray[y][x - 1]++;

                            }

                            if( m > 1 ) {

                                gridArray[y + 1][x]++;

                                if( n > 1 ) {

                                    gridArray[y + 1][x - 1]++;

                                }

                            }

                        }

                    } else if ((y > 0) && (y <= m - 2)) {

                        if (x == 0) {

                            if( m > 1 ) {

                                gridArray[y - 1][x]++;
                                gridArray[y + 1][x]++;

                                if( n > 1 ) {

                                    gridArray[y - 1][x + 1]++;
                                    gridArray[y + 1][x + 1]++;

                                }


                            }

                            if( n > 1 ) {

                                gridArray[y][x + 1]++;

                            }

                        } else if ((x > 0) && (x <= n - 2)) {

                            if( n > 1 ) {

                                gridArray[y][x - 1]++;
                                gridArray[y][x + 1]++;

                            }

                            if( m > 1 ) {


                                gridArray[y - 1][x]++;
                                gridArray[y + 1][x]++;

                                if( n > 1 ) {

                                    gridArray[y - 1][x - 1]++;
                                    gridArray[y - 1][x + 1]++;
                                    gridArray[y + 1][x + 1]++;
                                    gridArray[y + 1][x - 1]++;

                                }

                            }

                        } else if (x == n - 1) {

                            if( n > 1 ) {

                                gridArray[y][x - 1]++;

                            }

                            if( m > 1 ) {

                                gridArray[y - 1][x]++;
                                gridArray[y + 1][x]++;

                                if( n > 1 ) {

                                    gridArray[y - 1][x - 1]++;
                                    gridArray[y + 1][x - 1]++;

                                }

                            }

                        }

                    } else if (y == m - 1) {

                        if (x == 0) {

                            if( m > 1 ) {

                                gridArray[y - 1][x]++;

                                if( n > 1 ) {

                                    gridArray[y - 1][x + 1]++;

                                }

                            }

                            if( n > 1 ) {

                                gridArray[y][x + 1]++;

                            }

                        } else if ((x > 0) && (x <= n - 2)) {

                            if( m > 1 ) {

                                gridArray[y - 1][x]++;

                            }

                            if( n > 1 ) {

                                gridArray[y][x - 1]++;
                                gridArray[y][x + 1]++;

                                if( m > 1 ) {

                                    gridArray[y - 1][x - 1]++;
                                    gridArray[y - 1][x + 1]++;

                                }

                            }

                        } else if (x == n - 1) {

                            if( n > 1 ) {

                                gridArray[y][x - 1]++;

                            }

                            if( m > 1 ) {

                                gridArray[y - 1][x]++;

                                if( n > 1 ) {

                                    gridArray[y - 1][x - 1]++;

                                }

                            }

                        }

                    }

                }

            }

        }

        for( int y = 0; y <= m - 1; y++ ) {

            for( int x = 0; x <= n - 1; x++ ) {

                if( mineArray[y][x] == 1 ) {

                    System.out.print( "*");

                } else {

                    System.out.print( gridArray[y][x] );

                }

                if( x != n - 1 ) {

                    System.out.print( "  " );

                }

            }

            System.out.println();

        }

    }

}

I receive the following errors after submitting:

`Test 9: check that mines are uniformly random

• m = 1, n = 2, k = 1 [repeated 15000 times] value observed expected 2Oln(O/E) ------------------------------------------- 1-1 0 7500.0 0.00 1-2 15000 7500.0 20794.42 ------------------------------------------- 15000 15000.0 20794.42

  G-statistic = 20794.42 (p-value = 0.000000, reject if p-value <= 0.0001) Note: a correct solution will fail this test by bad luck 1 time in 10,000.

• m = 1, n = 3, k = 1 [repeated 15000 times] value observed expected 2Oln(O/E) ------------------------------------------- 1-1 0 5000.0 0.00 1-2 7624 5000.0 6432.57 1-3 7376 5000.0 5735.48 ------------------------------------------- 15000 15000.0 12168.05

  G-statistic = 12168.05 (p-value = 0.000000, reject if p-value <= 0.0001) Note: a correct solution will fail this test by bad luck 1 time in 10,000.

• m = 2, n = 2, k = 2 [repeated 15000 times] value observed expected 2Oln(O/E) ------------------------------------------- 1-1 0 7500.0 0.00 1-2 10044 7500.0 5867.15 2-1 9946 7500.0 5614.86 2-2 10010 7500.0 5779.41 ------------------------------------------- 30000 30000.0 17261.42

  G-statistic = 17261.42 (p-value = 0.000000, reject if p-value <= 0.0001) Note: a correct solution will fail this test by bad luck 1 time in 10,000.

• m = 2, n = 4, k = 3 [repeated 15000 times] value observed expected 2Oln(O/E) ------------------------------------------- 1-1 0 5625.0 0.00 1-2 6484 5625.0 1842.97 1-3 6477 5625.0 1826.99 1-4 6346 5625.0 1530.70 2-1 6439 5625.0 1740.49 2-2 6471 5625.0 1813.30 2-3 6435 5625.0 1731.41 2-4 6348 5625.0 1535.19 ------------------------------------------- 45000 45000.0 12021.05

  G-statistic = 12021.05 (p-value = 0.000000, reject if p-value <= 0.0001) Note: a correct solution will fail this test by bad luck 1 time in 10,000.

• m = 3, n = 3, k = 6 [repeated 15000 times] value observed expected 2Oln(O/E) ------------------------------------------- 1-1 0 10000.0 0.00 1-2 11257 10000.0 2665.77 1-3 11278 10000.0 2712.78 2-1 11313 10000.0 2791.31 2-2 11228 10000.0 2600.98 2-3 11289 10000.0 2737.44 3-1 11171 10000.0 2474.06 3-2 11180 10000.0 2494.07 3-3 11284 10000.0 2726.23 ------------------------------------------- 90000 90000.0 21202.65

  G-statistic = 21202.65 (p-value = 0.000000, reject if p-value <= 0.0001) Note: a correct solution will fail this test by bad luck 1 time in 10,000.

==> FAILED

Test 10: check statistical independence of mines within an m-by-n grid

• m = 500, n = 500, k = 125000
• m = 500, n = 500, k = 25000
• m = 500, n = 500, k = 225000

WARNING: the time limit of 60 seconds was exceeded, so not all tests could be completed.`

I already accounted for NOT handling above number of cell mines with my variable "totalMines" because I figured "Why not?" I'm very stumped right now. I come from a C++ hobbyist approach. I've seen other answers that use a table of m+2/n+2 values which, as a wannabe solo game dev, I would consider a VERY bad practice of doing. My personal belief is that you should only code what needs to be shown as it needs to be shown. So, no extra table elements. If that was done in C++ and compiled under the g++ compiler I would have to believe that, if uninitialized, those extra elements would default to garbage or NULL values and the program would SEGFAULT or interrupt. I am probably wrong, but I need help fixing my apparent wrong approach to the problem. Any help is GREATLY appreciated. I would like to NOT need to simplify this if it can be helped. I've been on this one single problem for almost two weeks and have worked about three/four hours a night for 5 nights a week on this. Thank you!

I cannot think of anything else besides simplifying the code, but that is not my intention.

EDIT 1: We cannot use any other random function besides a uniform distribution between 0 and n - 1 (0 being cell 1 and n being amount of cells) with Math.random(). I have seen answers by using a "grid" (int[][]) with two extra elements. As a wannabe game dev, I would not accept extra elements as an answer. Try doing that in C++ while not initializing all values to 0 first. I guess I am just not used to Java yet.

Answer 1

Here is how an old dog programmer might write it.

This approach differs significantly from the O/P's. I would have one grid. Each cell in the grid would have either an * for a mine, or a digit from 0 to 8 for a non-mine. The work of placing mines and counting mines in neighboring cells would operate on that grid.

First, I'd break the job into more methods, each method being smaller.

public class MineSweeper {    
   final static char ASTER = '*';

   public static char [][] createMineField
                  (int numRows, int numColumns, int numMines) {

      char [][] field = new char [numRows][numColumns];
      placeMines (field, numMines);
      setCounts (field);        
      return field;
 }

The method placeMines places the mines in an empty grid. setCounts sets the elements of the non-mine cells to indicate how many adjacent (orthogonal and diagonal) cells contain a mine.

Suppose we use this method for placing a mine:

1. Pick a row at random. Pick a column at random.
2. Check to see if there is collision. A collision occurs if there is already a mine at the row and column from step 1.
3. If there is a collision, go back to step 1.
4. Place the mine at the location.
5. Increment the count of mines placed.
6. If at least one more mine is needed, go to step 1.
7. Otherwise, we are finished with mine placement.

Suppose t is the total number of cells. That is t = number of rows multiplied by number of columns. Suppose m is the number of mines to be placed. When t is high, and the ratio m : t is high, this method has a potential problem: As more mines are placed, the more collisions there will be. This can slow the program. The following code always generates t random numbers, but avoids the collision problem. It seems wasteful if t is small, or the m : t ratio is low. But, it is guaranteed to avoid collisions:

public static void placeMines (char [][] grid, int numMines) {
    int size = grid.length * grid [0].length;
    int [] order = new int [size];
    for (int i = 0; i < size; i++) {
        order [i] = i;
    }
    shuffle (order);
    
    int r, c;
    for (int i = 0; i < numMines; i++) {
        r = order [i] / grid[0].length;
        c = order [i] % grid[0].length;
        grid [r][c] = ASTER;
    }
}
public static void shuffle (int [] arr) {
    Random rand = new Random ();
    int i, j, temp;
    for (i = arr.length - 1; i > 0; i--) {
        j = rand.nextInt (i + 1);
        temp = arr [j];
        arr [j] = arr [i];
        arr [i] = temp;
    }              
}

This generates the sequence 0 to t - 1 in an array, then shuffles the sequence. The first m elements of shuffled array are taken to position m mines.

Here is the code to fill in the rest of the grid:

public static void setCounts(char[][] grid) {
    int row, col, r, c, count;

    for (row = 0; row < grid.length; row++) {
        for (col = 0; col < grid[row].length; col++) {
            if (grid [row][col] == ASTER) { 
                continue;
            }

            count = 0;
            for (r = row - 1; r <= row + 1; r++) {
                for (c = col - 1; c <= col + 1; c++) {
                    if (    r >= 0           && c >= 0
                         && r <  grid.length && c < grid[row].length
                         && grid[r][c] == ASTER    ) {
                        count++;
                    }                            
                }
            }
            grid [row][col] = (char) ('0' + count);                
        }
    }
}

The O/P commented that he / she has not yet had a lesson with the char variable type. A char is a 16 bit Integer type, and is one of the primitive types. But, Java assumes these values represent 16 bit Unicode characters.

The line grid [row][col] = (char) ('0' + count); converts the count value, which contains a value from 0 to 8, to the corresponding Unicode decimal digit. This is similar to what can be done with ASCII in C, C++, and other characters.

If the O/P is not comfortable with using char, I suggest an int or short array instead. A mine might be represented with a "special" value outside that range, such as -1, 9, or 10.

     public static void main(String[] args) {
       System.out.println("Starting program with " + args.length + " args: "
        + Arrays.toString(args) + "\n");  
       char [][] game =  createMineField (15,30, 100);
       for (int k = 0; k < game.length; k++ ) { 
           System.out.println (Arrays.toString (game[k]));
       }                
     }    
 }

I hard coded a single test case. An array might be used to code multiple test cases.

In keeping with the original code, the O/P might need to parse args from main to get the values to use for a single test case each run, as in the O/P code. I also used a method from java.util.Arrays to quickly code output. The O/P will want to provide his / her own code to meet the requirements of the autochecker.

Sample output, with 15 rows, 30 columns, and 175 mines:

[3, *, *, 3, 1, 1, *, 3, *, 4, *, 3, 3, *, 4, *, *, 2, 3, *, 5, *, 4, 3, *, *, *, 3, *, 2]
[*, *, *, *, 3, 3, 3, 5, *, 4, *, 4, *, *, 6, *, 5, 3, *, *, *, *, *, *, 4, 4, 3, 4, *, 2]
[4, *, *, *, *, 3, *, *, 2, 3, 2, 5, *, 5, *, *, *, 4, 5, *, 7, 6, 6, 5, *, 2, 2, *, 2, 1]
[*, 6, *, 7, *, 4, 2, 3, 2, 2, *, 5, *, 4, 2, 4, *, *, 3, *, *, *, *, *, 4, *, 4, 3, 2, 0]
[3, *, *, 6, *, 4, 1, 3, *, 3, 2, *, *, 3, 1, 2, 3, 3, 2, 3, *, *, 4, 3, *, 5, *, *, 3, 1]
[*, 4, 4, *, *, 5, *, 5, *, 3, 2, 2, 4, *, 3, 2, *, 1, 0, 2, 4, 4, 3, 3, 4, *, *, *, *, 2]
[2, 3, *, 5, *, 7, *, *, 5, *, 2, 1, 2, *, *, 4, 3, 3, 1, 2, *, *, 3, *, *, 4, 5, *, *, 2]
[*, 4, 2, 3, *, *, *, *, *, 4, *, 1, 1, 3, 4, *, *, 5, *, 5, 5, 6, *, 4, 2, 2, *, 5, 4, 2]
[*, *, 3, 3, 3, 4, *, 4, 3, *, 4, 3, 2, 3, *, 5, *, *, *, *, *, *, *, 2, 0, 1, 3, *, *, 1]
[2, 3, *, *, 3, 2, 2, 3, 3, 3, *, *, 2, *, *, 3, 3, 5, 6, 5, 5, 4, 3, 2, 1, 2, 3, *, 4, 2]
[0, 1, 3, *, *, 1, 1, *, *, 3, 3, 2, 3, 3, 4, 3, 4, *, *, *, 3, *, 2, 2, *, 3, *, 4, 3, *]
[0, 0, 1, 2, 3, 2, 2, 2, 4, *, 4, 2, 2, *, 2, *, *, *, 5, 3, *, 3, 3, *, 3, 4, *, 4, *, 4]
[0, 1, 1, 2, 3, *, 4, 3, 4, *, *, *, 2, 2, 3, 3, 5, *, 4, 3, 4, *, 3, 3, *, 2, 1, 4, *, *]
[0, 1, *, 3, *, *, *, *, *, 4, 5, 4, 3, 2, *, 1, 2, *, 5, *, *, 6, *, 4, 2, 2, 0, 2, *, 3]
[0, 1, 1, 3, *, 4, 3, 3, 3, *, 2, *, *, 2, 1, 1, 1, 2, *, *, *, *, *, 3, *, 1, 0, 1, 1, 1]

I made all the methods static. Another approach would be to make the mine field an instance variable. The method createMineField could be replaced by a constructor. The methods placeMines and setCounts could be non-static, possibly non-public, instance methods.

It would be a good idea to verify the arguments. Check the number of rows and the number of columns fall within the allowed range. Also, put a constraint on the number of mines. Consider throwing and catching IllegalArgumentException for these.