利用python使用回溯法快速解决专家级数独问题

数独很适合拿来解释回溯法，因为它的规则简单，但搜索过程很典型。人手解题时通常会先排除重复项、填唯一值，实在不行再开始试探；而回溯法本质上就是把这个“试探并在失败后撤回”的过程系统化。

这篇文章用 Python 演示如何解决 9x9 数独。核心思想并不复杂：先找到空位，再找出候选数字，逐个尝试，如果后面走不通就回退到上一步继续试。

步骤：

数组表示数独表格
找出需要填补的空位
打印当前数独表格
找出当前可行的数字备选
根据当前数独数组确认当前数字可行性
如果可行，下一个空位，不可行返回上一空位继续,所有空格都填满了说明找到了答案

数组表示数独表格

数独是一个表格，因此数组表示这就是一个二维数组，为了方便表示，如下

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

0表示当前位置还没有任何数字，需要我们填充，数字表示当前存在的数字

找出需要填补的空位

第一步是自己根据数独样子手动填入。这里找空位就是找出数组中的0即可，我们从左到右从上到下一个一个填入，每次找出一个空位即可，代码如下

def find_empty(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if bo[i][j] == 0:
                return (i, j)  # row, col

    return None

打印当前数独表格

使用|和-来表示分割每个9宫格，横竖为3的倍数的时候插入即可。


def print_board(bo):
    for i in range(len(bo)):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - - - ")

        for j in range(len(bo[0])):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")

            if j == 8:
                print(bo[i][j])
            else:
                print(str(bo[i][j]) + " ", end="")

找出当前可行的数字备选

所有可能即为1-9的数字，如果该空格所在的位置，横竖和九宫格存在某一个数字，直接从可用数字中剔除，最后得到数字备选

def find_possible_valid(bo,pos):
    
    num_list = list(range(1,10))
    for i in range(9):
        if bo[pos[0]][i]!=0 and bo[pos[0]][i] in num_list:   #横
            num_list.remove(bo[pos[0]][i])
        if bo[i][pos[1]]!=0 and bo[i][pos[1]] in num_list:    #竖
            num_list.remove(bo[i][pos[1]])
    x,y = pos[0]//3,pos[1]//3
    for i in range(3*x,3*x+3):         #九宫格
        for j in range(3*y,3*y+3):
            if bo[i][j]!=0 and bo[i][j] in num_list:
                num_list.remove(bo[i][j])

    return num_list

根据当前数独数组确认1-9数字可行性

数独要求所有横列所有纵列均不得有重复数字，一旦重复，即返回not valid，表示当前数字不可行


def valid(bo, num, pos):
    # Check row
    for i in range(len(bo[0])):
        if bo[pos[0]][i] == num and pos[1] != i:
            return False

    # Check column
    for i in range(len(bo)):
        if bo[i][pos[1]] == num and pos[0] != i:
            return False

    # Check box
    x = pos[1] // 3
    y = pos[0] // 3

    for i in range(y*3, y*3 + 3):
        for j in range(x * 3, x*3 + 3):
            if bo[i][j] == num and (i,j) != pos:
                return False

    return True

如果可行，下一个空位，不可行返回上一空位继续,所有空格都填满了说明找到了答案

主循环，每次获得一个空格位置，从当前数字备选中一个一个尝试，可行就继续下一个空格，不可行就返回把当前位初始化，继续上一个空格的数字备选方案，直到所有空格都被填满，如果可行，说明数独已经找到了答案。

def solve_suduko(bo):
    find = find_empty(bo)
    if not find:
        return True
    else:
        row, col = find

    for i in find_possible_valid(bo,[row,col]):
        if valid(bo, i, (row, col)):
            bo[row][col] = i

            if solve_suduko(bo):
                return True

            bo[row][col] = 0

    return False

如何验证程序是否真的解出了数独

写完求解器后，最简单的验证方式有两步：

先打印求解前后的棋盘，确认所有 0 都被替换成了 1-9。
再人工检查任意一行、一列和一个 3x3 宫格，确认没有重复数字。

如果你想更严谨一点，也可以额外写一个检查函数，统一验证每一行、每一列和每一个九宫格是否都满足数独规则。

最后总结上面所有代码得到最终数独解决方案。

import time
def print_board(bo):
    for i in range(len(bo)):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - - - ")

        for j in range(len(bo[0])):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")

            if j == 8:
                print(bo[i][j])
            else:
                print(str(bo[i][j]) + " ", end="")

def find_possible_valid(bo,pos):
    
    num_list = list(range(1,10))
    for i in range(9):
        if bo[pos[0]][i]!=0 and bo[pos[0]][i] in num_list:
            num_list.remove(bo[pos[0]][i])
        if bo[i][pos[1]]!=0 and bo[i][pos[1]] in num_list:
            num_list.remove(bo[i][pos[1]])
    x,y = pos[0]//3,pos[1]//3
    for i in range(3*x,3*x+3):
        for j in range(3*y,3*y+3):
            if bo[i][j]!=0 and bo[i][j] in num_list:
                num_list.remove(bo[i][j])

    return num_list
    
    
    
    
def find_empty(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if bo[i][j] == 0:
                return (i, j)  # row, col

    return None

def solve_suduko(bo):
    find = find_empty(bo)
    if not find:
        return True
    else:
        row, col = find

    for i in find_possible_valid(bo,[row,col]):
        if valid(bo, i, (row, col)):
            bo[row][col] = i

            if solve_suduko(bo):
                return True

            bo[row][col] = 0

    return False


def valid(bo, num, pos):
    # Check row
    for i in range(len(bo[0])):
        if bo[pos[0]][i] == num and pos[1] != i:
            return False

    # Check column
    for i in range(len(bo)):
        if bo[i][pos[1]] == num and pos[0] != i:
            return False

    # Check box
    box_x = pos[1] // 3
    box_y = pos[0] // 3

    for i in range(box_y*3, box_y*3 + 3):
        for j in range(box_x * 3, box_x*3 + 3):
            if bo[i][j] == num and (i,j) != pos:
                return False

    return True
if __name__ == "__main__":
    board = [
    [0,0,1,0,0,3,0,0,0],
    [0,0,0,8,5,0,0,0,0],
    [0,4,0,0,2,6,8,0,0],
    [0,7,9,0,0,5,0,0,2],
    [0,0,2,0,0,0,0,0,0],
    [5,0,0,0,0,0,0,0,4],
    [0,0,0,0,0,0,0,2,7],
    [6,0,0,0,4,0,0,0,0],
    [0,0,0,1,9,0,6,8,0]
]

    print_board(board)
    start_time = time.time()
    solve_suduko(board)
    end_time = time.time()
    print("_____________________________\n")
    print_board(board)
    print("time used:{}s".format(end_time-start_time))

运行得到结果1秒钟不到就解决了专家级别的数独游戏。 suduko

总结：

本文主要介绍了使用python用不到一秒钟的时间解决了一道专家级别的数独难题，用到的方法就是回溯法，通过找到备选数字缩小数字查询范围可以极大的减少运行时间。当然这里数独数组还是需要手动输入表格，是个耗时的过程，以后看情况再弄个拍照获取数独表格就可以方便的一键拍照获取数独答案了，这真的是方便。当然大家不要忘了数独游戏的宗旨，是为了锻炼下脑子，而不是为了所谓的答题时间，嘿嘿。