这是一个经典的回溯算法问题。我们需要尝试在每一个空格填入 1-9 的数字，并检查是否满足数独规则。如果满足，则继续填下一个空格；如果不满足，则撤销当前操作，尝试下一个数字。

解题思路

1. 遍历：逐行逐列遍历棋盘上的每一个位置。
2. 检查空格：如果当前位置是数字，跳过；如果是 .（空格），则尝试填入 1 到 9。
3. 验证规则：
   • 当前数字是否已存在于当前行？
   • 当前数字是否已存在于当前列？
   • 当前数字是否已存在于当前的 3x3 宫格内？
4. 递归与回溯：
   • 如果填入的数字合法，则将该数字填入棋盘，然后递归处理下一个位置。
   • 如果递归调用返回 true，说明找到了解，直接向上返回 true。
   • 如果递归调用返回 false，说明当前填法行不通，需要回溯：将当前位置重置为 .，尝试下一个数字。
5. 结束条件：如果遍历完所有位置都没有返回 false，说明棋盘已填满且合法，返回 true。

JavaScript 代码实现

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    // 主递归函数
    function backtracking() {
        // 遍历棋盘的每一个位置
        for (let row = 0; row < 9; row++) {
            for (let col = 0; col < 9; col++) {
                // 如果当前位置不是 '.'，说明已有数字，跳过
                if (board[row][col] !== '.') continue;
                // 尝试填入 1 到 9
                for (let num = 1; num <= 9; num++) {
                    const val = String(num);
                    
                    // 检查当前数字是否合法
                    if (isValid(row, col, val)) {
                        board[row][col] = val; // 填入数字
                        
                        // 递归处理下一个位置
                        if (backtracking()) return true; // 如果找到解，直接返回
                        
                        board[row][col] = '.'; // 回溯，撤销处理结果
                    }
                }
                // 如果 1-9 都试过了都不行，说明这条路走不通，返回 false
                return false;
            }
        }
        // 遍历完所有位置都没有返回 false，说明全部填完了，返回 true
        return true;
    }
    // 辅助函数：检查在 放入数字 val 是否合法
    function isValid(row, col, val) {
        // 1. 检查行
        for (let i = 0; i < 9; i++) {
            if (board[row][i] === val) return false;
        }
        // 2. 检查列
        for (let i = 0; i < 9; i++) {
            if (board[i][col] === val) return false;
        }
        // 3. 检查 3x3 宫格
        // 找到当前所属宫格的起始位置
        const startRow = Math.floor(row / 3) * 3;
        const startCol = Math.floor(col / 3) * 3;
        for (let i = startRow; i < startRow + 3; i++) {
            for (let j = startCol; j < startCol + 3; j++) {
                if (board[i][j] === val) return false;
            }
        }
        return true;
    }
    backtracking();
    // 题目要求原地修改 board，不需要返回值
};
// ================= 测试代码 =================
const 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"]
];
solveSudoku(board);
console.log("解决后的数独:");
console.log(board.map(row => row.join(' ')).join('\n'));

复杂度分析

• 时间复杂度：$O(9^m)$，其中 $m$ 是空格的数量。最坏情况下，每个空格都要尝试 9 个数字。
• 空间复杂度：$O(1)$。数独大小固定为 9x9，递归深度最多为 81 层（常数级），存储棋盘的空间也是常数级。