37. Sudoku Solver
求解数独。前两天做了验证数独那道题,当时对于遍历hash的使用有了一些感悟,但看这道题时候特别头疼。这两天HackerRank也刷了一下,对于DFS和BFS的理解加深了一些,渐渐的思路就变得清晰。其实是很暴力的解法,但把他转化为代码,对几天前的我来说还有一些难度。经过这两天的学习,总算是可以勉强完成,但参考别人的答案后,果然进步空间还比较大。
我之前的版本,dfs函数没有加入i与j两个变量,每次调用都重新扫描一遍需要填的空,这导致效率很低,引入i和j后果然好了很多。另外之前的dfs是void不返回值,通过一个cnt变量计算总共的空数,当cnt等于0时停止,但由于我们需要在中途中断dfs函数(找到正确的解时,否则答案会被填回’.’),采用void的类型也会比较难以中断。借鉴了别人的解法,让dfs返回一个值来判定是否完成整个数独,这样好了很多。
算法解释:
- solveSudoku: 功能函数入口。
- dfs:深度优先搜索函数。
- 输入整个表和一个坐标。
- 如果该坐标已有数字,搜索下一个格子
j++
;当j==9
,说明这一排已搜索完,搜索下一排的第一个格子i++, j=0
;如果所有的行都已搜索完,说明所有的格子都被正确的填入了数字,则返回true
。 - 如果该坐标下没有数字
'.'
,从1开始填入,并验证该数字是否可行isValid(board, i, j)
。如果不可行,擦除填入的数字并填入下一个数字直到9。如果可行,搜索下一个格子,并直到整张表被填完。 - 如果一个没有填的格子所有的数字都不可行,代表之前填的数字有错,那么返回
false
。
- isValid:验证某个格子里的数字是否可行,是之前验证数独的简化版,因为只用验证特定位置的数字。
1 | class Solution { |