Free Hashing lessonsHashing · Stage 3 · Sets for structure · Step 4

Many sets at once

Check a sudoku grid with one set per row, column and box. About 12 minutes.

One set for every rule

A sudoku is valid when no digit repeats in any row, any column, or any of the nine 3 × 3 boxes. That's 27 separate "no repeats" rules.

Give each rule its own set: 9 for rows, 9 for columns, 9 for boxes. Every filled cell checks the three sets it belongs to. If the digit is already in any of them, the board is invalid. Otherwise, add it to all three.

Each cell: belongs to one row, one column and one box.

Checking row by row: each digit joins its row's, column's and box's set

box 0: {8}
col 0: {8}
row 0: {8}

8 in row 0, column 0: the top band and the left band, so box 0. It joins the sets for row 0, column 0 and box 0.

Move 1 of 5

Which box is a cell in?

The rows split into three bands: top (rows 0 to 2), middle (3 to 5) and bottom (6 to 8). The columns do the same. A cell's band is its row divided by 3, rounded down, and likewise for its column. The box number combines the two: three times the row band, plus the column band.

Row 4, column 7 is in the middle band and the right band: box 3 + 2 = 5. Empty cells are skipped.

Box number: 3 × row band + column band.

In code

rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
    for c in range(9):
        d = board[r][c]
        if d == ".":
            continue
        b = (r // 3) * 3 + c // 3
        seen = (d in rows[r] or d in cols[c]
                or d in boxes[b])
        if seen:
            return False
        rows[r].add(d)
        cols[c].add(d)
        boxes[b].add(d)
return True

Quick check

Numbering the boxes 0 to 8 left to right, top to bottom, which box holds the cell in row 4, column 7?

Show the answer

5. Row 4 is in the middle band and column 7 in the right band: 3 + 2 = 5, the middle-right box.

Your problem

Valid sudoku?

You get a partly filled sudoku as 9 strings of 9 characters, each a digit 1–9 or '.' for empty. Return true if no digit repeats in any row, any column or any of the nine 3 × 3 boxes. (It doesn't have to be solvable.)

Example

the board with first row "53..7...." (see the tests) → true

exactly 9 strings of 9 characters

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.