Recursive Backtracking for Sudoku

Question

I'm still pretty new to coding and I am trying work on slightly harder topics such as modifying the solution for a recursive backtracking program for a sudoku. The original solution is for a sudoku of size 3x3 and I would like mine to work with a normal sized sudoku (9x9). The 3x3 solution is found here.

I feel like I understand the algorithm well enough: for each list(holding the possible values for that cell) in the grid, try each numberand at each step, ensure that the board is still valid, move onto the next list, assign a possible number until its valid, etc. backtracking to the last board that was still valid should the current one be incorrect.

edit: Added a few functions to narrow down on the possible values for each empty cell, as well as filling in cells that only have one possible value. I have verified these functions are working properly. fill_zeros is only called when initializing the sudoku. make_nodes constructs up-to-date nodes from the board. node_to_board takes in a board in node-format and returns a board in row-format. The refine_by functions are self-explanatory.

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

Here are the (edited) auxiliary functions:

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 gets passed a list, which it loops through to ensure every item is unique (return True), returning False otherwise.

is_valid contains the broken down sections of the board: rows, columns and nodes (each 3x3 square). It then passes each piece of the board to is_distinct.

The (edited) recursive function is

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

And the setup is:

#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)

edit: Taking Prune's advice, I threw in a couple print calls to output some useful info. After tracking the output, I believe the issue lies in how the program backtracks after running through every possible output. For example: in the output, the board is valid until it reaches (3,8), it then runs through the outputs and instead of backtracking to an earlier cell, instead it moves on to the next empty(4,1). In addition, it seems the backtracking might go too far when it does; toward the end of the output, it says it is trying a new value at (0,1) even though the first guess (1) was the correct value.

I have tried looking at others' sudoku solutions of similar style, but can't seem to figure out where I'm going wrong.

edit: Sample in: 3 0 6 5 0 8 4 0 0 5 2 0 0 0 0 0 0 0 0 8 7 0 0 0 0 3 1 0 0 3 0 1 0 0 8 0 9 0 0 8 6 3 0 0 5 0 5 0 0 9 0 6 0 0 1 3 0 0 0 0 2 5 0 0 0 0 0 0 0 0 7 4 0 0 5 2 0 6 3 0 0

Sample out:

[[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

Correct out: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

Correct answer in sudoku format:

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

Could you provide a sample input, so we can go straight to solving your problem rather than recreating your inputs? — Arya McCarthy
Also—just a comment—you could switch to a 2D numpy array to exploit "fancy indexing". It would drastically cut down on 1) time, e.g. when copying 2) lines of code in is_valid. In general, there are some un-pythonic things going on here that will slow you down. Once your problem is resolved, I'd swing by Code Review. — Arya McCarthy
I'm also curious—does it still take forever when you have a full board minus one cell? — Arya McCarthy
Sure: sample input is: 3 0 6 5 0 8 4 0 0 5 2 0 0 0 0 0 0 0 0 8 7 0 0 0 0 3 1 0 0 3 0 1 0 0 8 0 9 0 0 8 6 3 0 0 5 0 5 0 0 9 0 6 0 0 1 3 0 0 0 0 2 5 0 0 0 0 0 0 0 0 7 4 0 0 5 2 0 6 3 0 0 — Z. Winters
expected output is 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 (although mine will still be in lists for this purpose) — Z. Winters

Unknown Unknown · Accepted Answer · 2017-07-26T16:41:43

Solved by OP. The working code is:

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)

Sample in: 3 0 6 5 0 8 4 0 0 5 2 0 0 0 0 0 0 0 0 8 7 0 0 0 0 3 1 0 0 3 0 1 0 0 8 0 9 0 0 8 6 3 0 0 5 0 5 0 0 9 0 6 0 0 1 3 0 0 0 0 2 5 0 0 0 0 0 0 0 0 7 4 0 0 5 2 0 6 3 0 0

Sample out:

[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]

Recursive Backtracking for Sudoku

1 Answers