0%

广搜&深搜算法和数独求解

最近中了数独的毒,没事就玩数独。玩到后面,发现其实也没啥技术含量,主要是看眼力和尝试,有点没劲。还是写代码求解下数独吧,比较不费劲。

求解数独应用到广度优先搜索和深度优先搜索算法。先简单介绍下这两个算法。最后在文末提供一个求解数据的demo。
数独所有可能的解法可以组成多叉树,遍历每一个节点,判断该节点是否是正解。

广度优先搜索

利用队列来实现,遍历队列中的节点,遍历节点的同时,需要将节点的子节点也添加到队列中。

1
2
3
4
enqueue root
while queue is not empty:
dequeue as node
enqueue node's subnode

深度优先搜索

利用栈来实现,从根节点出发,发现有子节点未访问过则将子节点入栈。

1
2
3
4
5
6
7
8
9
10
push root
while stack is not empty:
if left child of stack.top has not been visited:
set left child visited
push left child
else if right child of stack.top has not been visited:
set right child visited
push right child
else:
pop stack

解数独

数独你好 数独再见 👋👋