思考1、（穷举方法）为了满足规则要求，采用递归回溯的方法写入每个位置的数字。也就是说，先写入一个数字，然后在这一行这一列进行查询对比，如果存在相等的数字就退回到初始位置从1~9中重新选取一个数字写入，继续进行对比回溯重复，直到全部写入相应位置。这样做的显著缺点就是需要大量的回溯步骤和重新写入，导致时间复杂度高。
思考2、依据数独表格的分布状况可以看出，每一行，每一列，每一个九个粗线宫格内的九个小格有且仅有出现1~9数字中的一个。所以，在第一行的1~3列小格写入数字x（为1~9中的任一个），在第二行的4~6列小格同样写入数字x，同样的，在第三行的7~9列小格也写入x。然后重复上述操作，写入另一个数y。同样在4~6行同样进行这样的操作。这样写入的方法可以避免回溯次数。
补充思考1、将数独游戏构成抽象成“树”数据结构类型。将数独的中心线当做每一组四杈树的跟节点，并风别将四杈树，分成两组进行便利对比，判断节点的值不让其相同，若是相同则修改其值再次进行节点便利比较。缺点很明显不仅要在大的九宫格上进行树遍历比较，还要求在小九宫格中进行遍历比较，并且还不一定能够成功找出正确给出解。
补充思考2、将数独类比于求最优解的的问题，根据规则要求不管如何每一行，每一列，每一个粗框九宫格必定都要满足1~9这些分别且全部存在。采用深度优先遍历的算法能够很好的避免过多的回溯。甚至有些数据不需要回溯。
### 代码分析
-确定代码的IPO模式：
-输入为需要补充完整的部分数独
-输出为完整的数独组成
1.输入：已存在数据的按照原数据输入，不存在的数据以数字0表示。直接读取文件夹完成数据输入。
2.同时将数独表示列表的形式，使得用来查找的索引对应每一行每一列。
3.采用深度优先遍历的方法进行数据结构造。创建数独类 soduku （ Object ），定义方法 Check （）用来判断每一行每一列每一个粗线框九宫格是否存在相同项。定义方法 Getnext() 用来获取下一项。定义主循环 SudokuTry（）
4.输出：预测能够输出一个完整的数独
SudokuTry（）//主循环
if self.b[x][y] == 0:
for i in range(1,10):#从1到9尝试
self.t+=1
if self.check(x,y,i):#符合 行列宫均无条件 的
self.b[x][y]=i #将符合条件的填入0格
next_x,next_y=self.get_next(x,y)#得到下一个0格
if next_x == -1: #如果无下一个0格
return True #返回True
else: #如果有下一个0格，递归判断下一个0格直到填满数独
end=self.try_it(next_x,next_y)
if not end: #在递归过程中存在不符合条件的，即 使try_it函数返回None的项
self.b[x][y] = 0 #回朔到上一层继续
else:
return True
测试数据：
0 0 0 0 0 0 0 0 9
9 0 0 0 0 0 0 7 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
3 0 0 0 4 5 7 0 0
0 8 0 0 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
7 0 0 0 1 0 0 0 2
1 4 2 7 5 3 6 8 9
9 6 5 2 8 4 1 7 3
8 7 3 1 9 6 2 5 4
2 5 4 6 3 7 8 9 1
3 1 9 8 4 5 7 2 6
6 8 7 9 2 1 4 3 5
5 3 1 4 7 2 9 6 8
4 2 8 5 6 9 3 1 7
7 9 6 3 1 8 5 4 2
use Time: 0.793530 s
输入：
sudoku=[
0,0,7,0,0,0,8,2,0,
0,9,0,0,0,1,0,0,0,
0,4,0,9,7,0,0,0,0,
0,0,0,0,0,5,4,0,6,
0,0,3,0,0,0,7,0,0,
5,0,6,7,0,0,0,0,0,
0,0,0,0,8,4,0,5,0,
0,0,0,6,0,0,0,1,0,
0,2,4,0,0,0,6,0,0,
]
预测输出：
1 5 7 4 3 6 8 2 9
6 9 8 5 2 1 3 4 7
3 4 2 9 7 8 5 6 1
2 7 9 3 1 5 4 8 6
4 1 3 8 6 2 7 9 5
5 8 6 7 4 9 1 3 2
7 6 1 2 8 4 9 5 3
8 3 5 6 9 7 2 1 4
9 2 4 1 5 3 6 7 8
实际输出
1 5 7 4 3 6 8 2 9
6 9 8 5 2 1 3 4 7
3 4 2 9 7 8 5 6 1
2 7 9 3 1 5 4 8 6
4 1 3 8 6 2 7 9 5
5 8 6 7 4 9 1 3 2
7 6 1 2 8 4 9 5 3
8 3 5 6 9 7 2 1 4
9 2 4 1 5 3 6 7 8
use Time: 0.876582 s
python 3.6
网友评论