rows[r]
cols[c]
squares[sq]
public boolean isValidSudoku(char[][] board) { Set<Character>[] cols = new HashSet[9]; Set<Character>[] rows = new HashSet[9]; Set<Character>[] squares = new HashSet[9]; // r / 3 * 3 + c / 3 for (int i = 0; i < 9; i++) { cols[i] = new HashSet<>(); rows[i] = new HashSet<>(); squares[i] = new HashSet<>(); } for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { char v = board[r][c]; if (v == '.') { continue; } int sq = r / 3 * 3 + c / 3; if (rows[r].contains(v) || cols[c].contains(v) || squares[sq].contains(v)) { return false; } cols[c].add(v); rows[r].add(v); squares[sq].add(v); } } return true;}
- r, c
- —
- board[r][c]
- —
- box
- —
- digits checked
- 0
Why it works
- Brute force checks each of the 27 units separately: 9 rows, 9 columns and 9 boxes, each scanned for repeats. Fine for a fixed 9 × 9 board, but it reads every cell three times in three different loops.
- One pass, three memories. Each filled cell belongs to exactly one row, one column and one box, so keep a set per unit. A digit already in any of its three sets is a repeat; otherwise add it to all three. Box index
r / 3 * 3 + c / 3(integer division) maps each cell to its 3 × 3 block. - Complexity: 81 cells, O(1) set work each: O(81) = O(1) for a fixed board, O(n²) for an n × n one. The 27 sets hold at most 3 × 81 digits.
- Pitfall: this checks the rules, not solvability. A board with no repeats can still be impossible to finish, and it is still valid here. Also skip
"."before testing, or every empty cell would clash with the first one. - Bit trick: replace each set with a 9-bit mask:
bit = 1 << digit, test with&, add with|=. Related: Sudoku Solver (37) uses the same three lookups to prune its backtracking.