用python解数独

1、思路

使用递归与回溯的方法，从开头一直往后在数字为0的地方用1到9按顺序试，成功就填下一个空格，走到无路可走就回到上一层重新试下一个数字，直至完成。
数独用数组表示 ，空值用0表示。

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

2、开始实施

(1)、写一个验证数字是否合格的函数

def check(board,r,c,value):
    for item in board[r]:#判断行内是否重复
        if item==value:
            return False

    for item in board:#判断列内是否重复
        if item[c]==value:
            return False

    for row in board[(r//3)*3:(r//3)*3+3]:#判断宫内是否重复
        for item in row[(c//3)*3:(c//3)*3+3]:
            if item==value:
                return False

    return True

(2)、写一个打印展示数独的函数

def show(board):
    for r in range(9):
        for c in range(9):
            print(board[r][c],end=' ')
        print('')

(3)、主函数

def sudoku(board):
    for r in range(9):
        for c in range(9):
            if r==8 and c==8 and board[r][c]!=0:
                print('------answer------')
                show(board)
                print('------------------')
            if board[r][c]==0:
                for n in range(1,10):
                    if check(board,r,c,n):
                        board[r][c]=n
                        if not sudoku(board):
                            board[r][c]=0
                return False

3、测试

在文件的底部添加以下代码

if __name__=='__main__':
    board=[
        [8,0,0,0,0,0,0,0,0],
        [0,0,3,6,0,0,0,0,0],
        [0,7,0,0,9,0,2,0,0],
        [0,5,0,0,0,7,0,0,0],
        [0,0,0,8,4,5,7,0,0],
        [0,0,0,1,0,0,0,3,0],
        [0,0,1,0,0,0,0,6,8],
        [0,0,8,5,0,0,0,1,0],
        [0,9,0,0,0,0,4,0,0]]
    print('------subject------')
    show(board)
    print('-------------------')
    sudoku(board)

运行测试