37. 解数独

1. 题目描述

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

• 数字 1-9 在每一行只能出现一次。
• 数字 1-9 在每一列只能出现一次。
• 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
• 空白格用 ‘.’ 表示。

一个数独。

答案被标成红色。

Note:

• 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
• 你可以假设给定的数独只有唯一解。

• 给定数独永远是 9x9 形式的。

  2. 解题思路

  对于这道题目，我们需要对每个格子进行遍历，只要格子为空，就对其进行数字填充，填充数字的过程中要符合规则，根据要求，我们需要对以下两点进行验证：

• 判断每行每列中的数字不能有重复的值

• 将整个格子分为九块，分别对其进行验证

对宫格中的格子进行逐行遍历，如果当前的格子满足条件，就遍历下一个格子，下一个若不满足条件，就回溯到上一个格子，进行遍历。如果满足条件，就继续进行遍历。直至遍历完最后一个格子。

3. 代码实现

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    const fn = (row, col,val) => {
        // 判断行列中的数是否有冲突，无冲突为false，有冲突为true
        for(let i = 0; i < 9; i++){
            if(board[i][col] === val || board[row][i] === val){
                return true
            }
        }
        const rowStart = Math.floor(row / 3) * 3
        const colStart = Math.floor(col / 3) * 3
        for(let i = 0; i < 3; i++){
            for(let j = 0; j < 3; j++){
                if(val === board[rowStart + i][colStart + j]){
                    return true
                }
            }
        }
        return false
    }
    // 填充board
    const fill = (i, j) => {
        // 逐行遍历，遍历完一行就换行
        if(j === 9){
            i ++
            j = 0
            if(i === 9){
                return true
            }
        }
        if(board[i][j] != ".")  return fill(i, j + 1)  // 递归下一格
        for(let num = 1; num <= 9; num++){
            if(fn(i, j, String(num))) continue
            board[i][j] = String(num)
            // 如果基于这个数，填写下一格有解，就返回true，继续执行；如果无解，就将这个还设置为”.“，进行回溯
            if(fill(i, j + 1)){
                return true
            }else{
                board[i][j] = "."  
            }
        }
        return false
    }
    fill(0, 0)
    return board
};

4. 提交结果