Sudoku solver recursive backtrack in Java

Question

I am implementing recursive backtracking algorithm for sudoku. Below is the code to create board with random filling. I wonder if I can make it better in any terms of readable coding especially validation methods. in Board class.

public class Board {
private int[][] board;
public final static int SIZE = 9;

public Board() {
    create();
}

public int[][] getBoard() {
    return board;
}

private void create() {
    int openspots = 20;
    board = new int[SIZE][SIZE];
    Random rand = new Random();
    int random, randomrow, randomcolumn;

    while (openspots-- > 0) {
        random = rand.nextInt(SIZE) + 1;
        randomrow = rand.nextInt(SIZE);
        randomcolumn = (rand.nextInt(SIZE));

        if (board[randomrow][randomcolumn] == 0) {
            board[randomrow][randomcolumn] = random;
            int count = 0;

            while (!isValid(randomrow, randomcolumn)) {
                if (count++ == 9) {
                    board[randomrow][randomcolumn] = 0;
                    openspots++;
                    break;
                }

                random = rand.nextInt(SIZE) + 1;
                board[randomrow][randomcolumn] = random;
            }
        }
    }
}

public void printBoard() {
    for (int row = 0; row < SIZE; row++) {
        for (int column = 0; column < SIZE; column++) {
            System.out.print(board[row][column] + " ");
        }
        System.out.println();
    }
}

public boolean isValid(int row, int column) {
    return isValidRow(row) && isValidColumn(column) && isValidBlock(row, column);
}

private boolean isValidRow(int row) {
    if (row > 8 || row < 0)
        throw new IllegalArgumentException("Row must be between 0 and " + (SIZE - 1) + " inclusive!");

    Set<Integer> set = new HashSet<>();

    for (int i = 0; i < SIZE; i++) {
        if (board[row][i] != 0 && set.contains(board[row][i])) {
            return false;
        } else {
            set.add(board[row][i]);
        }
    }

    return true;
}

private boolean isValidColumn(int column) {
    if (column > 8 || column < 0)
        throw new IllegalArgumentException("Column must be between 0 and " + (SIZE - 1) + " inclusive!");

    Set<Integer> set = new HashSet<>();

    for (int i = 0; i < SIZE; i++) {
        if (board[i][column] != 0 && set.contains(board[i][column])) {
            return false;
        } else {
            set.add(board[i][column]);
        }
    }

    return true;
}

private boolean isValidBlock(int row, int column) {
    if (column > 8 || column < 0)
        throw new IllegalArgumentException("Column must be between 0 and " + (SIZE - 1) + " inclusive!");

    int blockrow = (row / 3) * 3;
    int blockcolumn = (column / 3) * 3;

    Set<Integer> set = new HashSet<>();

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[blockrow + i][blockcolumn + j] != 0 && set.contains(board[blockrow + i][blockcolumn + j])) {
                return false;
            } else {
                set.add(board[blockrow + i][blockcolumn + j]);
            }
        }
    }

    return true;
}
}

The one below is the solver class which has the main algorithm to solve sudoku.

public class Solver {

public boolean solve(Board board) {
    int[][] boardarr = board.getBoard();

    for (int i = 0; i < board.SIZE; i++) {
        for (int j = 0; j < board.SIZE; j++) {
            if (boardarr[i][j] == 0) {
                for (int k = 1; k <= board.SIZE; k++) {
                    boardarr[i][j] = k;
                    if (board.isValid(i,j) && solve(board)) {
                        return true;
                    }
                    boardarr[i][j] = 0;
                }
                return false;
            }
        }
    }

    return true;
}
}

Answer 1

Object Orientated Programming

you don't use object orientated programming! that would clean up the code in a large scale

public class Board {
    //private int[][] board; primitive obsession - use objects instead
    private Field[][] fields;
    private Column[] columns;
    private Row[] rows;
    private Block[] blocks;
    public final static int SIZE = 9;  

    ...      
}

you could provide the proper methods for the field - so you could easily represent the field - instead of trying to interpret an int value.

you could provide methods that are specific for these objects - you could even define an interface for common code, like isFieldValid(Field candidate) for Row, Column and Block

Naming

consider these names and you might find better

Random rand = new Random();
int random, randomrow, randomcolumn;

maybe it would be

Field candidate;

again here, in Java we don't use the hungarian notation and name a variable by it's type:

//int[][] boardarr = board.getBoard();
int[][] board = board.getBoard(); //would be better
Field[][] fields = board.getFields(); //even more better

Data Structure

if you would use Objects for your Sudoku-Solver you could re-use values (here an example snippet for Block)

class Block {
    final private Set<Field> fields = new HashSet<>();

    boolean isFieldValid(Field field) {
        //Set<Integer> set = new HashSet<>(); we already have such set 
        //and don't need to create a new one whenever we check
        return !fields.contains(field);
    }
}

Magic numbers

you already provide a SIZE = 9 constant - so why don't you use a proper one for the block size?

int blockrow = (row / 3) * 3;
int blockcolumn = (column / 3) * 3;

Testing

i assume you provide enough tests but just don't put these in the question

Summary

very nice piece of code - i'm glad you have posted it here! The algorithm seems straight forward, i like it! The OO-thing is the only flaw here. I would appreciate if you would provide another question with applied OOP!

Answer 2

A small side note: in create(), you wrote

int openspots = 20;
// ...
while (openspots-- > 0) {
// ...
}

While it looks clean, it's weird to read and should probably be written as a for-loop. This way, you also reduce the scope of openspots to inside the loop and don't clutter up your namespace inside of create(). Also, the twenty seems a bit like a magic number to me, you shold probably put it into a constant. This would make the loop look something like this:

for (int openspots = CONST - 1; openspots >= 0; openspots--) {
// ...
}