cconnected.
Understand the pattern. Find your own way.Find your starting point
Your learning feed/Idea 94 of 218
Ideas this builds on
Backtracking94 / 218

Sudoku: choose the tightest blank

Picture

A digit is legal only if absent from its row, column, and box. These three constraints intersect.

Predict

Does choosing the tightest blank change the solution set?

Walk through the small example

No. All blanks share constraints; choosing minimum remaining values exposes contradictions earlier.

Mental model and complete Python solution

Each blank asks for the intersection of three allowed sets. Pick the smallest intersection first; if it is empty, fail immediately. Every tentative digit owns three marks to undo.

What the function promises: Solve a 9×9 board in place using digits 1..9 and 0 for blanks. Return False for an invalid or unsatisfiable board.

def solve_sudoku(board):
    digits = set(range(1,10))
    rows, cols, boxes = [set() for _ in range(9)], [set() for _ in range(9)], [set() for _ in range(9)]
    blanks = []
    for r in range(9):
        for c in range(9):
            value = board[r][c]
            box = (r//3)*3+c//3
            if value == 0: blanks.append((r,c))
            elif value not in digits or value in rows[r] or value in cols[c] or value in boxes[box]:
                return False
            else: rows[r].add(value); cols[c].add(value); boxes[box].add(value)
    def search():
        if not blanks: return True
        best = min(range(len(blanks)), key=lambda i: len(digits-rows[blanks[i][0]]-cols[blanks[i][1]]-boxes[(blanks[i][0]//3)*3+blanks[i][1]//3]))
        r, c = blanks.pop(best); box = (r//3)*3+c//3
        for value in sorted(digits-rows[r]-cols[c]-boxes[box]):
            board[r][c] = value; rows[r].add(value); cols[c].add(value); boxes[box].add(value)
            if search(): return True
            rows[r].remove(value); cols[c].remove(value); boxes[box].remove(value)
        board[r][c] = 0; blanks.insert(best,(r,c))
        return False
    return search()

puzzle = [[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]]
assert solve_sudoku(puzzle)
assert all(set(row) == set(range(1,10)) for row in puzzle)

Work and storage: Exponential worst case; constraint sets use O(81) space and recursion has at most 81 blanks.

When to recognize it: All blanks share constraints; choosing minimum remaining values exposes contradictions earlier.

Check before applying it: A solver must validate the initial board and define behavior for zero or multiple solutions.

Change one rule

Need to prove the solution is unique.

See what changes

After finding one solution, continue searching until a second appears; do not stop at the first.

Connect

pruning: A tighter branch order reduces search without discarding legal answers.

N-Queens: place one row at a time: Both use sets for row, column, and geometric conflicts.