题目:
难度:Hard
相关话题:哈希表
、回溯算法
编写一个程序,通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则 :
数字 1-9
在每一行只能出现一次。
数字 1-9
在每一列只能出现一次。
数字 1-9
在每一个以粗实线分隔的 3x3
宫内只能出现一次。
空白格用 '.'
表示。
一个数独。
答案被标成红色。
Note:
思路:
这道题要求填充,解决办法就是回溯
,但是每填一个数字,需要检查是否有效,如果每次都重新检查,时间消耗太高。
因此用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
}
}
}
};