Minesweeper algorithm that works within O(1) space complexity

Question

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>();
 neighbors.add(new Pos(cur.x - 1, cur.y));
 neighbors.add(new Pos(cur.x + 1, cur.y));
 neighbors.add(new Pos(cur.x, cur.y - 1));
 neighbors.add(new Pos(cur.x, cur.y + 1));
 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

• Franky: 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".
• JS1: 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.

Answer 1

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.

• Michael Ran: 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.
• Michael Ran: 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!