Возврат в решателе судоку не работает

Я пишу решатель судоку на Python, который принимает частично заполненную доску и использует обратное отслеживание и прямую проверку, чтобы заполнить остальное и решить головоломку. Прямая проверка - это когда каждый раз, когда вы присваиваете значение пустой ячейке, вы проверяете, есть ли у ее неназначенных «соседей» строки, столбца и поля непустые домены после назначения.

Чтобы представить мою доску (размеры: N x N доска с полями P x Q), я использую 2D-список, в котором каждая запись имеет форму [значение, [домен]], где значение - это присвоенный номер ячейки. (0, если не назначено) и домен - это возможные значения для ячейки, которые будут поддерживать согласованность головоломки судоку.

Я считаю, что делаю что-то не так с моей рекурсией, но не могу понять, что именно. Функция всегда терпит неудачу и возвращает False. Ниже приведена часть моей рекурсивной функции решателя с извлеченным кодом предварительной обработки. При необходимости я могу опубликовать всю функцию и ее вспомогательные функции.

def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
    ###some preprocessing here to check if puzzle is solved and find next empty cell if not

    vals = board[row][col][1] #domain/possible values for the empty cell
    for num in vals:
        #if num doesn't violate the row, col, and box sudoku constraints
        if constraintCheck(row, col, num, P, N, Q, board):
            #make copy of cell's domain for backtracking
            tempDomain = copy.deepcopy(board[row][col][1])

            board[row][col][0] = num        #assign num to the cell

            #remove num from domains of neighbors,
            #if an empty domain results after removing num, 
            #return False and the original board,
            #else return True and the updated board
            noEmptyDomains, board = propagate_fc(board, N, P, Q, row, col, num)
            if noEmptyDomains:
                board[row][col][1] = [num]  #update domain to be num and then recurse
                if fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
                    return True
                #backtrack -- reset value and domain of assigned cell
                board[row][col][1] = tempDomain
                board[row][col][0] = 0
            else:
                board[row][col][0] = 0
    return False

РЕДАКТИРОВАТЬ: больше кода и опробовать решение Blckknght

def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
    if time.clock() >= timeout:
        return "timeout"

    while row < N and board[row][col][0] != 0: #find next blank
        if col == N-1:
            row = row + 1
            col = 0
        else:
            col = col + 1

    if row == N: #solved
        return True

    for num in vals:
        if constraintCheck(row, col, num, P, N, Q, board):
            board[row][col][0] = num
            noEmptyDomains, new_board = propagate_fc(board, N, P, Q, row, col, num) # new var
            if noEmptyDomains:
                new_board[row][col][1] = [num]   # this doesn't modify board, only new_board
                if fc_recursive_solve(new_board, N, P, Q, row, col, outputFile, timeout):
                    return True
            board[row][col][0] = 0   # the only thing that's required to backtrack
    return False

def propagate_fc(board, N, P, Q, row, col, num):
    origBoard = copy.deepcopy(board)
    #row propagate
    for x in range(N):
        if board[x][col][0] == 0:
            if num in board[x][col][1]:
                board[x][col][1].remove(num)
        if len(board[x][col][1]) == 0:
            return False, origBoard #domain is empty; return original board

    #col propagate
    for y in range(N):
        if board[row][y][0] == 0:
            if num in board[row][y][1]:
                board[row][y][1].remove(num)
        if len(board[row][y][1]) == 0:
            return False, origBoard #domain is empty

    #box propagate
    rDiv = row/P
    cDiv = col/P
    for i in range((rDiv * P), ((rDiv + 1) * P)):
        for j in range((cDiv * Q), ((cDiv + 1) * Q)):
            if board[i][j][0] == 0:
                if num in board[i][j][1]:
                    board[i][j][1].remove(num)
            if len(board[i][j][1]) == 0:
                return False, origBoard #domain is empty

    return True, board #success; return board with updated domains