回溯困难1 种解法
#37解数独
为每个空格尝试不与所在行、列和九宫格冲突的数字，找到一个完整解后立即停止。
#回溯#矩阵#位运算
原题
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1：
输入：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"]] 输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
board.length == 9board[i].length == 9board[i][j]是一位数字或者'.'- 题目数据 保证 输入数独仅有一个解
解题主线
- 数独只需要一个解，因此递归应返回 boolean，并在找到解时沿调用栈立刻结束。
- 用 9 位掩码维护行、列和宫中已用数字，可以 O(1) 得到候选集合。
- 每次落子必须同步更新三个掩码，失败后再同时撤销。
解法 1：位掩码回溯
先从棋盘构造三组占用掩码，再按顺序寻找空格，从候选位中逐个取最低位尝试。
-
时间复杂度： O(9^m)，m 为空格数；约束传播会显著缩小实际搜索树
-
空间复杂度： O(m)，递归栈；三个掩码数组为 O(1)
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