数独的递归回溯

Question

我对编码还是很陌生的，我正在尝试一些稍微困难的主题，例如修改数独递归回溯程序的解决方案。最初的解决方案是针对大小为3x3的数独，我希望我的解决方案可以与正常大小的数独（9x9）一起使用。3x3解决方案在这里找到。

我觉得我对算法非常了解：对于网格中的每个列表（包含该单元格的可能值），在每一步尝试每个数字，确保电路板仍然有效，移动到下一个列表，分配一个可能的数字直到其有效，等等。如果当前电路板不正确，则回溯到最后一个仍然有效的电路板。

编辑：添加了一些函数来缩小每个空单元格的可能值，以及填充只有一个可能值的单元格。我已经验证了这些函数是否正常工作。fill_zeros仅在初始化数独时调用。make_nodes从板构造最新节点。node_to_board以节点格式接收板并以行格式返回板。refine_by函数是不言自明的。

def make_nodes(board):
    nodes = [[board[0][0], board[0][1], board[0][2],
             board[1][0], board[1][1], board[1][2],
             board[2][0], board[2][1], board[2][2]],
             [board[0][3], board[0][4], board[0][5],
              board[1][3], board[1][4], board[1][5],
              board[2][3], board[2][4], board[2][5]],
             [board[0][6], board[0][7], board[0][8],
              board[1][6], board[1][7], board[1][8],
              board[2][6], board[2][7], board[2][8]],
             [board[3][0], board[3][1], board[3][2],
              board[4][0], board[4][1], board[4][2],
              board[5][0], board[5][1], board[5][2]],
             [board[3][3], board[3][4], board[3][5],
              board[4][3], board[4][4], board[4][5],
              board[5][3], board[5][4], board[5][5]],
             [board[3][6], board[3][7], board[3][8],
              board[4][6], board[4][7], board[4][8],
              board[5][6], board[5][7], board[5][8]],
             [board[6][0], board[6][1], board[6][2],
              board[7][0], board[7][1], board[7][2],
              board[8][0], board[8][1], board[8][2]],
             [board[6][3], board[6][4], board[6][5],
              board[7][3], board[7][4], board[7][5],
              board[8][3], board[8][4], board[8][5]],
             [board[6][6], board[6][7], board[6][8],
              board[7][6], board[7][7], board[7][8],
              board[8][6], board[8][7], board[8][8]]
             ]
    return nodes


def fill_zeros(board):
    nodes = make_nodes(board)
    allnums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    for i in range(9):
        for j in range(9):
            possible = [h for h in allnums if h not in nodes[i]]
            if nodes[i][j] == 0:
                nodes[i][j] = possible
    return nodes


def node_to_board(nodes):
    board = []
    for y in range(3):
        for i in range(0,9, 3):
            for node in nodes[(y*3):((y+1)*3)]:
                for x in range(3):
                    board.append(node[i+x])
    board = [board[pos:pos + 9] for pos in range(0, 9 * 9, 9)]
    return board


def refine_empty_by_col(board):
    for col in range(9):
        col_done = []
        for row in range(9):
            if type(board[row][col]) == int:
                col_done.append(board[row][col])
        for row in range(9):
            if type(board[row][col]) == list:
                board[row][col] = [x for x in board[row][col] if x not in col_done]
        for row in range(9):
            if type(board[row][col]) == list:
                if len(board[row][col]) == 1:
                    k = board[row][col].pop()
                    board[row][col] = k
    return board


def refine_empty_by_row(board):
    for row in range(9):
        row_done = []
        for col in range(9):
            if type(board[row][col]) == int:
                row_done.append(board[row][col])
        for col in range(9):
             if type(board[row][col]) == list:
                board[row][col] = [x for x in board[row][col] if x not in row_done]
        for col in range(9):
            if type(board[row][col]) == list:
                if len(board[row][col]) == 1:
                    k = board[row][col].pop()
                    board[row][col] = k
    return board

def refine_empty_by_node(board):
    nodes = make_nodes(board)
    allnums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    for node in range(9):
        taken = [x for x in allnums if x in nodes[node]]
        for item in range(9):
            if type(nodes[node][item]) == list:
                nodes[node][item] = [x for x in nodes[node][item] if x not in taken]
                if len(nodes[node][item]) == 1:
                    k = nodes[node][item].pop()
                    taken.append(k)
                    nodes[node][item] = k
        node_list_nums = []
        for item in range(9):
            if type(nodes[node][item]) == list:
                node_list_nums += nodes[node][item]
        node_list_nums = [x for x in node_list_nums if node_list_nums.count(x) == 1]
        for item in range(9):
            if type(nodes[node][item]) == list:
                if any(nodes[node][item]) in node_list_nums:
                    for x in node_list_nums:
                        if x in nodes[node][item]:
                            nodes[node][item] = x
                            node_list_nums.remove(x)

    board = node_to_board(nodes)
    return board

def refine_easy_style(board):
    board_after = board
    board_orig = []
    while board_orig != board_after:
        board_orig = board_after
        board_after = refine_empty_by_col(board_orig)
        board_after = refine_empty_by_row(board_after)
        board_after = refine_empty_by_node(board_after)

    return board_after

以下是（编辑过的）辅助功能：

def is_distinct(passed):
    used = []
    for item in passed:
        if type(item) == list:
            continue
        if item in used:
            return False
        used.append(item)
    return True

def is_valid(board):
    for i in range(9):
        row = [board[i][row] for row in range(9)]
        if not is_distinct(row):
            return False

        col = [board[row][i] for row in range(9)]
        if not is_distinct(col):
            return False

    for node in make_nodes(board):
        if not is_distinct(node):
            return False

    return True

is_distinct获得一个列表，它循环通过该列表以确保每个项目都是唯一的（return True），否则返回False。

是否有效包含电路板的细分部分：行、列和节点（每个3x3正方形）。然后，它将每一块电路板传递给is_distinct。

（编辑过的）递归函数是

def solve_puzzle(board):
    empties = 0
    for row in board:
        for item in row:
            if type(item) == list:
                empties += 1

    if empties == 0:
        if is_valid(board):
            return board
        else:
            print('0 empties')
            return False

    for i in range(9):
        for j in range(9):
            if type(board[i][j]) == list:
                board2 = board
                for k in board2[i][j]:
                    print('trying = {}, cell-list ={}, coords = {},{}'.format(k, board2[i][j], i, j))
                    board2[i][j] = k
                    if is_valid(board2) and solve_puzzle(board2):
                        return True
                    else:
                        print('{} at slot {}, {} didnt work.'.format(k, i , j))
                    print('Backtracking here...')
                    board2[i][j] = board[i][j]
    return False

设置是：

#below this line works
inp = [int(x) for x in input().split()]
empties = inp.count(0)
board = [inp[pos:pos+9] for pos in range(0, 9*9, 9)]
board = node_to_board(fill_zeros(board))
print(board)
board = refine_easy_style(board)
print(board)
#above this line works
# below this line is testing
board = solve_puzzle(board)
print(board)

编辑：听了Prune的建议，我打了几个打印电话来输出一些有用的信息。在跟踪输出后，我认为问题在于程序在运行完所有可能的输出后如何回溯。例如：在输出中，电路板在达到（3,8）之前是有效的，然后在输出中运行，而不是回溯到之前的单元，而是移动到下一个空单元（4,1）。此外，回溯可能会走得太远；虽然第一次尝试的结果是正确的，但它表示第一次尝试的结果是正确的。

我曾尝试过其他类似风格的数独解决方案，但似乎不知道我错在哪里。

编辑：样本输入：3 0 6 5 0 8 4 0 0 5 2 0 0 0 0 0 0 8 0 0 0 0 0 0 0 3 0 0 0 8 0 0 8 6 0 5 0 0 0 0 9 0 0 0 6 0 1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0

样本：

[[3, [1, 4, 9], 6, 5, [1, 2, 3, 4, 6, 7, 9], 8, 4, [2, 5, 6, 7, 8, 9], [2, 5, 6, 7, 8, 9]], [5, 2, [1, 4, 9], [1, 2, 3, 4, 6, 7, 9], [1, 2, 3, 4, 6, 7, 9], [1, 2, 3, 4, 6, 7, 9], [2, 5, 6, 7, 8, 9], [2, 5, 6, 7, 8, 9], [2, 5, 6, 7, 8, 9]], [[1, 4, 9], 8, 7, [1, 2, 3, 4, 6, 7, 9], [1, 2, 3, 4, 6, 7, 9], [1, 2, 3, 4, 6, 7, 9], [2, 5, 6, 7, 8, 9], 3, 1], [[1, 2, 4, 6, 7, 8], [1, 2, 4, 6, 7, 8], 3, [2, 4, 5, 7], 1, [2, 4, 5, 7], [1, 2, 3, 4, 7, 9], 8, [1, 2, 3, 4, 7, 9]], [9, [1, 2, 4, 6, 7, 8], [1, 2, 4, 6, 7, 8], 8, 6, 3, [1, 2, 3, 4, 7, 9], [1, 2, 3, 4, 7, 9], 5], [[1, 2, 4, 6, 7, 8], 5, [1, 2, 4, 6, 7, 8], [2, 4, 5, 7], 9, [2, 4, 5, 7], 6, [1, 2, 3, 4, 7, 9], [1, 2, 3, 4, 7, 9]], [1, 3, [2, 4, 6, 7, 8, 9], [1, 3, 4, 5, 7, 8, 9], [1, 3, 4, 5, 7, 8, 9], [1, 3, 4, 5, 7, 8, 9], 2, 5, [1, 6, 8, 9]], [[2, 4, 6, 7, 8, 9], [2, 4, 6, 7, 8, 9], [2, 4, 6, 7, 8, 9], [1, 3, 4, 5, 7, 8, 9], [1, 3, 4, 5, 7, 8, 9], [1, 3, 4, 5, 7, 8, 9], [1, 6, 8, 9], 7, 4], [[2, 4, 6, 7, 8, 9], [2, 4, 6, 7, 8, 9], 5, 2, [1, 3, 4, 5, 7, 8, 9], 6, 3, [1, 6, 8, 9], [1, 6, 8, 9]]]
[[3, [1, 9], 6, 5, 7, 8, 4, [2, 9], [2, 9]], [5, 2, [1, 9], [1, 3, 4], [3, 4], [1, 4], [7, 8, 9], [6, 9], [6, 7, 8, 9]], [4, 8, 7, 6, 2, 9, 5, 3, 1], [[2, 6, 7], [4, 6, 7], 3, [4, 7], 1, [2, 4, 5, 7], [7, 9], 8, [2, 7, 9]], [9, [1, 4, 7], [1, 2, 4], 8, 6, 3, [1, 7], [1, 2, 4], 5], [[2, 7, 8], 5, [1, 2, 4, 8], [4, 7], 9, [2, 4, 7], 6, [1, 2, 4], [2, 3, 7]], [1, 3, [4, 8, 9], [4, 7, 9], [4, 8], [4, 7], 2, 5, [6, 8, 9]], [[2, 6, 8], [6, 9], [2, 8, 9], [1, 3, 9], [3, 5, 8], [1, 5], [1, 8, 9], 7, 4], [[7, 8], [4, 7, 9], 5, 2, [4, 8], 6, 3, [1, 9], [8, 9]]]
trying = 1, board-list =[1, 9], coords = 0,1
trying = 2, board-list =[2, 9], coords = 0,7
trying = 2, board-list =[2, 9], coords = 0,8
2 at slot 0, 8 didnt work.
Backtracking here...
trying = 9, board-list =2, coords = 0,8
trying = 1, board-list =[1, 9], coords = 1,2
1 at slot 1, 2 didnt work.
Backtracking here...
trying = 9, board-list =1, coords = 1,2
trying = 1, board-list =[1, 3, 4], coords = 1,3
trying = 3, board-list =[3, 4], coords = 1,4
trying = 1, board-list =[1, 4], coords = 1,5
1 at slot 1, 5 didnt work.
Backtracking here...
trying = 4, board-list =1, coords = 1,5
trying = 7, board-list =[7, 8, 9], coords = 1,6
trying = 6, board-list =[6, 9], coords = 1,7
trying = 6, board-list =[6, 7, 8, 9], coords = 1,8
6 at slot 1, 8 didnt work.
Backtracking here...
trying = 7, board-list =6, coords = 1,8
7 at slot 1, 8 didnt work.
Backtracking here...
trying = 8, board-list =7, coords = 1,8
trying = 2, board-list =[2, 6, 7], coords = 3,0
trying = 4, board-list =[4, 6, 7], coords = 3,1
trying = 4, board-list =[4, 7], coords = 3,3
4 at slot 3, 3 didnt work.
Backtracking here...
trying = 7, board-list =4, coords = 3,3
trying = 2, board-list =[2, 4, 5, 7], coords = 3,5
2 at slot 3, 5 didnt work.
Backtracking here...
trying = 4, board-list =2, coords = 3,5
4 at slot 3, 5 didnt work.
Backtracking here...
trying = 5, board-list =4, coords = 3,5
trying = 7, board-list =[7, 9], coords = 3,6
7 at slot 3, 6 didnt work.
Backtracking here...
trying = 9, board-list =7, coords = 3,6
trying = 2, board-list =[2, 7, 9], coords = 3,8
2 at slot 3, 8 didnt work.
Backtracking here...
trying = 7, board-list =2, coords = 3,8
7 at slot 3, 8 didnt work.
Backtracking here...
trying = 9, board-list =7, coords = 3,8
9 at slot 3, 8 didnt work.
Backtracking here...
trying = 1, board-list =[1, 4, 7], coords = 4,1
1 at slot 4, 1 didnt work.
Backtracking here...
trying = 4, board-list =1, coords = 4,1
4 at slot 4, 1 didnt work.
Backtracking here...
trying = 7, board-list =4, coords = 4,1
7 at slot 4, 1 didnt work.
Backtracking here...
trying = 1, board-list =[1, 2, 4], coords = 4,2
1 at slot 4, 2 didnt work.
Backtracking here...
trying = 2, board-list =1, coords = 4,2
2 at slot 4, 2 didnt work.
Backtracking here...
trying = 4, board-list =2, coords = 4,2
4 at slot 4, 2 didnt work.
Backtracking here...
trying = 1, board-list =[1, 7], coords = 4,6
1 at slot 4, 6 didnt work.
Backtracking here...
trying = 7, board-list =1, coords = 4,6
7 at slot 4, 6 didnt work.
Backtracking here...
trying = 1, board-list =[1, 2, 4], coords = 4,7
1 at slot 4, 7 didnt work.
Backtracking here...
trying = 2, board-list =1, coords = 4,7
2 at slot 4, 7 didnt work.
Backtracking here...
trying = 4, board-list =2, coords = 4,7
4 at slot 4, 7 didnt work.
Backtracking here...
trying = 2, board-list =[2, 7, 8], coords = 5,0
2 at slot 5, 0 didnt work.
Backtracking here...
trying = 7, board-list =2, coords = 5,0
7 at slot 5, 0 didnt work.
Backtracking here...
trying = 8, board-list =7, coords = 5,0
8 at slot 5, 0 didnt work.
Backtracking here...
trying = 1, board-list =[1, 2, 4, 8], coords = 5,2
1 at slot 5, 2 didnt work.
Backtracking here...
trying = 2, board-list =1, coords = 5,2
2 at slot 5, 2 didnt work.
Backtracking here...
trying = 4, board-list =2, coords = 5,2
4 at slot 5, 2 didnt work.
Backtracking here...
trying = 8, board-list =4, coords = 5,2
8 at slot 5, 2 didnt work.
Backtracking here...
trying = 4, board-list =[4, 7], coords = 5,3
4 at slot 5, 3 didnt work.
Backtracking here...
trying = 7, board-list =4, coords = 5,3
7 at slot 5, 3 didnt work.
Backtracking here...
trying = 2, board-list =[2, 4, 7], coords = 5,5
2 at slot 5, 5 didnt work.
Backtracking here...
trying = 4, board-list =2, coords = 5,5
4 at slot 5, 5 didnt work.
Backtracking here...
trying = 7, board-list =4, coords = 5,5
7 at slot 5, 5 didnt work.
Backtracking here...
trying = 1, board-list =[1, 2, 4], coords = 5,7
1 at slot 5, 7 didnt work.
Backtracking here...
trying = 2, board-list =1, coords = 5,7
2 at slot 5, 7 didnt work.
Backtracking here...
trying = 4, board-list =2, coords = 5,7
4 at slot 5, 7 didnt work.
Backtracking here...
trying = 2, board-list =[2, 3, 7], coords = 5,8
2 at slot 5, 8 didnt work.
Backtracking here...
trying = 3, board-list =2, coords = 5,8
3 at slot 5, 8 didnt work.
Backtracking here...
trying = 7, board-list =3, coords = 5,8
7 at slot 5, 8 didnt work.
Backtracking here...
trying = 4, board-list =[4, 8, 9], coords = 6,2
4 at slot 6, 2 didnt work.
Backtracking here...
trying = 8, board-list =4, coords = 6,2
8 at slot 6, 2 didnt work.
Backtracking here...
trying = 9, board-list =8, coords = 6,2
9 at slot 6, 2 didnt work.
Backtracking here...
trying = 4, board-list =[4, 7, 9], coords = 6,3
4 at slot 6, 3 didnt work.
Backtracking here...
trying = 7, board-list =4, coords = 6,3
7 at slot 6, 3 didnt work.
Backtracking here...
trying = 9, board-list =7, coords = 6,3
9 at slot 6, 3 didnt work.
Backtracking here...
trying = 4, board-list =[4, 8], coords = 6,4
4 at slot 6, 4 didnt work.
Backtracking here...
trying = 8, board-list =4, coords = 6,4
8 at slot 6, 4 didnt work.
Backtracking here...
trying = 4, board-list =[4, 7], coords = 6,5
4 at slot 6, 5 didnt work.
Backtracking here...
trying = 7, board-list =4, coords = 6,5
7 at slot 6, 5 didnt work.
Backtracking here...
trying = 6, board-list =[6, 8, 9], coords = 6,8
6 at slot 6, 8 didnt work.
Backtracking here...
trying = 8, board-list =6, coords = 6,8
8 at slot 6, 8 didnt work.
Backtracking here...
trying = 9, board-list =8, coords = 6,8
9 at slot 6, 8 didnt work.
Backtracking here...
trying = 2, board-list =[2, 6, 8], coords = 7,0
2 at slot 7, 0 didnt work.
Backtracking here...
trying = 6, board-list =2, coords = 7,0
6 at slot 7, 0 didnt work.
Backtracking here...
trying = 8, board-list =6, coords = 7,0
8 at slot 7, 0 didnt work.
Backtracking here...
trying = 6, board-list =[6, 9], coords = 7,1
6 at slot 7, 1 didnt work.
Backtracking here...
trying = 9, board-list =6, coords = 7,1
9 at slot 7, 1 didnt work.
Backtracking here...
trying = 2, board-list =[2, 8, 9], coords = 7,2
2 at slot 7, 2 didnt work.
Backtracking here...
trying = 8, board-list =2, coords = 7,2
8 at slot 7, 2 didnt work.
Backtracking here...
trying = 9, board-list =8, coords = 7,2
9 at slot 7, 2 didnt work.
Backtracking here...
trying = 1, board-list =[1, 3, 9], coords = 7,3
1 at slot 7, 3 didnt work.
Backtracking here...
trying = 3, board-list =1, coords = 7,3
3 at slot 7, 3 didnt work.
Backtracking here...
trying = 9, board-list =3, coords = 7,3
9 at slot 7, 3 didnt work.
Backtracking here...
trying = 3, board-list =[3, 5, 8], coords = 7,4
3 at slot 7, 4 didnt work.
Backtracking here...
trying = 5, board-list =3, coords = 7,4
5 at slot 7, 4 didnt work.
Backtracking here...
trying = 8, board-list =5, coords = 7,4
8 at slot 7, 4 didnt work.
Backtracking here...
trying = 1, board-list =[1, 5], coords = 7,5
1 at slot 7, 5 didnt work.
Backtracking here...
trying = 5, board-list =1, coords = 7,5
5 at slot 7, 5 didnt work.
Backtracking here...
trying = 1, board-list =[1, 8, 9], coords = 7,6
1 at slot 7, 6 didnt work.
Backtracking here...
trying = 8, board-list =1, coords = 7,6
8 at slot 7, 6 didnt work.
Backtracking here...
trying = 9, board-list =8, coords = 7,6
9 at slot 7, 6 didnt work.
Backtracking here...
trying = 7, board-list =[7, 8], coords = 8,0
7 at slot 8, 0 didnt work.
Backtracking here...
trying = 8, board-list =7, coords = 8,0
8 at slot 8, 0 didnt work.
Backtracking here...
trying = 4, board-list =[4, 7, 9], coords = 8,1
4 at slot 8, 1 didnt work.
Backtracking here...
trying = 7, board-list =4, coords = 8,1
7 at slot 8, 1 didnt work.
Backtracking here...
trying = 9, board-list =7, coords = 8,1
9 at slot 8, 1 didnt work.
Backtracking here...
trying = 4, board-list =[4, 8], coords = 8,4
4 at slot 8, 4 didnt work.
Backtracking here...
trying = 8, board-list =4, coords = 8,4
8 at slot 8, 4 didnt work.
Backtracking here...
trying = 1, board-list =[1, 9], coords = 8,7
1 at slot 8, 7 didnt work.
Backtracking here...
trying = 9, board-list =1, coords = 8,7
9 at slot 8, 7 didnt work.
Backtracking here...
trying = 8, board-list =[8, 9], coords = 8,8
8 at slot 8, 8 didnt work.
Backtracking here...
trying = 9, board-list =8, coords = 8,8
9 at slot 8, 8 didnt work.
Backtracking here...
9 at slot 3, 6 didnt work.
Backtracking here...
5 at slot 3, 5 didnt work.
Backtracking here...
trying = 7, board-list =5, coords = 3,5
7 at slot 3, 5 didnt work.
Backtracking here...
7 at slot 3, 3 didnt work.
Backtracking here...
4 at slot 3, 1 didnt work.
Backtracking here...
trying = 6, board-list =4, coords = 3,1
6 at slot 3, 1 didnt work.
Backtracking here...
trying = 7, board-list =6, coords = 3,1
7 at slot 3, 1 didnt work.
Backtracking here...
2 at slot 3, 0 didnt work.
Backtracking here...
trying = 6, board-list =2, coords = 3,0
6 at slot 3, 0 didnt work.
Backtracking here...
trying = 7, board-list =6, coords = 3,0
7 at slot 3, 0 didnt work.
Backtracking here...
8 at slot 1, 8 didnt work.
Backtracking here...
trying = 9, board-list =8, coords = 1,8
9 at slot 1, 8 didnt work.
Backtracking here...
6 at slot 1, 7 didnt work.
Backtracking here...
trying = 9, board-list =6, coords = 1,7
9 at slot 1, 7 didnt work.
Backtracking here...
7 at slot 1, 6 didnt work.
Backtracking here...
trying = 8, board-list =7, coords = 1,6
8 at slot 1, 6 didnt work.
Backtracking here...
trying = 9, board-list =8, coords = 1,6
9 at slot 1, 6 didnt work.
Backtracking here...
4 at slot 1, 5 didnt work.
Backtracking here...
3 at slot 1, 4 didnt work.
Backtracking here...
trying = 4, board-list =3, coords = 1,4
4 at slot 1, 4 didnt work.
Backtracking here...
1 at slot 1, 3 didnt work.
Backtracking here...
trying = 3, board-list =1, coords = 1,3
3 at slot 1, 3 didnt work.
Backtracking here...
trying = 4, board-list =3, coords = 1,3
4 at slot 1, 3 didnt work.
Backtracking here...
9 at slot 1, 2 didnt work.
Backtracking here...
9 at slot 0, 8 didnt work.
Backtracking here...
2 at slot 0, 7 didnt work.
Backtracking here...
trying = 9, board-list =2, coords = 0,7
9 at slot 0, 7 didnt work.
Backtracking here...
1 at slot 0, 1 didnt work.
Backtracking here...
trying = 9, board-list =1, coords = 0,1
9 at slot 0, 1 didnt work.
Backtracking here...
False

更正：3 1 6 5 7 8 4 9 2 5 2 9 1 3 4 7 6 6 2 9 5 3 1 2 6 4 1 5 9 8 7 4 6 3 1 2 5 8 1 7 9 2 6 3 3 1 8 7 2 6 6 9 2 2 3 3 5 1 7 4 7 4 4 4 5 8 3 1 9

数独格式的正确答案：

3 1 6 5 7 8 4 9 2

5 2 9 1 3 4 7 6 8

4 8 7 6 2 9 5 3 1

2 6 3 4 1 5 9 8 7

9 7 4 8 6 3 1 2 5

8 5 1 7 9 2 6 4 3

1 3 8 9 4 7 2 5 6

6 9 2 3 5 1 8 7 4

7 4 5 2 8 6 3 1 9

Answer 1

由OP解决。工作代码为：

def make_nodes(board):
    '''
    make_nodes converts a board compiled of 1x9 rows to a board compiled of 3x3 nodes
    :param board:
    :return nodes:
    '''
    nodes = [[board[0][0], board[0][1], board[0][2],
             board[1][0], board[1][1], board[1][2],
             board[2][0], board[2][1], board[2][2]],
             [board[0][3], board[0][4], board[0][5],
              board[1][3], board[1][4], board[1][5],
              board[2][3], board[2][4], board[2][5]],
             [board[0][6], board[0][7], board[0][8],
              board[1][6], board[1][7], board[1][8],
              board[2][6], board[2][7], board[2][8]],
             [board[3][0], board[3][1], board[3][2],
              board[4][0], board[4][1], board[4][2],
              board[5][0], board[5][1], board[5][2]],
             [board[3][3], board[3][4], board[3][5],
              board[4][3], board[4][4], board[4][5],
              board[5][3], board[5][4], board[5][5]],
             [board[3][6], board[3][7], board[3][8],
              board[4][6], board[4][7], board[4][8],
              board[5][6], board[5][7], board[5][8]],
             [board[6][0], board[6][1], board[6][2],
              board[7][0], board[7][1], board[7][2],
              board[8][0], board[8][1], board[8][2]],
             [board[6][3], board[6][4], board[6][5],
              board[7][3], board[7][4], board[7][5],
              board[8][3], board[8][4], board[8][5]],
             [board[6][6], board[6][7], board[6][8],
              board[7][6], board[7][7], board[7][8],
              board[8][6], board[8][7], board[8][8]]
             ]
    return nodes


def fill_zeros(board):
    '''
    fill_zeros replaces every empty 0 with the possible values for that cell based off given values in its node
    :param board:
    :return board:
    '''
    nodes = make_nodes(board)
    allnums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    for i in range(9):
        for j in range(9):
            possible = [h for h in allnums if h not in nodes[i]]
            if nodes[i][j] == 0:
                nodes[i][j] = possible
    return nodes


def node_to_board(nodes):
    '''
    node_to_board converts a board compiled of 3x3 nodes to a board of 1x9 rows
    :param nodes:
    :return board:
    '''
    board = []
    for y in range(3):
        for i in range(0,9, 3):
            for node in nodes[(y*3):((y+1)*3)]:
                for x in range(3):
                    board.append(node[i+x])
    board = [board[pos:pos + 9] for pos in range(0, 9 * 9, 9)]
    return board


def refine_empty_by_col(board):
    '''
    refine_empty_by_col takes a board with empty cells, and checks each number in the empty cells. If the number
    is already a definitenumber in its own column, remove that number from the possible values for that cell
    :param board:
    :return board:
    '''
    for col in range(9):
        col_done = []
        for row in range(9):
            if type(board[row][col]) == int:
                col_done.append(board[row][col])
        for row in range(9):
            if type(board[row][col]) == list:
                board[row][col] = [x for x in board[row][col] if x not in col_done]
        for row in range(9):
            if type(board[row][col]) == list:
                if len(board[row][col]) == 1:
                    k = board[row][col].pop()
                    board[row][col] = k
    return board


def refine_empty_by_row(board):
    '''
    refine_empty_by_row takes a board with empty cells, and checks each number in the empty cells. If the number is
    already a definite number in its own row, remove that number from the possible values for that cell
    :param board:
    :return board:
    '''
    for row in range(9):
        row_done = []
        for col in range(9):
            if type(board[row][col]) == int:
                row_done.append(board[row][col])
        for col in range(9):
             if type(board[row][col]) == list:
                board[row][col] = [x for x in board[row][col] if x not in row_done]
        for col in range(9):
            if type(board[row][col]) == list:
                if len(board[row][col]) == 1:
                    k = board[row][col].pop()
                    board[row][col] = k
    return board


def refine_empty_by_node(board):
    '''
    refine_empty_by_node takes a board with empty cells, and checks each number in the empty cells. If the number is
    already a definite number in its own node, remove that number from the possible values for that cell
    :param board:
    :return board:
    '''
    nodes = make_nodes(board)
    allnums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    for node in range(9):
        taken = [x for x in allnums if x in nodes[node]]
        for item in range(9):
            if type(nodes[node][item]) == list:
                nodes[node][item] = [x for x in nodes[node][item] if x not in taken]
                if len(nodes[node][item]) == 1:
                    k = nodes[node][item].pop()
                    taken.append(k)
                    nodes[node][item] = k
        node_list_nums = []
        for item in range(9):
            if type(nodes[node][item]) == list:
                node_list_nums += nodes[node][item]
        node_list_nums = [x for x in node_list_nums if node_list_nums.count(x) == 1]
        for item in range(9):
            if type(nodes[node][item]) == list:
                if any(nodes[node][item]) in node_list_nums:
                    for x in node_list_nums:
                        if x in nodes[node][item]:
                            nodes[node][item] = x
                            node_list_nums.remove(x)

    board = node_to_board(nodes)
    return board


def refine_easy_style(board):
    '''
    refine_easy_style takes a "fresh" board and repeatedly calls refine_empty_by_* until no more changes can be made
    using this method.
    :param board:
    :return board:
    '''
    board_after = board
    board_orig = []
    while board_orig != board_after:
        board_orig = board_after
        board_after = refine_empty_by_col(board_orig)
        board_after = refine_empty_by_row(board_after)
        board_after = refine_empty_by_node(board_after)

    return board_after

## above this line works
## below this line is testing


def is_distinct(passed):
    '''
    is_distinct checks to ensure the (node|row|column) is has only unique definite values (True) if not return False
    :param passed:
    :return True if all distinct definites, False otherwise:
    '''
    used = []
    for item in passed:
        if type(item) == list:
            continue
        if item in used:
            return False
        used.append(item)
    return True


def is_valid(board):
    '''
    is_valid ensures the entire board is still valid by checking each row, column and node via is_distinct
    :param board:
    :return True if valid board, False otherwise:
    '''
    for i in range(9):
        row = [board[i][row] for row in range(9)]
        if not is_distinct(row):
            return False

        col = [board[row][i] for row in range(9)]
        if not is_distinct(col):
            return False

    for node in make_nodes(board):
        if not is_distinct(node):
            return False

    return True


def next_empty(board):
    '''
    next_empty finds the next empty cell on the board, based on how many possibilities that empty cell has in
    ascending order
    :param board:
    :return x,y coords:
    '''
    min = [x for x in range(9)]
    row = 0
    col = 0
    for i in range(9):
        for j in range(9):
            if type(board[i][j]) == list:
                if len(board[i][j]) < len(min):
                    min = board[i][j]
                    row = i
                    col = j
    return row, col


def solve_puzzle(board):
    '''
    solve_puzzle recursively calls itself until the board is solved or a solution is not found
    :param board:
    :return True if solved, False if no solution exists:
    '''
    # if there are no empty cells left, ensure the board is valid
    empties = 0
    for row in board:
        for item in row:
            if type(item) == list:
                empties += 1
    if empties == 0:
        return is_valid(board)

    # get the next empty cell coords
    row, col = next_empty(board)
    board2 = board
    possible = board2[row][col]
    # recursive step
    # loop through every possible value until one is valid, backtracking until a valid board is found
    for k in possible:
        board2[row][col] = k
        if is_valid(board2) and solve_puzzle(board2):
            return True
        board2[row][col] = possible
    return False


# read input
inp = [int(x) for x in input().split()]

# make a board from the input (row-format)
board = [inp[pos:pos+9] for pos in range(0, 9*9, 9)]

# fill zeros with possible values, then put it back to row-format
board = node_to_board(fill_zeros(board))

# fill in what is possible without recursion
board = refine_easy_style(board)

# solve the remaining cells with recursion
solve_puzzle(board)
for row in board:
    print(row)

抽样调查：306050804000502007000100010008090806030060605000200505020050505050505050505050505000400050020005060300

样本：

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