# Minesweeper algorithm that works within O(1) space complexity

For minesweeper algorithm, instead of the most obvious BFS or DFS solution, I want a O(1) space solution.

First of all, I'll explain how the program works. I will pass in a 2D array, with 1 represent mine and 0 represent blank space. The program return true if the map can be opened with single click. Return false if it cannot. Example:

0, 0, 0, 1, 0
0, 1, 1, 1, 1
0, 0, 0, 0, 1
0, 1, 1, 0, 1
0, 0, 1, 0, 1

should return false

0, 0, 0, 0, 0
0, 1, 1, 1, 1
0, 0, 0, 0, 1
0, 1, 1, 0, 1
0, 0, 1, 0, 1

should return true

My algorithm is to visit each 0s and mark as 2. Than from that point, I continue to visit all the 0s and mark as 2. When there's no more 0s, I will visit 2s and then mark 2s as 3s. In the end, all 0s should be marked as 3 if they are inter-connected. Example:

0, 0, 1
0, 1, 1
0, 0, 1
|
v
2, 0, 1
0, 1, 1
0, 0, 1
|
v
2, 2, 1
0, 1, 1
0, 0, 1
|
v
2, 3, 1
0, 1, 1
0, 0, 1
|
v
2, 3, 1
2, 1, 1
0, 0, 1
|
v
2, 3, 1
2, 1, 1
2, 0, 1
|
v
2, 3, 1
2, 1, 1
2, 2, 1
|
v
2, 3, 1
2, 1, 1
2, 3, 1
|
v
2, 3, 1
2, 1, 1
3, 3, 1
|
v
2, 3, 1
3, 1, 1
3, 3, 1
|
v
3, 3, 1
3, 1, 1
3, 3, 1
|
v
return true, since there's no more 0 in the graph

This is my code followed by 3 test cases. Kindly help me review the coding structure/styles or tell me if I have considered all possible test cases. Thanks!

import java.util.ArrayList;
import java.util.List;

public class MineSweeperAlgorithm {

// this minesweeper algorithm uses O(1) space complexity

// set verbose to false to hide the step-by-step loggging
private static final boolean verbose = true;
private static int stepCount = 1;

public static void main(String[] args) {
MineSweeperAlgorithm ins = new MineSweeperAlgorithm();

int[][] matrix;
// make a test case
stepCount = 1;
matrix = new int[5][];
matrix[0] = new int[]{0, 0, 0, 1, 0};
matrix[1] = new int[]{0, 1, 1, 1, 1};
matrix[2] = new int[]{0, 0, 0, 0, 1};
matrix[3] = new int[]{0, 1, 1, 0, 1};
matrix[4] = new int[]{0, 0, 1, 0, 1};

// run the test
System.out.println("Result is " +
ins.validate(matrix, matrix.length, matrix[0].length));
System.out.println();

// make another test case
stepCount = 1;
matrix = new int[5][];
matrix[0] = new int[]{0, 0, 0, 1, 0};
matrix[1] = new int[]{0, 1, 0, 1, 0};
matrix[2] = new int[]{0, 1, 0, 1, 0};
matrix[3] = new int[]{0, 1, 0, 1, 0};
matrix[4] = new int[]{0, 1, 0, 0, 0};

// run the test
System.out.println("Result is " +
ins.validate(matrix, matrix.length, matrix[0].length));
System.out.println();

// make another test case
stepCount = 1;
matrix = new int[5][];
matrix[0] = new int[]{0, 0, 0, 1, 0};
matrix[1] = new int[]{0, 1, 1, 1, 0};
matrix[2] = new int[]{0, 1, 0, 1, 0};
matrix[3] = new int[]{0, 0, 0, 1, 0};
matrix[4] = new int[]{0, 1, 0, 0, 0};

// run the test
System.out.println("Result is " +
ins.validate(matrix, matrix.length, matrix[0].length));
System.out.println();
}

public boolean validate(int[][] matrix, int m, int n) {
Pos nextStep = findZero(matrix, m, n);
if (nextStep == null) {
// the matrix deos not contain 0
return false;
}

// visit the first position, and go from there
matrix[nextStep.x][nextStep.y] = 2;
while (nextStep != null) {
nextStep = step(matrix, nextStep, m, n);
}

// after visiting all positions, check if there is remaining 0s
return findZero(matrix, m, n) == null;
}

Pos step(int[][] matrix, Pos cur, int m, int n) {
// Now cur is located at a pos with value = 2
// print matrix in "verbose" mode
if (verbose) {
System.out.println("Step #" + stepCount++);
for (int[] array : matrix) {
for (int num : array) {
System.out.print(num + " ");
}
System.out.println();
}
System.out.println();
}

// make a list of valid neighbors, for the convenience of checking
List<Pos> neighbors = new ArrayList<Pos>();
for (int i = neighbors.size() - 1; i >= 0; i--) {
if (!isValidPos(neighbors.get(i), m, n)) {
neighbors.remove(i);
}
}

// check if there is adjacent 0,
// if there is, mark 0 as 2 and return that position
for (Pos neighbor : neighbors) {
if (matrix[neighbor.x][neighbor.y] == 0) {
matrix[neighbor.x][neighbor.y] = 2;
return neighbor;
}
}

// if no adjacent 0, then check if there is adjacent 2.
// if there is, mark current as 3 and then return that position
for (Pos neighbor : neighbors) {
if (matrix[neighbor.x][neighbor.y] == 2) {
matrix[cur.x][cur.y] = 3;
return neighbor;
}
}

//if no adjacent 0 and no adjacent 2, mark current as 3 and return null
matrix[cur.x][cur.y] = 3;
return null;
}

boolean isValidPos(Pos p, int m, int n) {
return p.x >= 0 && p.x < m && p.y >= 0 && p.y < n;
}

Pos findZero(int[][] matrix, int m, int n) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
return new Pos(i, j);
}
}
}
return null;
}

class Pos {
int x;
int y;

public Pos(int a, int b) {
x = a;
y = b;
}
}
}

The code is also available online for viewing or checking execution result at http://ideone.com/wmryWn

• The examples above are not opened with a single click. All cells with a 0 have mines as neighbors, are not labelled 0 and therefore do not trigger an "open all neighbors". Apr 16, 2015 at 5:58
• It seems as if you are solving a graph connectivity problem or even a "flood fill" problem. But I wouldn't exactly call it a minesweeper problem because the standard minesweeper game doesn't work that way.
– JS1
Apr 16, 2015 at 8:43

## Bug

Your program failed with this input:

matrix[0] = new int[]{0, 0, 1, 1, 1};
matrix[1] = new int[]{0, 1, 1, 1, 1};
matrix[2] = new int[]{0, 1, 0, 0, 1};
matrix[3] = new int[]{0, 0, 0, 0, 1};
matrix[4] = new int[]{0, 0, 0, 0, 1};

You can see the result here at ideone.

The reason for the failure is that your backtracking (following the 2's) is susceptible to running itself into a dead end. I'm not convinced that you can ever get your current method to work for all test cases.

## Is it really O(1) space?

Since you are storing integers into your matrix, I'm not sure I would call that an O(1) space solution. If you stored a direction into each cell as you passed through it, you could easily implement a DFS that way. So I believe your solution is really O(N) space.

• You're right. The test case won't pass because the traverse goes into a dead-end. Thanks very much for pointing out! I will check my code in a while. Apr 17, 2015 at 3:44
• About O(1) space, I mean the extra space used in the algorithm is only the "List<Pos> neighbors" wihch is only 4 item. The 2D matrix is given as input, so it's not counted as a space usage. Let me know your thoughts! Apr 17, 2015 at 3:46