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

经常在休闲时间玩玩数独游戏作为休息手段，一般使用手段是去除重复，找到唯一的数据先填上，然后在来一步一步填上，但是还是难免有需要猜个数字，根据反馈来做，那么有没有一个比较好的算法解决数独问题呢，这里就使用回溯法用python解决9✖️9 的数独难题。回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，我们那么使用python解决数独步骤分为以下几步。

步骤：

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

数组表示数独表格

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

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

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

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