Start learning free

LESSON 325 OF 576 · HASH TABLE

Valid Sudoku in Rust: One HashSet per Row, Column and Box

Practice O(81) Read the full explanation

A Sudoku board is a 9 x 9 grid of cells. Each cell holds a digit from '1' to '9', or '.' while it is empty. Rows 0-2, 3-5 and 6-8 and columns 0-2, 3-5 and 6-8 split the board into nine 3 x 3 boxes.

Given a partly filled board, return true if it is valid so far, and false otherwise. The board is valid when no digit appears twice:

  1. in the same row,
  2. in the same column,
  3. in the same 3 x 3 box.

Only the filled cells are checked; empty cells don't count. A valid board doesn't have to be solvable: you check the digits already on it, you don't solve the puzzle.

Rows are numbered from 0 at the top and columns from 0 at the left. In the examples, each line is one row of the board.

 

Example 1:



Input: board =
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Output: true
Explanation: No row, column or box holds the same digit twice.

Example 2:

Input: board =
83..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Output: false
Explanation: The board of Example 1 with an 8 instead of the 5 in the top left corner.
Column 0 now holds two 8s, in rows 0 and 3, and so does the top left box, in rows 0 and 2.

Example 3:

Input: board =
12345678.
.........
.........
.........
........9
.........
.........
.........
.........
Output: true
Explanation: No digit repeats, so the board is valid, although it has no solution:
the last cell of row 0 can only be a 9, and column 8 already has a 9 in row 4.

 

Constraints:

  • The board has 9 rows, and each row has 9 cells.
  • Each cell holds a digit from '1' to '9' or '.'.

Note:

Your algorithm should look at each cell once and check it in constant time: O(81) time and O(81) extra space for the 81 cells. Scanning the row, the column and the box of every cell again would also work on a board this small, but it looks at each cell many times.

STEP 1 OF 11
    Ctrl + Enter to check

    RUST · HASH TABLE

    Valid Sudoku in Rust, explained

    Problem overview

    The function is_valid_sudoku receives a 9 x 9 board as a Vec<Vec<char>>. Each cell holds a digit from '1' to '9', or '.' when it is empty. The board is valid when no digit appears twice in the same row, the same column or the same 3 x 3 box. Only filled cells count, and the board does not have to be solvable: the function only checks the digits that are already there.

    The first example is a partly filled board with no repeated digit, so the result is true. Replace its top-left 5 with an 8 and the result is false, because column 0 now holds two 8s (rows 0 and 3) and so does the top-left box.

    The third example shows why "valid" is not "solvable". Row 0 holds the digits 1 to 8 and a lone 9 sits in row 4, column 8. The last cell of row 0 could then only be a 9, but column 8 already has one, so the puzzle has no solution. No digit repeats, though, so the function returns true.

    Approach: remember what each row, column and box has seen

    The slow way rescans the row, the column and the box of every cell. The lesson asks for one visit per cell with a constant-time check. For that, keep a set of seen digits for each of the 9 rows, each of the 9 columns and each of the 9 boxes, 27 sets in all. Every cell belongs to exactly one row, one column and one box. When a filled cell is visited:

    • If its digit is already in any of its three sets, it is a repeat, so return false.
    • Otherwise add the digit to all three sets and go on.

    Each cell is compared with the cells visited before it, so every pair of cells that shares a row, column or box is compared exactly once.

    Numbering the boxes

    The cell at row r and column c lies in box row r / 3 and box column c / 3. Number the boxes left to right and then top to bottom, and the box index is (r / 3) * 3 + c / 3. Integer division drops the remainder, so 7 / 3 is 2, not 2.33. Some examples:

    cell (0,0) box 0
cell (2,3) box 1
cell (4,7) box 5
cell (8,8) box 8

    Step by step

    1. Create the row sets. rows is a Vec<HashSet<char>> of nine empty sets, built with vec![HashSet::new(); 9]. rows[r] holds the digits seen so far in row r.
    2. Create cols and boxes the same way: 27 sets in total, one per row, column and box.
    3. Visit every cell row by row with an outer loop for r over 0..9 and an inner loop for c over 0..9.
    4. Read the cell into digit.
    5. Skip empty cells. If digit == '.', continue to the next cell. Empty cells never break a rule.
    6. Compute box_index with the formula above. The name avoids box, which is a reserved word in Rust.
    7. Look for a repeat. If rows[r], cols[c] or boxes[box_index] already contains the digit, return false. contains takes a reference, so pass &digit.
    8. Record the digit in all three sets with insert, so later cells in the same row, column or box can find it.
    9. Finish with true after both loops, without a semicolon. Every filled cell was checked against the ones before it and none repeated.

    The solution in Rust

    impl Solution {
    fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
        let mut rows: Vec<HashSet<char>> = vec![HashSet::new(); 9];
        let mut cols: Vec<HashSet<char>> = vec![HashSet::new(); 9];
        let mut boxes: Vec<HashSet<char>> = vec![HashSet::new(); 9];
        for r in 0..9 {
            for c in 0..9 {
                let digit = board[r][c];
                if digit == '.' {
                    continue;
                }
                let box_index = (r / 3) * 3 + c / 3;
                if rows[r].contains(&digit) || cols[c].contains(&digit) || boxes[box_index].contains(&digit) {
                    return false;
                }
                rows[r].insert(digit);
                cols[c].insert(digit);
                boxes[box_index].insert(digit);
            }
        }
        true
    }
}

    The Rust details worth a closer look:

    • vec![HashSet::new(); 9] clones. The vec![value; n] form makes n clones of the value, so it needs a type that implements Clone, and HashSet does. Each clone is a separate set: inserting into the first one leaves the others empty. After v[0].insert('x') on such a vector of three sets, the sizes are 1, 0 and 0.
    • The type annotations. HashSet::new() alone doesn't say what the sets hold. The annotation Vec<HashSet<char>> tells the compiler, which is why the declarations carry it.
    • char cells. A board cell is a char, written with single quotes, so digit == '.' compares characters. The digits stay characters; nothing here needs their numeric value.
    • Indexing with usize. r and c come from 0..9 and are used to index vectors, so they are usize, and so is box_index.
    • || short-circuits. If the row set already contains the digit, the column and box sets are not even consulted.
    • Early return. The first repeat ends the function, so a bad board is rejected as soon as the second copy is visited.

    Complexity

    Time: O(81), a constant. The loops visit 81 cells, and each visit does a few set lookups and inserts that take constant time on average. Because the board size is fixed, this is the same as O(1). The point is that each cell is looked at once rather than once for every cell sharing its row, column or box.

    Space: O(81). The 27 sets hold at most 81 digits between them, since each filled cell is stored three times at most, once per kind of group.

    Edge cases and common mistakes

    • A repeat in one kind of group only. A board can repeat a digit in a box without repeating it in any row or column. With a 5 at row 0, column 0 and another 5 at row 2, column 2, the function returns false because of the box alone. A repeat in only a row, or only a column, is caught by the matching set in the same way.
    • Treating '.' as a digit. Without the continue, the second empty cell in a row would look like a repeat. An empty board of 81 dots must return true.
    • Wrong box formula. r / 3 + c / 3 maps different boxes to the same number. The box row must be multiplied by 3.
    • Forgetting to insert. A check without the three insert calls never finds anything and always returns true.
    • Checking solvability. The function never tries to complete the board. The third example is valid even though it has no solution.
    • Passing a value instead of a reference. contains(digit) doesn't compile. The compiler reports mismatched types, expected `&char`, found `char`, and suggests borrowing with &digit.

    Testing

    • The first example board returns true.
    • The same board with an 8 in the top-left corner returns false.
    • Row 0 set to 12345678. with a single 9 at row 4, column 8 returns true.
    • A board of 81 dots returns true.
    • Two 5s at row 0, column 0 and row 2, column 2 return false (same box).
    • Two 7s in row 4, at columns 0 and 8, return false (same row).
    • Two 9s in column 4, at rows 0 and 8, return false (same column).
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free