Recursive Sudoku Solver

Question

I just finished up a program which takes a byte[9][9] as input and recursively does a DFS to find any solutions (including multiple solutions). I'm pretty happy with it and it works pretty quickly as far as I can tell. I'm mainly looking for advice on the algorithm I used and its efficiency, as well as the way I handled return values, but any advice is appreciated.

The algorithm:

1. Generate a byte[9][9] with each cell value representing the # of possible values that can be placed in that spot on the sudoku grid.
2. Check each cell in the possible values grid. If it is 1, then there is only one possible value - enter this into the sudoku grid.
3. If a value was changed in 2, repeat 1-2 with the updated possible values grid.
4. If the grid is full, it is solved; return it. If the grid has empty cells, but zero possible values, it is invalid; return an empty byte[1][1]. Otherwise, continue to 5.
5. Once there are no more 1's in the possible values grid, find a cell with the least possible values n (usually 2 or 3) and create n copies of the sudoku grid, filling in the cell of each with each of the possible values. Call the same function on each of these grid, and if the return value is not an empty byte[1][1], return it because it is the solution.

It seems very roundabout to have to return a byte[1][1] but I can't think of a better way to still satisfy the return type.

public byte[][] solve(byte[][] g) {
        byte[][] grid = twoDimensionalCopy(g);
        byte[][] numPossible = getNumPossible(grid);
        //  Fills cells where only one value is possible. 
        // If a new value is added at any point in the loop, repeats the loop until there are no cells with only one possible value.
        boolean valueAdded = false;
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                numPossible = getNumPossible(grid);
                if (numPossible[row][col] == 1) {
                    enterValue(getPossibleValues(row, col, grid).get(0), row,
                            col, grid);
                    valueAdded = true;
                }
            }
            // If at the end of the loop and a value was added, repeat.
            if (row == 8 && valueAdded) {               
                row = -1;
                valueAdded = false;
            }
        }
        // If the grid is full, then it must be a solution since all values added are first checked to be valid.
        if (isFull(grid)) {
            return grid;
        }
        else {
            for (int row = 0; row < 9; row++) {
                for (int col = 0; col < 9; col++) {
                    // If there exists an empty cell on the grid with no possible values, return an empty byte[][].
                    if (cellEmpty(row, col, grid)
                            && getPossibleValues(row, col, grid).size() == 0) {
                        return new byte[1][1];
                    }
                }
            }
            // If neither of the above cases works, find a cell with the least number of possible values.
            int lowestPossible = -1;
            int lowestRow = -1;
            int lowestCol = -1;
            for (int row = 0; row < 9; row++) {
                for (int col = 0; col < 9; col++) {
                    if ((lowestPossible == -1 && cellEmpty(row, col, grid))
                            || (numPossible[row][col] != 0 && numPossible[row][col] < lowestPossible)) {
                        lowestRow = row;
                        lowestCol = col;
                        lowestPossible = numPossible[row][col];
                    }
                }
            }

            ArrayList<Byte> pValues = getPossibleValues(lowestRow, lowestCol,   grid);    
            // For each of the possible values for the cell, enter the value in the grid and call the function again. Add all the results to the ArrayList, then return the ArrayList.
            for (byte pValue : pValues) {
                byte[][] newGrid = twoDimensionalCopy(grid);
                enterValue(pValue, lowestRow, lowestCol, newGrid);
                newGrid = solve(newGrid);
                if (newGrid[0][0] != 0){
                    return newGrid;
                }
            }           
        }
        return new byte[1][1];
    }




private byte[][] getNumPossible(byte[][] grid) {
    // Returns a byte[][] with cells representing the number of possible values for each cell.
}

private ArrayList<Byte> getPossibleValues(int row, int col, byte[][] grid) {
    // Returns an ArrayList with all the possible values for a given cell.
}
private boolean anyHas(int value, int row, int col, byte[][] grid) {
    // Returns true if a cell in the same row, column, or section has the same value as the given one. 
}

Answer 1

Avoid magic numbers

        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                numPossible = getNumPossible(grid);
                if (numPossible[row][col] == 1) {
                    enterValue(getPossibleValues(row, col, grid).get(0), row,
                            col, grid);
                    valueAdded = true;
                }
            }
            // If at the end of the loop and a value was added, repeat.
            if (row == 8 && valueAdded) {               
                row = -1;
                valueAdded = false;
            }
        }

In this code, you have three magic numbers: 9, 8, and -1. The start of a solution is the declaration of a constant, which would likely happen outside the current method but in the same class:

    private static final int BOARD_SIZE = 9;

Then you can use it like

        for (int row = 0; row < BOARD_SIZE || ! valueAdded; row++) {
            // If finished with the board and a value was added, repeat.
            if (row >= BOARD_SIZE) {               
                row = 0;
                valueAdded = false;
            }

            for (int col = 0; col < BOARD_SIZE; col++) {

Note that the valueAdded check moves into the row loop. This allows us to move the reset check to the beginning of the loop, eliminating two magic numbers: 8 (replaced by BOARD_SIZE) and -1. Setting row to 0 is clearer about what it is doing than setting it to -1 so that it could be incremented to 0.

A side effect of this is that the compiler has a chance to optimize out the second check. Note that row < BOARD_SIZE and row >= BOARD_SIZE are logical negations of each other. This may create a slight performance improvement, although it is unlikely to make a significant difference.

Also consider moving this section of code into its own method. This method is rather long. You could get this block of code down to a single line by abstracting it into a method that takes grid as a parameter. Note that you'd have to move the numPossible declaration after the method call.

An else is unnecessary after a return

        if (isFull(grid)) {
            return grid;
        }
        else {

Since you return in the if clause, you can leave off the else. The rest of the function will only be reached in the else case anyway. This saves you a level of indent.

Declare as the interface rather than the implementation

        ArrayList<Byte> pValues = getPossibleValues(lowestRow, lowestCol,   grid);

This works but makes your implementation difficult to modify. Unless you are using functionality limited only to that implementation, you should declare as the interface instead.

        List<Byte> pValues = getPossibleValues(lowestRow, lowestCol,   grid);

This will allow you to change the implementation without changing this declaration.

private ArrayList<Byte> getPossibleValues(int row, int col, byte[][] grid) {

Same thing here.

private List<Byte> getPossibleValues(int row, int col, byte[][] grid) {

Note that if you actually wanted to only return an ArrayList here, you could still change the first one. A List variable will always accept any object that implements the List interface.

You can actually go even more generic if you want.

        for (byte pValue : pValues) {

This can become

        for (byte pValue : getPossibleValues(lowestRow, lowestCol,   grid)) {

In which case you don't need the pValues variable.

You could declare a Grid class

It seems very roundabout to have to return a byte[1][1] but I can't think of a better way to still satisfy the return type.

The problem here is that you are using a primitive type. If you declare a Grid class and then have the method return a Grid object, you can return null on an invalid case. This would also allow you to move some operations into the Grid class. Consider if you want to make Grid implement Iterable so that you can use it in the for each form. Perhaps you don't want to engage in that level of engineering, but it does allow for some elegant solutions.