Valid Sudoku

The problem

Given a 9 × 9 Sudoku board that is partly filled in, return true if the digits placed so far break no rule, and false if they break one. A digit may appear only once in each row, once in each column, and once in each of the nine 3 × 3 boxes. Empty cells are written as "." and are ignored. The board does not have to be solvable: only the cells already filled are checked.

What to write

function solve(board: string[][]): boolean

Input
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

Output
true

Input
board = [["5","5",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

Output
false

Constraints

The board is 9 × 9 and contains digits 1–9 or dots.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The board is always 9 × 9, so speed is not the problem here. The hard part is checking three kinds of groups, rows, columns and boxes, without writing three separate programs.

2. Hint 2: Ask a smaller question

   For a cell in row r and column c, which of the nine boxes is it in? Try a few cells by hand and look for a rule that turns r and c into a box.

3. Hint 3: Name the pattern

   Each rule says "no repeated digit inside this group", which is the duplicate question again. Remember what you have seen in a hash set and check before you add: hash set membership. Read the lesson on hash set membership.

4. Hint 4: State the invariant

   The set holds one entry for every digit seen so far in each row, each column and each box. The board stays valid as long as no entry is ever added twice.

5. Hint 5: Sketch the pseudocode

   Start with an empty set. For each filled cell with digit d at row r, column c, build three entries: (row r, d), (column c, d) and (box r ÷ 3, c ÷ 3, d), dropping the remainders. If any is already in the set, return false; otherwise add all three. Return true at the end.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Track a separate key for each digit in its row, column, and box. A repeated key makes the board invalid.

The slow way

Check each of the nine rows for a repeated digit, then each of the nine columns, then each of the nine boxes, with a separate loop for each kind. It works, but it is three programs that all answer the same question.

The insight

All three rules are the same rule about different groups. If you tag each digit with the group it sits in, one set can watch every row, column and box at once, and a repeated tag is a broken rule.

Step by step

1. One set remembers every digit seen, tagged with where it was. A tag such as "row 0 has a 5" belongs to one rule and one group, so one set can hold the tags of all 27 groups without mixing them up.
2. An empty cell cannot break a rule. Only digits can repeat. A dot is a blank, and many blanks in one row are fine.
3. A digit sits in one row, one column and one box: three tags. The box comes from dividing the row and the column by 3 and dropping the remainder: rows 0 to 2 give 0, rows 3 to 5 give 1, rows 6 to 8 give 2.
4. A tag seen before means the digit repeats there. The set holds the tags of all the cells before this one. Finding a tag there means the same digit is already in that row, column or box.
5. No tag repeated, so every rule holds. Every filled cell was checked against all the cells before it in its three groups, and none clashed.

The same numbered steps are the comments in each solution.

function solve(board) {
  // 1. One set remembers every digit seen, tagged with where it was
  const seen = new Set();
  for (let r = 0; r < 9; r++)
    for (let c = 0; c < 9; c++) {
      const v = board[r][c];
      // 2. An empty cell cannot break a rule
      if (v === ".") continue;
      // 3. A digit sits in one row, one column and one box: three tags
      for (const key of [
        "r" + r + v,
        "c" + c + v,
        "b" + Math.floor(r / 3) + Math.floor(c / 3) + v,
      ]) {
        // 4. A tag seen before means the digit repeats there
        if (seen.has(key)) return false;
        seen.add(key);
      }
    }
  // 5. No tag repeated, so every rule holds
  return true;
}

function solve(board: string[][]): boolean {
  // 1. One set remembers every digit seen, tagged with where it was
  const seen = new Set<string>();
  for (let r = 0; r < 9; r++)
    for (let c = 0; c < 9; c++) {
      const v = board[r][c];
      // 2. An empty cell cannot break a rule
      if (v === ".") continue;
      // 3. A digit sits in one row, one column and one box: three tags
      for (const key of [
        "r" + r + v,
        "c" + c + v,
        "b" + Math.floor(r / 3) + Math.floor(c / 3) + v,
      ]) {
        // 4. A tag seen before means the digit repeats there
        if (seen.has(key)) return false;
        seen.add(key);
      }
    }
  // 5. No tag repeated, so every rule holds
  return true;
}

def solve(board):
    # 1. One set remembers every digit seen, tagged with where it was
    seen = set()
    for r, row in enumerate(board):
        for c, value in enumerate(row):
            # 2. An empty cell cannot break a rule
            if value == ".":
                continue
            # 3. A digit sits in one row, one column and one box: three tags
            box = (r // 3, c // 3)
            for key in (("row", r, value), ("col", c, value), ("box", box, value)):
                # 4. A tag seen before means the digit repeats there
                if key in seen:
                    return False
                seen.add(key)
    # 5. No tag repeated, so every rule holds
    return True

Example 2, traced

Input
board = [["5","5",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

Output
false

Why it works

Two cells break a rule exactly when they hold the same digit and share a row, a column or a box, and in that case they produce at least one identical tag. The second of the two cells finds that tag already in the set, so every broken rule is caught and nothing else is.

Time and space

Time O(81), extra space O(81). The board always has 81 cells and each adds at most three tags, so both the time and the space are constant: O(81). For a larger board the method would grow in step with the number of cells.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Skip the empty cells. If "." is treated as a value, the second blank in any row looks like a repeat.
• Divide the row and the column by 3 before combining them into a box. Using the row and column themselves makes every cell its own box, so a repeat inside a real box is never found.
• Keep the kind of group in the tag. Without it, "5 in row 3" and "5 in column 3" would be the same entry.

Pattern

Hash set membership. Builds on Contains Duplicate.

Keep going