递归 | HJ44 Sudoku

# 最优解
class Solution:
 
    def isValue(self, board, x, y):
        # 检查已经填入的坐标是否和列中有的元素相等
        for i in range(9):
            if i != x and board[i][y] == board[x][y]:
                return False
        # 检查已经填入的坐标是否和行中有的元素相等
        for j in range(9):
            if j != y and board[x][j] == board[x][y]:
                return False
 
        # 检查每个正方形是否符合（粗线框内只有1~9）
        m, n = 3*(x // 3), 3*(y // 3)  # 这里求出的是3x3网格的左上角的坐标
        for i in range(3):
            for j in range(3):
                if(i+m != x or j+n != y) and board[i+m][j+n] == board[x][y]:
                    return False 
 
        return True
 
    def dfs(self, board):
 
        for i in range(9):
            for j in range(9):
                if board[i][j] == 0:
                    for k in '123456789':  # 从里面选择一个
                        board[i][j] = int(k)
                        if self.isValue(board, i, j) and self.dfs(board):
                            return True
                        # 回溯
                        board[i][j] = 0
                    # 都不行，说明上次的数字不合理
                    return False
        # 全部便利完，返回True
        return True
 
while True:
    try:
        board = []
        for i in range(9):
            row = list(map(int, input().split()))
            board.append(row)
 
        s = Solution()
        s.dfs(board)
 
        for i in range(9):
            board[i] = list(map(str, board[i]))
            print(' '.join(board[i]))
    except:
        break

# 我的代码（原本不通过，5/6，加入最优解的递归后通过）
import copy
def set_value(board, blanks, d, left):
    N = {"1", "2", "3", "4", "5", "6", "7", "8", "9"}
    for x, y in blanks:
        if d[x, y] == set():
            continue
        # 3*3方块内
        cube = []
        for i in range(x // 3 * 3, x // 3 * 3 + 3):
            for j in range(y // 3 * 3, y // 3 * 3 + 3):
                cube.append(board[i][j])
        d[x, y] = d[x, y] & (N - set(cube)) if d[x, y] else N - set(cube)
        # 交叉行列内
        row, col = board[x], [row[y] for row in board]
        d[x, y] &= (N - set(row)) & (N - set(col))
        # 3*3方块内另两行两列
        pal_r1, pal_r2 = [num for num in range(3) if num != x % 3]
        pal_c1, pal_c2 = [num for num in range(3) if num != y % 3]
        pal_r1, pal_r2 = board[x // 3 * 3 + pal_r1], board[x // 3 * 3 + pal_r2]
        pal_c1, pal_c2 = [row[y // 3 * 3 + pal_c1] for row in board], [
            row[y // 3 * 3 + pal_c2] for row in board
        ]
        for choice in d[x, y]:
            if choice in pal_r1 and choice in pal_r2:
                cube_blank = [
                    j
                    for j in range(y // 3 * 3, y // 3 * 3 + 3)
                    if board[x][j] == "0" and j != y
                ]
                if len(cube_blank) == 0:
                    d[x, y] = {choice}
                    break
                elif len(cube_blank) == 1:
                    another_col = [row[cube_blank[0]] for row in board]
                    if choice in another_col:
                        d[x, y] = {choice}
                        break
                elif len(cube_blank) == 2 and choice in pal_c1 and choice in pal_c2:
                    d[x, y] = {choice}
                    break
            elif choice in pal_c1 and choice in pal_c2:
                cube_blank = [
                    i
                    for i in range(x // 3 * 3, x // 3 * 3 + 3)
                    if board[i][y] == "0" and i != x
                ]
                if len(cube_blank) == 0:
                    d[x, y] = {choice}
                    break
                elif len(cube_blank) == 1:
                    another_row = board[cube_blank[0]]
                    if choice in another_row:
                        d[x, y] = {choice}
                        break
                elif len(cube_blank) == 2 and choice in pal_r1 and choice in pal_r2:
                    d[x, y] = {choice}
                    break

        if len(d[x, y]) == 1:
            board[x][y] = d[x, y].pop()
            left -= 1
    return left


def is_valid(board, x, y):
    for i in range(9):  # 检查列
        if i != x and board[i][y] == board[x][y]:
            return False
    for j in range(9):
        if j != y and board[x][j] == board[x][y]:
            return False
    for i in range(x // 3 * 3, x // 3 * 3 + 3):
        for j in range(y // 3 * 3, y // 3 * 3 + 3):
            if (i != x and j != y) and board[x][y] == board[i][j]:
                return False
    return True


def dfs(board, blanks, d):
    for x, y in blanks:
        if board[x][y] != "0":
            continue
        for v in d[x, y]:
            board[x][y] = v
            if is_valid(board, x, y) and dfs(board, blanks, d):
                return True
            board[x][y] = "0"
        return False
    # 全部遍历完返回true
    return True


while True:
    try:
        board = []
        blanks = []
        for i in range(9):
            row = input().split(" ")
            board.append(row)
            for j, num in enumerate(row):
                if num == "0":
                    blanks.append((i, j))
        d = dict.fromkeys(blanks)
        left = len(blanks)
        while left:
            left_tmp = set_value(board, blanks, d, left)
            if left == left_tmp:  # 陷入死局，一个没填
                board_copy, blanks_copy, d_copy = (
                    copy.deepcopy(board),
                    copy.deepcopy(blanks),
                    copy.deepcopy(d),
                )
                dfs(board_copy, blanks_copy, d_copy)
                board = board_copy
                break
            else:
                left = left_tmp
        for row in board:
            print(" ".join(map(str, row)))

    except:
        break

用时：4h