导读：前面几篇文章分享了一些BFS相关的题目，今天再来一道DFS算法的题目，大家一起来学习吧！
题目描述
编写一个程序，来解决数独问题。
一个数独的解法需遵循如下规则：
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示
待解的数独
解开的数独
题目来源：leetcode 37. Sudoku Solver
题目分析
这种类型题目，对于学习过算法的粉丝来说，应该不难，很容易想到用深度优先搜索算法来解决（DFS）。DFS算法在运行过程中，我们需要对每个待确定的小方格里的数字逐一尝试，每个待确定的小方格里的数字，必须和数独的特性不冲突，所以，我们需要用额外的hash数组来标识哪些数字已经不能使用，针对每一行，每一列，每一个3*3的子宫格都需要hash一下。其实，这种类型DFS虽然说简单，但是DFS往往涉及比较多的递归，回溯的过程，这里面的状态要维护好，不然容易出错，堆栈溢出，或者其他奇奇怪怪的问题！
直接见源码，代码是很久以前java写的，比较粗糙，其实，这个题目有个优化的技巧，后续算法哥再说明！
源码片段一
源码片段二
复杂度分析
这个复杂度其实不太好分析，因为与给出的数独的复杂度相关性很大，极端情况，复杂度会很大！
题目总结
《解数独》这道题目，是非常经典的DFS的题目，对递归，回溯的要求还是蛮高的，不熟悉的话，很容易写错！
前面说过这个题目有个优化的技巧，其实，每个待确定的方格里，需要尝试的数字可能个数是有多少的区别的，我们可以尽量从个数少的方格开始递归，这样会效率更高的，至于为什么留给读者自己思考吧！
今天的题目分享完毕，请帮助算法哥上头条吧，您的关注，转发，点赞，收藏都是对算法哥最大的鼓励！
分享到:
閱讀更多 算法哥 的文章
