数独有感 |

基本策略

使用set解决重复，使用回溯法解决，验证数独是否有效是关键函数

下面是一个使用JavaScript实现的数独验证和求解算法，展示了解题的核心思路：

// 验证数独是否有效的函数
function isValidSudoku(board) {
    const boxes = Array(9).fill().map(() => new Set());
    for (let i = 0; i < 9; i++) {
        let rolSet = new Set()
        let colSet = new Set()
        for (let j = 0; j < 9; j++) {
            if (board[i][j] !== '.') {
                if (rolSet.has(board[i][j])) return false
                rolSet.add(board[i][j])
            }
            if (board[j][i] !== '.') {
                if (colSet.has(board[j][i])) return false
                colSet.add(board[j][i])
            }
            let boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3)
            if (board[i][j] !== '.') {
                if (boxes[boxIndex].has(board[i][j])) return false
                boxes[boxIndex].add(board[i][j])
            }
        }
    }
    return true
}

// 寻找空白格
function findEmpty(board) {
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] === '.') {
                return [i, j]
            }
        }
    }
}

// 递归求解数独
function solveSudoku(board) {
    let empty = findEmpty(board)
    if (!empty) {
        // 完成
        return board
    }
    for (let i = 1; i <= 9; i++) {
        board[empty[0]][empty[1]] = String(i)
        if (isValidSudoku(board)) {
            let result = solveSudoku(board)  // 递归解决剩余的格子
            if (result) return result
        }
        board[empty[0]][empty[1]] = '.'
    }
    return false
}

这个算法体现了数独解题的关键原则：

isValidSudoku 函数用于验证数独的有效性
findEmpty 函数找到下一个待填充的空白格
solveSudoku 函数使用递归和回溯的方法尝试填充数独

个人感悟

数独不仅仅是一个简单的逻辑游戏，它更是一个算法和系统思维的缩影。在游戏开发和软件设计中，数独的解题思路提供了诸多启示：

分块与编号策略：数独的9x9矩阵通过3x3的小方块进行分区，这种分块编号方法与游戏世界地图的设计如出一辙。在游戏开发中，复杂的地图往往需要通过类似的分块策略来管理和优化空间逻辑。
约束与剪枝：数独算法中的isValidSudoku函数体现了计算机科学中的约束满足问题（CSP）解决思路。通过实时验证和剪枝，可以快速排除不可能的解，这一思想在人工智能、路径规划等领域都有广泛应用。
递归与回溯：solveSudoku函数展示了递归和回溯算法的典型应用。这种在失败时能够及时撤回、重新尝试的策略，不仅适用于数独，也是解决复杂问题的通用范式。