Backtracking in sudoku solver failing

Question

I'm writing a sudoku solver in Python that takes in a partially filled in board and uses backtracking and forward checking to fill in the rest and solve the puzzle. Forward checking is where every time you assign a value to a blank cell you check whether its row, col, and box unassigned "neighbors" still have nonempty domains after the assignment.

To represent my board (dimenstions: N x N board with P x Q boxes), I'm using a 2D list in which each entry is of the form [value, [domain]], where value is the assigned number of the cell (0 if unassigned) and domain is the possible values for the cell that would keep the sudoku puzzle consistent.

I believe I am doing something wrong with my recursion but can't figure out what. The function always fails and returns False. Below is a portion of my recursive solver function with the preprocessing code taken out. If necessary, I can post the entire function and its helper functions.

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

EDIT: more code and trying out Blckknght's solution

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

Blckknght · Accepted Answer

If you're doing backtracking you need to be able to return the state of your board to how it was before. Your current code is not doing that. The propagate_fc function modifies board in a way that is not easy to undo.

Since I don't see an easy way to reverse the logic of propagate_fc, I suggest changing the design of the solver so that it makes copies of the board and only modifies the copies before passing them on to further recursive steps. If the copy doesn't lead to a solution, it can be thrown away, rather than trying to write backtracking code to fix it back up.

(I'm sure it is possible to backtrack, it's just not obvious what a good way to keep track of the changes, and figuring it out is too much work for this answer.)

Anyway, here's what I suggest for the modified version of the solver:

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 board

    for num in vals:
        if constraintCheck(row, col, num, P, N, Q, board):
            new_board = copy.deepcopy(board)
            new_board[row][col][0] = num
            if propagate_fc(new_board, N, P, Q, row, col, num):
                new_board[row][col][1] = [num] 
                result = fc_recursive_solve(new_board, N, P, Q, row, col, outputFile, timeout)
                if result is not None and result != "timeout":
                    return result
        return None

I've changed it to return the solved board, if it's successful. Otherwise, you'd get a True response, but not be able to see the result (since the top-level code's board won't be modified).

Here's the changed version of propagate_fc to go with it:

def propagate_fc(board, N, P, Q, row, col, num):
    # no copying any more here

    #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

    #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

    #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

    return board #success; return new board

The only real change here is that I don't bother returning the board, since we're always modifying it in place. Only the bool result is needed (to say if the board is valid or not).

(I'd initially thought there was another issue, with the if len(...) == 0 checks in each block, but it turned out not to be a problem after all. You might get slightly better performance doing those checks only when you've just removed a value from the current board[x][y][1] list (by indenting those blocks by two levels), but it's not likely to be a big performance gain.)

Backtracking in sudoku solver failing

Answers (2)

Related Questions