Valid Sudoku
You are given a 9 by 9 sudoku board as an array of 9 strings of 9 characters , where each character is a digit from 1 to 9 or a dot for an empty square. Return true if the board is valid. A board is valid when no digit repeats inside a row, inside a column, or inside a 3 by 3 box . Only the digits already written down are checked, and the board does not have to be solvable. Walk every square once. For each digit, build three short text keys that describe where it sits, and keep them all in one hash set. If a key is already in the set, that digit has been seen in the same row, column or box before, so the board is invalid.
Constraints
- board.length == 9 and every row is a string of length 9
- Each character is a digit 1 to 9 or the dot character
- Empty squares are ignored, and the board need not be solvable
Example
board rows = ["53..7....", "6..195...", ".98....6.", ... ]trueExplanation No digit is repeated in any row, any column or any 3 by 3 box, so the filled squares are a valid start.
In plain terms
- Hash set
- A bag of values that answers "have I stored this exact value already?" very quickly, and never keeps two copies of the same value.
- Composite key
- A key built by gluing several facts together into one piece of text, such as "row 0 has 5". Two squares clash only when they build the same key.
- 3 by 3 box
- One of the nine small squares a sudoku grid is divided into. The box of a square is found by dividing its row and column by 3 and dropping the remainder.
Each cell is a slot in the hash set, holding one seen key
The set starts empty. This walkthrough uses a row that begins 5, 3, dot, dot, 5.
What happens in this step
Row 0 of the board reads "53..5...." seen = empty Each square that holds a digit will add three keys. A dash means that slot of the set is still unused.
Steps to visualize
- The cells below are slots in the hash set. Each one holds a key such as r0:5, meaning "row 0 already has a 5".
- Walk the board square by square and skip every dot.
- For a digit, build three keys: one for its row, one for its column, one for its box.
- If any of the three keys is already in the set, the board is invalid and you stop.
- Otherwise store all three keys and move to the next square.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
The set starts empty. This walkthrough uses a row that begins 5, 3, dot, dot, 5.
What happens in this step
Row 0 of the board reads "53..5...." seen = empty Each square that holds a digit will add three keys. A dash means that slot of the set is still unused.
Solution
function isValidSudoku(board) {
const grid = board.map((row) => row.split(''));
const seen = new Set();
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
const value = grid[r][c];
if (value === '.') {
continue;
}
const rowKey = 'r' + r + ':' + value;
const colKey = 'c' + c + ':' + value;
const boxKey = 'b' + Math.floor(r / 3) + Math.floor(c / 3) + ':' + value;
if (seen.has(rowKey) || seen.has(colKey) || seen.has(boxKey)) {
return false;
}
seen.add(rowKey);
seen.add(colKey);
seen.add(boxKey);
}
}
return true;
}- Time
- O(1) because the board is always 81 squares
- Space
- O(1)
Test cases
| Input | Expected | Covers |
|---|---|---|
a valid partly filled board | true | example from the description |
the same board with the first square changed to 8 | false | two copies of 8 in the first column |
a board of nine rows of dots | true | no digits at all, so no rule can be broken |
a 1 at the start and the end of row 0 | false | clash in a row while the column and box are fine |
a 1 in column 0 of row 0 and row 3 | false | clash in a column while the row and box are fine |
a 1 at row 0 column 2 and row 1 column 0 | false | clash inside one 3 by 3 box while the row and column differ |