AI Hints
Home›DSA in Python Tutorial›More Practice: Sets, Windows and Trees
DSA in Python · Lesson 124 of 132

Practice: Valid Sudoku

Sets for rows, columns, boxes.

⏱ 2 min read▶ Video at 2:27:45🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Is a partly filled Sudoku board valid? Each row, each column, and each three by three box must not repeat a digit. Empty cells don't matter. Pause. What would you use to spot a repeat?

Practice: Valid Sudoku
From the video: Practice: Valid Sudoku
  • Rows, columns, boxes
  • No repeated digits
  • Spot a repeat

One set per rule

Each digit makes three keys, one for its row, one for its column, and one for its box. Integer division by three gives each cell's box number. If any of those keys is already in the seen set, the board is invalid. Run it. Valid, until we put a second five in the top row.

sudoku.pypython
def valid(board):
    seen = set()
    for r, row in enumerate(board):
        for c, d in enumerate(row):
            if d == ".":
                continue
            keys = {("row", r, d), ("col", c, d), ("box", r // 3, c // 3, d)}
            if seen & keys:
                return False
            seen |= keys
    return True

rows = ["53..7....", "6..195...", ".98....6."] + ["." * 9] * 6
print(valid(rows))
rows[0] = "53..7...5"
print(valid(rows))
Output
True
False

One pass

We look at each cell once, and each set check is O of one, so the whole board takes one quick pass. Using tuples like row, two, five as keys lets one set hold all three rules. It's a neat way to turn several conditions into one membership check.

keyvalue
Row key('row', r, d)
Column key('col', c, d)
Box(r // 3, c // 3)
Costone pass

Summary

Track each row, column, and box with set keys, and report any repeat. Next, the smallest window that contains every letter you need.

Key takeaways
  • One key per rule
  • r // 3, c // 3 boxes
  • Set intersection
Next up: Practice: Minimum Window Substring — a shrinking window