Start learning free

LESSON 321 OF 572 · HASH TABLE

Valid Sudoku in C#: 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:

in the same row,
in the same column,
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 14

Guided

Ctrl + Enter to check

C# · HASH TABLE

Valid Sudoku in C#, explained

Problem overview

The method IsValidSudoku receives a 9 x 9 board as a char[][]: an array of 9 rows, each a char[] of 9 cells. A cell holds a digit from '1' to '9', or '.' when it is empty. 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 are checked. The board doesn't have to be solvable: a board with the digits 1 to 8 in row 0 and a 9 at row 4, column 8 is valid, although the last cell of row 0 can no longer be filled. If you take a valid board and replace its top-left 5 with an 8, the board becomes invalid: column 0 and the top-left box then hold two 8s.

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

You could scan the row, the column and the box of every filled cell again for each cell. On a board this small that works, but it looks at each cell many times. A better way is to visit each cell once and keep, for every row, column and box, the set of digits seen so far.

For a filled cell, ask three questions: does its row's set already hold this digit? Its column's? Its box's? If any answer is yes, the digit appears twice, so return false. Otherwise add the digit to all three sets and move on. A set answers "is it there?" in constant time, so each cell costs a constant amount of work.

That makes 27 sets: 9 for rows, 9 for columns and 9 for boxes. Every cell belongs to exactly one set of each kind.

Which box is a cell in?

The boxes are numbered left to right, then top to bottom, from 0 to 8. Dividing a row or column by 3 gives the box's own row or column (0, 1 or 2), because integer division drops the remainder. So the box number is (r / 3) * 3 + c / 3:

cell (0, 0) -> box 0
cell (0, 8) -> box 2
cell (3, 3) -> box 4
cell (4, 7) -> box 5
cell (8, 0) -> box 6
cell (8, 8) -> box 8

Step by step

Create rows as an array of 9 sets: new HashSet<char>[9]. This creates only the array, with 9 empty places (null), not the sets.
Create cols and boxes the same way.
Fill the arrays with a loop over i from 0 to 8, putting a new HashSet<char>() in rows[i], cols[i] and boxes[i]. Each row, column and box needs its own set.
Visit every cell, row by row, with two nested loops over r and c.
Read the cell into a char named digit. If it is '.', continue with the next cell: empty cells never break a rule.
Compute the box number as shown above.
Check for a repeat. If rows[r], cols[c] or boxes[box] already contains the digit, return false. The sets hold the digits of the cells visited before this one, so finding the digit there means it appears twice.
Record the digit with Add in all three sets.
After both loops, return true: every filled cell was compared with the earlier ones, and no digit repeated.

The solution in C#

class Solution {
    public bool IsValidSudoku(char[][] board) {
        HashSet<char>[] rows = new HashSet<char>[9];
        HashSet<char>[] cols = new HashSet<char>[9];
        HashSet<char>[] boxes = new HashSet<char>[9];
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<char>();
            cols[i] = new HashSet<char>();
            boxes[i] = new HashSet<char>();
        }
        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].Contains(digit) || cols[c].Contains(digit) || boxes[box].Contains(digit)) {
                    return false;
                }
                rows[r].Add(digit);
                cols[c].Add(digit);
                boxes[box].Add(digit);
            }
        }
        return true;
    }
}

The C# details worth knowing:

An array of sets starts out empty. new HashSet<char>[9] holds nine null references. Calling Add on one of them throws a NullReferenceException, which is why the first loop creates the sets before the main loop uses them.
char[][] is a jagged array: an array of arrays, read as board[r][c]. A rectangular char[,] would be read as board[r, c] instead, and is a different type.
'.' is a char literal. Single quotes make a char, double quotes a string. Comparing a char to "." doesn't compile.
The digits stay characters. The sets hold '5', not the number 5. That is fine here, because the code only asks whether two cells hold the same character, and never does arithmetic on them.
Integer division. With two ints, / drops the remainder, so 7 / 3 is 2. The box formula relies on that.
HashSet<T> lives in System.Collections.Generic. In a file of your own, add using System.Collections.Generic; at the top.
Add returns a bool: true when the item was new, false when it was already in the set. That allows a shorter form, if (!rows[r].Add(digit) || !cols[c].Add(digit) || !boxes[box].Add(digit)) return false;. It works because || stops at the first true part, and every digit that reaches a later Add was new in the earlier sets. The version above, with separate Contains and Add calls, is easier to read.

Complexity

Time: O(81), a constant. The two loops visit 81 cells, and each cell needs three Contains calls and three Add calls, each O(1) on average.

Space: O(81), also a constant. The 27 sets together hold at most 81 digits per kind: each digit is stored once in a row set, once in a column set and once in a box set.

Edge cases and common mistakes

Checking only the rows. Rows, columns and boxes all count. A board where a digit repeats only inside a box (two 1s at (0, 0) and (1, 1)) must return false.
Wrong box formula. r / 3 + c / 3 maps different boxes to the same number. The row part must be multiplied by 3.
Sharing one set. If the loop forgets to create a separate set for each index, or the code uses one set for everything, valid boards come back as invalid.
Treating '.' as a digit. A board full of dots has many repeated '.' characters. Skipping empty cells is what keeps it valid.
Trying to solve the puzzle. The method only checks the digits already on the board. An unsolvable board with no repeated digit returns true.
Forgetting the null sets. Creating the three arrays without filling them is a NullReferenceException on the first digit.

Testing

These results come from boards written one string per row.

The standard puzzle (first row 53..7....) returns true.
The same puzzle with an 8 in the top-left corner instead of the 5 returns false.
Row 0 12345678. plus a single 9 at row 4, column 8, returns true.
A board of 81 dots returns true.
Two 1s at (0, 0) and (0, 1) (same row) return false.
Two 1s at (0, 0) and (3, 0) (same column) return false.
Two 1s at (0, 0) and (1, 1) (same box only) return 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