1
Backtracking with constraint tables
Time Exponential in the worst case; fast in practice Space O(81)Precompute used[row][d], used[col][d], used[box][d]. Recursively fill cells in order; for an empty cell try digits not used in its row, column or box; return true when all cells are filled; undo on failure.
class Solution {
private final boolean[][] row = new boolean[9][10], col = new boolean[9][10], box = new boolean[9][10];
public void solveSudoku(char[][] board) {
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (board[r][c] != '.') mark(r, c, board[r][c] - '0', true);
solve(board, 0);
}
private boolean solve(char[][] b, int cell) {
if (cell == 81) return true;
int r = cell / 9, c = cell % 9;
if (b[r][c] != '.') return solve(b, cell + 1);
for (int d = 1; d <= 9; d++) {
if (row[r][d] || col[c][d] || box[(r / 3) * 3 + c / 3][d]) continue;
b[r][c] = (char) ('0' + d);
mark(r, c, d, true);
if (solve(b, cell + 1)) return true;
mark(r, c, d, false);
b[r][c] = '.';
}
return false;
}
private void mark(int r, int c, int d, boolean v) {
row[r][d] = v;
col[c][d] = v;
box[(r / 3) * 3 + c / 3][d] = v;
}
}Verdict: Solves typical puzzles in milliseconds.