python回溯算法解数独

0821fzh

记录使用回溯算法解析数独

# 数独计算
import copy


def sudoku_analyze(board):
    def isValid(board, r, c, n):
        for i in range(9):

            if board[r] == n:
                return False

            if board[c] == n:
                return False

            if board[int(r / 3) * 3 + int(i / 3)][int(c / 3) * 3 + i % 3] == n:
                return False
        return True

    def backtrack(board, i, j):
        m, n = 9, 9

        if j == n:
            return backtrack(board, i + 1, 0)

        if i == m:
            return True

        if board[j] != 0:
            return backtrack(board, i, j + 1)

        for ch in range(1, 10):
            if not isValid(board, i, j, ch):
                continue

            board[j] = ch

            if backtrack(board, i, j + 1):
                return True

            board[j] = 0

        return False

    backtrack(board, 0, 0)


# array = [[-1] * 9 for _ in range(9)]# 输入的数独矩阵
array = [
    [0, 0, 0, 6, 0, 4, 7, 0, 0],
    [7, 0, 6, 0, 0, 0, 0, 0, 9],
    [0, 0, 0, 0, 0, 5, 0, 8, 0],
    [0, 7, 0, 0, 2, 0, 0, 9, 3],
    [8, 0, 0, 0, 0, 0, 0, 0, 5],
    [4, 3, 0, 0, 1, 0, 0, 7, 0],
    [0, 5, 0, 2, 0, 0, 0, 0, 0],
    [3, 0, 0, 0, 0, 0, 2, 0, 8],
    [0, 0, 2, 3, 0, 1, 0, 0, 0],
]

array_copy = copy.deepcopy(array)
sudoku_analyze(array_copy)

for i in range(9):

    print("\033[1;30m", end='')  # 白色
    if i % 3 == 0:
        # print('=' * line)
        print('++===+===+===++===+===+===++===+===+===++')
    else:
        print('++---+---+---++---+---+---++---+---+---++')

    for j in range(9):

        print("\033[1;30m", end='')  # 白色
        if j % 3 == 0:
            print('||', end='')
        else:
            print('|', end='')

        print(' ', end='')
        if array[j] == array_copy[j]:
            print("\033[1;37m", end='')  # 红色
        else:
            print("\033[1;31m", end='')  # 灰色

        print(array_copy[j], end='')

        print(' ', end='')

    print("\033[1;30m", end='')  # 白色
    print('||', end='')
    print()

print('=' * line)

Pau250

支持一下楼主

别吵我搞设计啊

感谢分享

hqt

支持 有成品效果吗

kav521

学习了，支持你哦。