HJ44 Sudoku 数独 ”思维 搜索“

数独要求：在横、竖、3x3矩阵内0-9不可重复出现

重点思路实现方法是，填入一个数后下一步推算基于前面已经填好的数值的新矩阵。
相当于在这一过程中不断更新初始值用于下一步计算。

递归穷举，从第一个空开始填;再更新矩阵填下一个值，一直到最后一个空填完。

回溯：

查错花最多时间在：回溯没重置0导致错误。“递归要缩小规模，回溯要重置或父节点...”
尝试错误需要回溯，回复需要有一个父亲指标，（从链表通过父亲节点回溯中得到启发）

 1 '''
 2 测试案例
 3 m=[[0, 9, 2, 0, 0, 1, 7, 6, 3],
 4 [0, 0, 3, 7, 6, 2, 9, 8, 5],
 5 [0, 0, 7, 3, 5, 9, 4, 1, 2],
 6 [6, 2, 4, 1, 9, 5, 3, 7, 8],
 7 [7, 5, 9, 8, 4, 3, 1, 2, 6],
 8 [1, 3, 8, 6, 2, 7, 5, 9, 4],
 9 [2, 7, 1, 5, 3, 8, 6, 4, 9],
10 [3, 8, 6, 9, 1, 4, 2, 5, 7],
11 [0, 0, 5, 2, 7, 6, 8, 3, 1]]
12 m=[[0, 9, 5, 0, 2, 0, 0, 6, 0],
13 [0, 0, 7, 1, 0, 3, 9, 0, 2],
14 [6, 0, 0, 0, 0, 5, 3, 0, 4],
15 [0, 4, 0, 0, 1, 0, 6, 0, 7],
16 [5, 0, 0, 2, 0, 7, 0, 0, 9],
17 [7, 0, 3, 0, 9, 0, 0, 2, 0],
18 [0, 0, 9, 8, 0, 0, 0, 0, 6],
19 [8, 0, 6, 3, 0, 2, 1, 0, 5],
20 [0, 5, 0, 0, 7, 0, 2, 8, 3]]
21 '''
22 m=[]
23 for i in range(9):    
24     m.append(list(map(int,input().split())))
25 
26 def renew(item):#判断i所在的3x3矩阵并返回矩阵值；
27     #第一个3x3矩阵每个元素下标除以3向下取整为0，第二个3x3矩阵横坐标取整为0，纵坐标为1；
28     #第三个3x3矩阵横坐标取整为0，纵坐标为2；第四个3x3矩阵横坐标取整为1，纵坐标为0，继续类推。
29     renew_grid=[m[i][j] for i in range(item[0]//3*3,item[0]//3*3+3) \
30                 for j in range(item[1]//3*3,item[1]//3*3+3)]
31     renew_row=m[item[0]]
32     mTranspose=list(zip(*m))
33     renew_col=mTranspose[item[1]]        
34     return renew_grid,renew_row,renew_col
35 def recursion(get0):
36     if not get0:
37         return True
38     renew_grid,renew_row,renew_col=renew(get0[0])
39     for j in range(1,10):
40 '''
41         if m[0][7]==6:
42             print(j,get0[0])
43             for i in m:    
44                 print(" ".join(map(str,i)))
45 '''
46         if j not in renew_grid and j not in renew_row and j not in renew_col:
47             m[get0[0][0]][get0[0][1]] =j #更新m矩阵的值 
48             if recursion(get0[1:]):#get0路径跟踪,顺利就去除第一个元素继续跟着
49                 return True     
50             else:
51                 m[get0[0][0]][get0[0][1]] =0#回溯要重置0,否则不可实现
52 get0=[]
53 for i in range(len(m)) :
54     for j in range(len(m[0])):
55         if m[i][j]==0:
56             get0.append((i,j))
57 renew_grid,renew_row,renew_col=renew(get0[0])
58 recursion(get0)
59 for i in m:    
60     print(" ".join(map(str,i)))

 代码行数优化

可把上述代码的renew函数通过下面优化，得到正在填充节点的行列和3x3矩阵。通过“”set()-“”技巧

1 def value(m, x, y):    
2     i, j = x//3, y//3    
3     grid = [m[i*3+r][j*3+c] for r in range(3) for c in range(3)]
4     row_val = m[x]
5     col_val = list(zip(*m))[y]    
6     val = set([i for i in range(1,10)]) - set(grid) - set(row_val) - set(col_val)
7     return list(val)