Snakes and Ladders using a magic die

Question

This is a problem from here where you're given a magic die, and the objective is to find the minimum number of dice throws (hops) to go from the start point to the end of the board, and win the game.

I am representing the board as a matrix as follows. If the value at a cell is 0, you could go to any of the next 6 places using your magic die. If the value at a cell is non-zero, you compulsorily have to go to the cell that is represented by the value (think there is a snake or ladder at that cell which is taking you to the cell represented by the value). For example, if you land at (0,1), you are forced to go to 11, which is (2,1).

int[][] a = {
                     {0,11,0,0,0},
                     {0,0,0,0,0},
                     {0,0,1,23,0},
                     {0,0,4,0,0},
                     {10,0,0,0,0}
        };

Background

I have implemented this using Depth First Search / Recursion. Someone who reviewed my code said this solution is incorrect, and this problem is not a good candidate for Depth First Search / Recursion, and can only be done by using Breadth First Search, the reason being that, there are cells which are interdependent on each other. For example, this is a valid path, (0,0) -> (0,1) -> (2,1) -> (2,2) -> (0,1). However, you are trying to find the minimum number of hops from each cell, and here, (0,1) depends on (2,1) which in turn depends on (0,1).

I am not completely sure this is a valid argument, since if you go from (0,1) to (2,1), there is no reason, to go back to (0,1) since it anyways cannot be the shortest path, since if you go back, you're basically going back to a point you previously were in except that you have made two more hops. So, this is not useful, and I have handled this by using a visited[][] state to capture that.

public class SnakesAndLadders {

    /**
     * @param args
     */
    public static void main( String[] args ) {
        // TODO Auto-generated method stub
        int[][] a = {
                     {0,11,0,0,0},
                     {0,0,0,0,0},
                     {0,0,1,23,0},
                     {0,0,4,0,0},
                     {10,0,0,0,0}
        };
        boolean[][] visited = new boolean[a.length][a[0].length];

        System.out.println( shortestPath( a, 0, 0, visited ) );
    }

    static int shortestPath(int[][] a, int i, int j, boolean[][] visited)
    {
        if(i >= a.length || j >= a[0].length)
            return Integer.MAX_VALUE-100;

        if( i == a.length-1 && j == a[0].length-1)
            return 0;

        if(visited[i][j] == true )
            return Integer.MAX_VALUE-100;

        visited[i][j] = true;
        int min = Integer.MAX_VALUE-100;
        if(a[i][j] == 0)
        {
            int pos = i*a[0].length + j;    
            for(int k = pos+1;k<=pos+6;k++)
            {
                min = Math.min( min, shortestPath( a, k/a[0].length, k%a[0].length, visited ) + 1) ;
            }

        }
        else
            return shortestPath( a, a[i][j]/a[0].length, a[i][j]%a[0].length, visited ) + 1;

        visited[i][j] = false;
        return min;
    }
}

Please review my code, and give me your thoughts on whether this would work, or if depth first search cannot be used for this class of problems where you could go back to a previous recursion state.

Answer 1

I don't believe your depth-first approach is incorrect, as far as I can tell your visited variable does its job. However, there is room for improvement.

General improvents to readability
Firstly, this game's board can be represented by a linear tape of cells, rather than a two-dimensional grid. Using a one-dimensional array greatly simplifies the code. Only one position variable will be passed around instead of two. Additionally, the translation steps between coordinate systems that you're currently making (e.g.: int pos = i*a[0].length + j;) are eliminated.

Likely bugs
The aim is to count the minimum number of dice rolls, but you're also incrementing min when you use a snake or ladder. I think you should remove the + 1 in the else branch.

You're currently using the magic number 100, here: Integer.MAX_VALUE-100. There is no explanation as to where this 100 comes from, why it needs to be exactly that number. I assume it's to prevent interger wrapping when taking a sum. However, this exposes you to bugs. What if you use this program on a larger board that has paths longer than a 100 rolls? Your program now thinks the most optimum route is done in negative two billion rolls.

The current implementation assigns a special meaning to the value zero (no snake or ladder). However, position zero is a valid cell. This means that there is no way for a snake to point towards the cell at zero! One workaround would be to change the default value to -1.

Nitpicks
I recommend always using brackets with conditional blocks, even if there's just one line. Read this for more information.