[技术交流] Python解数独（回溯算法，代码少于 60 行）

#coding=utf-8

#初始化数独的二维数组
sudoku = [
        [0, 0, 0, 0, 0, 4, 0, 1, 8],
        [0, 0, 0, 0, 0, 0, 0, 6, 0],
        [0, 9, 8, 0, 7, 5, 0, 0, 0],
        [1, 0, 0, 3, 0, 0, 0, 0, 0],
        [0, 5, 0, 0, 0, 0, 0, 2, 0],
        [0, 0, 0, 0, 0, 2, 0, 0, 6],
        [0, 0, 0, 4, 1, 0, 6, 3, 0],
        [0, 2, 0, 0, 0, 0, 0, 0, 0],
        [8, 6, 0, 7, 0, 0, 0, 0, 0]]

matrix = sudoku[:]

#验证算法，判断数独内部是否有不合规填充
def suCheck(row, line, value) :
        #行与列的验证
        for i in range(9) :
                if (matrix[row][i] == value) or (matrix[i][line] == value) :
                        return False
        #小九宫格验证
        tempRow = row // 3
        tempLine = line // 3
        for i in range(3) :
                for j in range(3) :
                        if (matrix[tempRow * 3 + i][tempLine * 3 + j] == value) :
                                return False
        return True

#递归算法，填充数独
def backTrace(i = 0, j = 0) :
        if (i == 8) and (j == 9) :
                print('数独填充完毕：')
                printSudoku()
                return
        if j == 9 :
                i += 1
                j = 0
        if matrix[i][j] == 0 :
                for each in range(1, 10) :
                        if suCheck(i, j, each) :
                                matrix[i][j] = each
                                backTrace(i, j + 1)
                                matrix[i][j] = 0
        else :
                backTrace(i, j + 1)

def printSudoku() :
        for i in range(9) :
                for j in range(9) :
                        print(matrix[i][j], end='  ')
                print()
        print()

backTrace()