回溯困难1 种解法

#37解数独

为每个空格尝试不与所在行、列和九宫格冲突的数字，找到一个完整解后立即停止。

#回溯#矩阵#位运算

解题主线

数独只需要一个解，因此递归应返回 boolean，并在找到解时沿调用栈立刻结束。

用 9 位掩码维护行、列和宫中已用数字，可以 O(1) 得到候选集合。

每次落子必须同步更新三个掩码，失败后再同时撤销。

解法 1：位掩码回溯

先从棋盘构造三组占用掩码，再按顺序寻找空格，从候选位中逐个取最低位尝试。

时间复杂度

O(9^m)，m 为空格数；约束传播会显著缩小实际搜索树

空间复杂度

O(m)，递归栈；三个掩码数组为 O(1)

37. 解数独 · 位掩码回溯

java

final class Solution {
    public void solveSudoku(char[][] board) {
        int[] rows = new int[9];
        int[] columns = new int[9];
        int[] boxes = new int[9];
        for (int row = 0; row < 9; row++) {
            for (int column = 0; column < 9; column++) {
                char value = board[row][column];
                if (value == '.') {
                    continue;
                }
                int bit = 1 << (value - '1');
                int box = row / 3 * 3 + column / 3;
                if ((rows[row] & bit) != 0 || (columns[column] & bit) != 0
                        || (boxes[box] & bit) != 0) {
                    throw new IllegalArgumentException("invalid sudoku board");
                }
                rows[row] |= bit;
                columns[column] |= bit;
                boxes[box] |= bit;
            }
        }
        solve(board, 0, rows, columns, boxes);
    }

    private boolean solve(char[][] board, int position, int[] rows, int[] columns, int[] boxes) {
        while (position < 81 && board[position / 9][position % 9] != '.') {
            position++;
        }
        if (position == 81) {
            return true;
        }

        int row = position / 9;
        int column = position % 9;
        int box = row / 3 * 3 + column / 3;
        int candidates = ~(rows[row] | columns[column] | boxes[box]) & 0x1FF;
        while (candidates != 0) {
            int bit = Integer.lowestOneBit(candidates);
            candidates &= candidates - 1;
            board[row][column] = (char) ('1' + Integer.numberOfTrailingZeros(bit));
            rows[row] |= bit;
            columns[column] |= bit;
            boxes[box] |= bit;

            if (solve(board, position + 1, rows, columns, boxes)) {
                return true;
            }

            rows[row] ^= bit;
            columns[column] ^= bit;
            boxes[box] ^= bit;
            board[row][column] = '.';
        }
        return false;
    }
}

先从棋盘构造三组占用掩码，再按顺序寻找空格，从候选位中逐个取最低位尝试。

边界与易错点

某个空格的所有数字都失败后必须返回 false，不能继续扫描后续格子。
位掩码和棋盘必须在一次调用内初始化，避免多次调用共享旧状态。
回溯失败时既要把棋盘恢复为 '.'，也要清除对应的行、列、宫位标记。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

backtrack/Q037_solveSudoku.java