题解 | #Sudoku#

#---------------------------------------------------------------------------------
def print2D(S):
    for i in S:
        print(' '.join(map(str,i)))
#---------------------------------------------------------------------------------
# 检测value所在的i行，j列，ij所在3*3的粗线宫格是否已有重复数字，返回true时说明没有
def check(S,i,j,value):
    if value in S[i]:
        return False
    for ii in range(9):
        if value == S[ii][j]:
            return False
    ii = i//3*3
    jj = j//3*3
    for r in range(ii,ii+3):
        for c in range(jj,jj+3):
            if value == S[r][c]:
                return False
    return True
#---------------------------------------------------------------------------------
# 返回0值所有的行列，及长度
def ijzero(S):
    I = []
    J = []
    for i in range(9):
        for j in range(9):
            if S[i][j] == 0:
                I.append(i)
                J.append(j)
    return I,J,len(I)
#=================================================================================

input = ['0 9 2 4 8 1 7 6 3',
         '4 1 3 7 6 2 9 8 5',
         '8 6 7 3 5 9 4 1 2',
         '6 2 4 1 9 5 3 7 8',
         '7 5 9 8 4 3 1 2 6',
         '1 3 8 6 2 7 5 9 4',
         '2 7 1 5 3 8 6 4 9',
         '3 8 6 9 1 4 2 5 7',
         '0 4 5 2 7 6 8 3 1']

#S = []
#for i in range(9):
#    t = list(map(int,input().strip().split()))
#    S.append(t)

S = []
for i in range(9):
    t = list(map(int,input[i].strip().split()))
    S.append(t)

for i in range(4):
    for j in range(4):
        S[i][j] = 0
print2D(S)
#---------------------------------------------------------------------------------
# 返回0值所有的行列，及长度

I,J,n = ijzero(S)
value = [1,2,3,4,5,6,7,8,9]

res = []
def dfs(k, res):
    if k==n:                # 如达到最后一个节点
        #print(res)
        return res          # 返回第一个合法解，如无返回可打印所有合法解

    if 0<=k<=n-1:           # 限定搜索范围保证访问不越界
        i = I[k]            # 取行值
        j = J[k]            # 取列值
        for v in value:                         # 遍历当前节点每个候选解
            if check(S,i,j,v):                  # 检查当前节点当前候选解合法性
                S[i][j] = v                     # 如合法赋值
                solve_opt = dfs(k+1, res+[v])   # 递归进入下一个节点，第二个参数加入当前节点合法解。dfs()的返回值solve只有两种情况，
                if solve_opt:                   # 1、为空，说明下一个节点几个候选解check()都返回false，即本节点当前候选解不对，
                    return solve_opt            #    本节点要回溯执行下一个候选解，因此要恢复S[i][j]=0，对一下个候选解执行check()
                S[i][j] = 0                     # 2、不为空时，说明到达终点k==n，solve返回所有路径点res

solve_opt = dfs(0, res)
print('solve_opt=',solve_opt)
if solve_opt:
    print2D(S)
else:
    print('none')