Start learning free

LESSON 317 OF 568 · HASH TABLE

Valid Sudoku in C++: One Pass with unordered_set

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

    C++ · HASH TABLE

    Valid Sudoku in C++, explained

    Problem overview

    The method isValidSudoku receives a 9 x 9 board of characters. Each cell holds a digit from '1' to '9' or '.' for an empty cell. The method returns true when no digit appears twice in the same row, the same column or the same 3 x 3 box, and false otherwise.

    Only the filled cells matter. The task is to validate the digits already on the board, not to solve the puzzle, so a board can be valid even if it has no solution. In the third example, the first row holds 1 to 8 and the last cell of that row could only be a 9, but column 8 already has a 9 lower down. No digit repeats, so the answer is still true.

    The second example takes the board of the first one and puts an 8 in the top left corner. That 8 clashes with the 8 in row 3 of column 0, and with the 8 in row 2 of the same box, so the answer is false.

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

    One way is to rescan the row, the column and the box of every filled cell. On a board this small that still works, but each cell is looked at many times. A better way is to visit every cell once and keep a record of the digits seen so far in each row, each column and each box.

    That is 27 sets: nine for rows, nine for columns, nine for boxes. Every cell belongs to exactly one row, one column and one box. When a filled cell arrives, check whether its digit is already in the sets of its row, column or box. If it is, the digit appears twice and the board is invalid. If not, add the digit to the three sets and move on.

    Because each set only answers "is this digit in here?", an unordered_set<char> fits: a lookup takes constant time on average.

    Finding the box number

    The boxes are numbered 0 to 8, left to right and then top to bottom. For the cell in row r and column c, r / 3 is the box's row (0, 1 or 2) and c / 3 is its column. The box number is (r / 3) * 3 + c / 3. For the cell at row 4, column 7, that is 1 * 3 + 2 = 5. Integer division drops the remainder, so 7 / 3 is 2, not 2.33.

    The multiplication by 3 matters. Along row 0 the formula gives the box numbers 0 0 0 1 1 1 2 2 2, and down column 0 it gives 0 0 0 3 3 3 6 6 6. Adding the two quotients without it, r / 3 + c / 3, gives 2 for the cell (0, 6), 2 for (6, 0) and 2 for (3, 3), while the correct formula gives 2, 6 and 4. Different boxes would share one set and report repeats that are not there.

    Step by step

    1. Create the row sets. rows is a vector<unordered_set<char>> of size 9. Giving the vector a size creates nine empty sets, and rows[r] will hold the digits seen in row r.
    2. Create cols and boxes the same way, nine empty sets each.
    3. Loop over the rows with r from 0 to 8.
    4. Loop over the columns of that row with c from 0 to 8. Together, the two loops visit all 81 cells.
    5. Read the cell into a char named digit.
    6. Skip empty cells. If digit is '.', continue with the next cell: empty cells never break a rule.
    7. Compute the box number with the formula above.
    8. Look for a repeat. If rows[r], cols[c] or boxes[box] already counts the digit, return false. The three count checks are joined with ||. On a set, count is 1 when the value is present and 0 when it isn't.
    9. Record the digit in rows[r] with insert, so later cells of the same row see it.
    10. Record it in cols[c] and boxes[box] too.
    11. Return true after both loops. Every filled cell was compared with all the cells visited before it in its row, column and box, and none repeated a digit.

    The solution in C++

    class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<unordered_set<char>> rows(9);
        vector<unordered_set<char>> cols(9);
        vector<unordered_set<char>> boxes(9);
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char digit = board[r][c];
                if (digit == '.') continue;
                int box = (r / 3) * 3 + c / 3;
                if (rows[r].count(digit) || cols[c].count(digit) || boxes[box].count(digit)) {
                    return false;
                }
                rows[r].insert(digit);
                cols[c].insert(digit);
                boxes[box].insert(digit);
            }
        }
        return true;
    }
};

    Some C++ details worth knowing:

    • vector<unordered_set<char>> rows(9) builds nine empty sets in one go. Using count to test membership does not change the set. That is different from operator[] on a map, which inserts a default value for a missing key.
    • Digits stay characters. The sets hold char values such as '5', not numbers, so the code never converts them. Comparing with '.' uses a character literal in single quotes; a string in double quotes would not compile against a char.
    • The board is passed by reference. vector<vector<char>>& board avoids copying all 81 cells. The code only reads from it.
    • Early exit. return false inside the nested loops leaves both loops and the method at once, so there is no need for a flag.

    Complexity

    Time: O(81). Each of the 81 cells is visited once and costs a few constant-time set operations. Since the board size is fixed, this is constant time. For a board of side n, the same method would take O(n²).

    Space: O(81). Each filled cell adds its digit to three sets, so the sets hold at most 3 * 81 entries.

    Edge cases and common mistakes

    • An empty board. Nine rows of ......... are valid: nothing is filled, so nothing repeats.
    • A repeat in only one unit. A row such as 5.......5 repeats a digit in its row, with the two 5s in different columns and different boxes. A 5 at (0, 4) and another at (8, 4) repeats in a column only. A 5 at (0, 0) and another at (2, 2) repeats in a box only. All three boards return false, which is why all three kinds of set are needed.
    • The same digit in different units is fine. A 5 at (0, 0) and a 5 at (3, 3) share no row, column or box, so that board returns true.
    • Treating '.' as a digit. Without the continue, the second empty cell in a row would look like a repeated digit and a nearly empty board would come out invalid.
    • Solving instead of checking. The method never tries to fill a cell. A valid board may be unsolvable.
    • A wrong box formula. Forgetting the multiplication, as shown above, merges different boxes into one.

    Testing

    • The first example board (53..7...., 6..195..., and so on) gives true.
    • The same board with an 8 in the top left corner gives false.
    • The board with 12345678. in row 0 and a single 9 at the end of row 4 gives true.
    • Nine rows of ......... give true.
    • A board with only a 5 at (0, 0) and a 5 at (3, 3) gives true.
    • A board with only a 5 at (0, 0) and a 5 at (2, 2) gives false.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free