Java solution using brute-force search, backtracking and bitwise operations

• I solved this by using arrays to keep track of the available digits. There's one array for the rows, one for the columns and one for the squares.
For example, row[0] = 109 (001110101 in binary) means that digits 1, 3, 5, 6 and 7 have not yet been used in the first row.

With this approach, checking if a digit is available, updating the board and arrays and backtracking all take constant-time by using simple bitwise operations.

Then, I use a recursive method starting from the first cell. Also, I don't use any division or modulo operations to get the square indexes which is a little bit faster.

``````private static final int SIZE = 9;

private static final int SQR_SIZE = 3;

private static final int DBL_SQR_SIZE = 3 << 1;

public static void solveSudoku(char[][] board) {
// Each array contains the available digits in binary
// If the k-th bit is set to 1, it means the digit k+1 has not yet been used
int[] rows = new int[SIZE];
int[] cols = new int[SIZE];
int[] sqrs = new int[SIZE];
// Initialization. At first, the 9 digits are available
int allAvailable = -1 >>> 23;
for (int i = 0; i < SIZE; ++i) {
rows[i] = allAvailable;
cols[i] = allAvailable;
sqrs[i] = allAvailable;
}

// Remove the prefilled digits
for (int row = 0; row < SIZE; ++row) {
int sqrRow = (row < SQR_SIZE ? 0 : (row < DBL_SQR_SIZE ? 3 : 6));
for (int col = 0; col < SIZE; ++col) {
char cell = board[row][col];
if (cell == '.')
continue;
int cellBitmask = 1 << (cell - '1');
int sqr = sqrRow + (col < SQR_SIZE ? 0 : (col < DBL_SQR_SIZE ? 1 : 2));
// XOR removes the specified bit
}
}

// Start solving at the top-left corner
solveSudoku(board, rows, cols, sqrs, 0, 0);
}

private static boolean solveSudoku(char[][] board, int[] rows, int[] cols, int[] sqrs, int row, int col) {
// Correct coordinates if col is too big
if (col == SIZE) {
++row;
col = 0;
}
// Sudoku solved
if (row == SIZE)
return true;

// Cell already filled, directly solve the next one
if (board[row][col] != '.')
return solveSudoku(board, rows, cols, sqrs, row, col + 1);

// Compute square index
int sqr = (row < SQR_SIZE ? 0 : (row < DBL_SQR_SIZE ? 3 : 6))
+ (col < SQR_SIZE ? 0 : (col < DBL_SQR_SIZE ? 1 : 2));

// Brute-force search through all available values
for (int i = 0, bitmask = 1; i < SIZE; ++i, bitmask <<= 1) {
// If value is already used in the row or the column or the square, skip it
if (((rows[row] & bitmask) == 0) || ((cols[col] & bitmask) == 0) || ((sqrs[sqr] & bitmask) == 0))
continue;
// Value is available. Remove it from the available lists and update board
board[row][col] = (char) (i + '1');
// If a solution is found, returns with the board updated
if (solveSudoku(board, rows, cols, sqrs, row, col + 1))
return true;