【杂记】数独求解

# 主流程函数
def get_res(self):
row, column = self.get_zero_pos()
# 如果找不到需要填写数字的位置，则已求得解，递归结束
if row >= 9 or column >= 9:
return True

# 小方格的编号
rect_num = row // 3 * 3 + column // 3
#for val in range(1, 10):
int_lst = [] while True:
if 9 == len(int_lst):
return False
# 为了增加趣味性，使用随机值代替
# 如果不想要随机结果，放开50行的for循环，注释掉51 - 60行的while循环
val = random.randint(1, 9)
if val in int_lst:
continue
int_lst.append(val)

self.shudu_array[row][column] = val
# 判断填入数字后，是否是有效的数独
if not self.is_valid(row, column, rect_num):
self.shudu_array[row][column] = 0
continue

# 更新记录表的行、列和小方格数据
self.rec['row'][row].append(val)
self.rec['column'][column].append(val)
self.rec['rect'][rect_num].append(val)

# 判断是否填入成功
if self.get_res():
return True

# 搜索失败，还原本次操作，继续下次循环
self.shudu_array[row][column] = 0
self.rec['row'][row].pop()
self.rec['column'][column].pop()
self.rec['rect'][rect_num].pop()

return False

# 获取下个需要填写数字的行列下标
def get_zero_pos(self):
for row in range(0, 9):
for column in range(0, 9):
if 0 == self.shudu_array[row][column]:
return row, column

return row + 1, column + 1

if __name__ == '__main__':
shudu_array = [[9,0,0,0,0,0,0,0,0],
[0,0,2,6,0,0,0,0,0],
[0,8,0,0,3,0,5,0,0],
[0,1,0,0,0,8,0,0,0],
[0,0,0,0,4,1,8,0,0],
[0,0,0,0,0,0,0,2,0],
[0,0,0,0,0,0,0,6,9],
[0,0,9,1,0,0,0,0,0],
[0,3,0,0,0,0,4,0,0]]

start_time = time.time()
shudu = Solution(shudu_array)
shudu.get_res()
if shudu.get_res():
for row in shudu_array:
print(row)

end_time = time.time()
print("duration : ", end_time - start_time)

作者：冰临天下

 2/2   首页 上一页 1 2