算法刷题系列（三十三）：数独问题——把约束满足转成搜索

算法刷题系列（三十三）：数独问题——把约束满足转成搜索

标准数独是一个约束满足问题：每行、每列、每个 3×3 宫都必须恰好使用数字 1 到 9。搜索时不必每次扫描九个格子检查冲突；可以用三个掩码集合保存已经占用的数字，并在填数后立即更新约束状态。

棋盘用 '.' 表示空格。本文求任意一个解并原地修改棋盘；若题面还要求找出所有解，需要改为收集解而不是找到第一个就返回。

位掩码表示约束

数字 d 对应位 1 << (d - 1)。行掩码 rows[r]、列掩码 cols[c] 和宫掩码 boxes[b] 的某一位为 1，表示该数字已经占用。宫编号是 (r / 3) * 3 + c / 3。

对空格 (r,c)，可选位为：

ALL & ~(rows[r] | cols[c] | boxes[boxIndex])

ALL 仅保留低九位。选择一位后，将其同时写入三个掩码；递归失败则用异或清掉这三位，并把格子恢复为 '.'。这是回溯的状态不变量：掩码始终精确反映当前棋盘上已经填入的数字。

Java 实现

import java.util.ArrayList;
import java.util.List;

public class SudokuSolver {
    private static final int ALL = (1 << 9) - 1;
    private final int[] rows = new int[9];
    private final int[] cols = new int[9];
    private final int[] boxes = new int[9];
    private final List<int[]> empty = new ArrayList<>();

    public boolean solve(char[][] board) {
        validateShape(board);
        empty.clear();
        for (int i = 0; i < 9; i++) {
            rows[i] = cols[i] = boxes[i] = 0;
        }

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char cell = board[r][c];
                if (cell == '.') {
                    empty.add(new int[] {r, c});
                    continue;
                }
                if (cell < '1' || cell > '9') {
                    throw new IllegalArgumentException("cells must be '.' or '1'..'9'");
                }
                int bit = 1 << (cell - '1');
                int box = boxIndex(r, c);
                if (((rows[r] | cols[c] | boxes[box]) & bit) != 0) {
                    return false;
                }
                rows[r] |= bit;
                cols[c] |= bit;
                boxes[box] |= bit;
            }
        }
        return fill(board, 0);
    }

    private boolean fill(char[][] board, int position) {
        if (position == empty.size()) {
            return true;
        }

        int best = position;
        int fewest = 10;
        for (int i = position; i < empty.size(); i++) {
            int[] cell = empty.get(i);
            int mask = ALL & ~(rows[cell[0]] | cols[cell[1]]
                | boxes[boxIndex(cell[0], cell[1])]);
            int count = Integer.bitCount(mask);
            if (count < fewest) {
                best = i;
                fewest = count;
            }
        }
        if (fewest == 0) {
            return false;
        }

        swap(empty, position, best);
        int[] cell = empty.get(position);
        int r = cell[0], c = cell[1], box = boxIndex(r, c);
        int available = ALL & ~(rows[r] | cols[c] | boxes[box]);
        while (available != 0) {
            int bit = available & -available;
            available -= bit;
            int digit = Integer.numberOfTrailingZeros(bit) + 1;
            board[r][c] = (char) ('0' + digit);
            rows[r] |= bit;
            cols[c] |= bit;
            boxes[box] |= bit;

            if (fill(board, position + 1)) {
                swap(empty, position, best);
                return true;
            }

            rows[r] ^= bit;
            cols[c] ^= bit;
            boxes[box] ^= bit;
            board[r][c] = '.';
        }
        swap(empty, position, best);
        return false;
    }

    private static int boxIndex(int r, int c) {
        return (r / 3) * 3 + c / 3;
    }

    private static void swap(List<int[]> cells, int a, int b) {
        int[] temp = cells.get(a);
        cells.set(a, cells.get(b));
        cells.set(b, temp);
    }

    private static void validateShape(char[][] board) {
        if (board == null || board.length != 9) {
            throw new IllegalArgumentException("board must be 9 by 9");
        }
        for (char[] row : board) {
            if (row == null || row.length != 9) {
                throw new IllegalArgumentException("board must be 9 by 9");
            }
        }
    }
}

Python 实现

ALL = (1 << 9) - 1

def solve_sudoku(board: list[list[str]]) -> bool:
    if len(board) != 9 or any(len(row) != 9 for row in board):
        raise ValueError("board must be 9 by 9")

    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9
    empty: list[tuple[int, int]] = []

    def box_index(row: int, col: int) -> int:
        return (row // 3) * 3 + col // 3

    for row in range(9):
        for col in range(9):
            cell = board[row][col]
            if cell == ".":
                empty.append((row, col))
                continue
            if cell not in "123456789":
                raise ValueError("cells must be '.' or '1'..'9'")
            bit = 1 << (int(cell) - 1)
            box = box_index(row, col)
            if (rows[row] | cols[col] | boxes[box]) & bit:
                return False
            rows[row] |= bit
            cols[col] |= bit
            boxes[box] |= bit

    def fill(position: int) -> bool:
        if position == len(empty):
            return True

        best = position
        fewest = 10
        for index in range(position, len(empty)):
            row, col = empty[index]
            mask = ALL & ~(rows[row] | cols[col] | boxes[box_index(row, col)])
            count = bin(mask).count("1")
            if count < fewest:
                best, fewest = index, count
        if fewest == 0:
            return False

        empty[position], empty[best] = empty[best], empty[position]
        row, col = empty[position]
        box = box_index(row, col)
        available = ALL & ~(rows[row] | cols[col] | boxes[box])
        while available:
            bit = available & -available
            available -= bit
            digit = bit.bit_length()
            board[row][col] = str(digit)
            rows[row] |= bit
            cols[col] |= bit
            boxes[box] |= bit
            if fill(position + 1):
                empty[position], empty[best] = empty[best], empty[position]
                return True
            rows[row] ^= bit
            cols[col] ^= bit
            boxes[box] ^= bit
            board[row][col] = "."

        empty[position], empty[best] = empty[best], empty[position]
        return False

    return fill(0)

best_mask 仅用于统计候选数量；填入时会根据选定的格子重新计算可用掩码。也可以保留该掩码并复用，但要确保它对应交换后的那个格子。

为什么先选候选最少的格子？

每层扫描剩余空格并优先选可填数字最少的格子，即最少剩余值（MRV）启发式。若某格没有候选，马上失败；候选越少，越容易尽早发现矛盾。它不改变可解性的证明，只改变探索顺序，通常显著减少搜索量。

最坏情况下仍可能尝试每个空格的至多九种数字，时间上界粗略为 O(9^m)（m 是空格数）；掩码和空格列表额外空间为 O(m + 1)。MRV 是实践优化，不消除指数级最坏情况。

边界与常见错误

• 先检查棋盘形状、字符范围和已有冲突；输入本身不合法时不能把它当作普通无解搜索。
• 宫编号要用整除后的行、列坐标；漏掉 c / 3 会让三个宫的约束混在一起。
• bit & -bit 取最低位，bit_length() 在 Python 中恰好给出从 1 开始的数字。
• 递归失败要同时恢复棋盘和三个掩码；只恢复其中一部分会污染后续分支。
• 题目只要求一个解时找到后立即返回。若要求统计所有解，不能在第一个成功分支停止。

把约束压缩成位集合后，合法性检查和候选生成都变成几次位运算；而回溯负责试探、传播约束和恢复状态。