LeetCode 037. 解数独

题目描述:

难度：Hard

相关话题：哈希表、回溯算法

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

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

1. 数字 1-9 在每一行只能出现一次。

2. 数字 1-9 在每一列只能出现一次。

3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

• 给定的数独序列只包含数字 1-9 和字符 '.' 。

• 你可以假设给定的数独只有唯一解。

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

Js中文网 – 前端进阶资源教程 www.javascriptC.com,typescript 中文文档
Javascript中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js……等，以帮助开发者成长为愿景的社区

---

思路：

这道题要求填充，解决办法就是回溯，但是每填一个数字，需要检查是否有效，如果每次都重新检查，时间消耗太高。

因此用hash保存初始行，列，块的数字，后面回溯过程中，每填一个数字，只要检查hash便可以，有效即更新hash。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
  let memRow=Array(9).fill().map(()=>Array(10).fill(false)),
      memCol=Array(9).fill().map(()=>Array(10).fill(false)),
      memBox=Array(9).fill().map(()=>Array(10).fill(false))
  let needToFill=[]
  for(let r=0;r<9;r++){
    for(let c=0;c<9;c++){
      let curVal=board[r][c]
      if(curVal!=='.'){
        memRow[r][curVal]=true
        memCol[c][curVal]=true
        let boxID=Math.floor(r/3)*3+Math.floor(c/3)
        memBox[boxID][curVal]=true
      }else{
        needToFill.push([r,c])
      }
    }
  }
  dfs(0)
  function dfs(index){
    if(index===needToFill.length)return true
    let [r,c]=needToFill[index]
    let boxID=Math.floor(r/3)*3+Math.floor(c/3)
    for(let val=1;val<10;val++){
      if(!memRow[r][val] && !memCol[c][val] && !memBox[boxID][val]){
        memRow[r][val]=true
        memCol[c][val]=true
        memBox[boxID][val]=true
        board[r][c]=val+''
        if(dfs(index+1))return true
        board[r][c]='.'
        memRow[r][val]=false
        memCol[c][val]=false
        memBox[boxID][val]=false
      }
    }
  }
};