python小练习（067）：回溯法（深度优先搜索）求解数独问题

jerryxjr1220

数独的求解其实之前已经有分享过，但是目前正好讲解回溯法（深度优先搜索），就顺便拿过来再分享一下。

求解数独问题的过程是非常典型的回溯法的应用。

原始数独：
[0,0,8,0,0,0,2,0,0]
[0,3,0,8,0,2,0,6,0]
[7,0,0,0,9,0,0,0,5]
[0,5,0,0,0,0,0,1,0]
[0,0,4,0,0,0,6,0,0]
[0,2,0,0,0,0,0,7,0]
[4,0,0,0,8,0,0,0,6]
[0,7,0,1,0,3,0,9,0]
[0,0,1,0,0,0,8,0,0]

输出：
[6, 1, 8, 7, 3, 5, 2, 4, 9]
[5, 3, 9, 8, 4, 2, 7, 6, 1]
[7, 4, 2, 6, 9, 1, 3, 8, 5]
[3, 5, 7, 4, 2, 6, 9, 1, 8]
[1, 8, 4, 5, 7, 9, 6, 2, 3]
[9, 2, 6, 3, 1, 8, 5, 7, 4]
[4, 9, 3, 2, 8, 7, 1, 5, 6]
[8, 7, 5, 1, 6, 3, 4, 9, 2]
[2, 6, 1, 9, 5, 4, 8, 3, 7]

源代码：

游客，如果您要查看本帖隐藏内容请回复

caiyouqian

学习，受教了

新手·ing

谢谢，学习了

知飞科技

厉害

qianlixiaozhuoz

高端

荷风香煞

学习

余欲渔

来学习思路

木木子_666

正想要找一些Python习题练习一下，不过这里面的看起来难度挺大

小小王python

学习

WelanceLee

global a
a = [[0,0,8,0,0,0,2,0,0],
[0,3,0,8,0,2,0,6,0],
[7,0,0,0,9,0,0,0,5],
[0,5,0,0,0,0,0,1,0],
[0,0,4,0,0,0,6,0,0],
[0,2,0,0,0,0,0,7,0],
[4,0,0,0,8,0,0,0,6],
[0,7,0,1,0,3,0,9,0],
[0,0,1,0,0,0,8,0,0]]

def check(x, y):
    global a
    flag = 0
    for i in range(9):
        if a[i][y] == a[x][y]:
            flag += 1
    for j in range(9):
        if a[x][j] == a[x][y]:
            flag += 1
    if flag > 2:
        return False
    else:
        return True
    
def fillblank(x, y):
    global a
    if x == 9:
        input('input a key to stop: ')
        print(a)
        exit()
    if a[x][y] == 0:
        for i in range(1, 10):
            a[x][y] = i
            if check(x, y):
                if y < 8:
                    fillblank(x, y + 1)
                else:
                    fillblank(x + 1, 0)
            else:
                continue
        a[x][y] = 0
    else:
        if y < 8:
            fillblank(x, y + 1)
        else:
            fillblank(x + 1, 0)
        
fillblank(0, 0)

WelanceLee

WelanceLee 发表于 2017-4-25 13:32

有个疑问：如果我在fillblank函数判断终止那儿写 if x == 9：return，那么函数会运行很长时间（没有等到结果），这是为甚吗？

a649456500

M喵狮

膜拜大佬

z6112539

受教了

jerryxjr1220

WelanceLee 发表于 2017-4-25 13:40
有个疑问：如果我在fillblank函数判断终止那儿写 if x == 9：return，那么函数会运行很长时间（没有等到 ...

你的check函数好像不完整吧？

def check(x, y):
    global a
    flag = 0
    for i in range(9):
        if a[i][y] == a[x][y]:
            flag += 1
    for j in range(9):
        if a[x][j] == a[x][y]:
            flag += 1
    if flag > 2:
        return False
    else:
        return True

你只检查了横行和竖排不能重复，还有9格的呢？ 数独的规则是3x3的9格内也不允许有重复数字。

而且你这个算法哪怕写得正确也很难算出来，因为你几乎是在穷举每一个可能的值，那你算算81个格子内，每个格子有9个可能，一共有多少种不同的排列组合？ 一共是196627050475552913618075908526912116283103450944214766927315415537966391196809种， 就算每秒钟可以计算100万种，总共需要6e+63年才能算完

逝痕

老甲鱼与小甲鱼

学习学习

WelanceLee

jerryxjr1220 发表于 2017-4-27 21:48
你的check函数好像不完整吧？

你只检查了横行和竖排不能重复，还有9格的呢？ 数独的规则是3x3的9格 ...

原来我连玩法都没搞清楚啊，尴了个大尬~

cngrand

学习