Python Sudoku Recursion with Brute Force Backtracking Error

Question

I am doing a Sudoku puzzle solver for homework, but am encountering some difficulty. The code right now cycles past the solution, although it does reach it for easy puzzles, and for harder puzzles, it gets stuck with several 9's for no apparent reason. I would appreciate any help on this. (check_cell determines if the placement is valid or not.)

1. Is backtracking implemented correctly in this code, and if not, how would that be fixed?
2. How can I stop the solver from freezing? It solves around 3 rows and then freezes, changing most of the values to 9s.

Some code:

def solve_helper(self, row, col):
# Try placing a number in each column of current row
    board = self.the_board
    if board[row][col] != 0:
        ?????
    elif board[row][col] == 0:
        for i in range(1,10):
            print("Setting value at i with ") + str (i) + (" located at " ) + str(row) + str(col)
            self.set_cell(row, col, i)
            self.guesses = self.guesses + 1
            if self.check_cell(row, col):
                if self.solve_helper(row, col): return True
            else:
                self.set_cell(row, col, 0)
    else:
        return self.mover(row,col)
    return False

def mover(self, row, col):
    if col + 1 != 9:
        return self.solve_helper(row, (col+1))
    elif row + 1 != 9:
        print "Moving to row" + str(row + 1)
        return self.solve_helper((row+1),0)
    else:
        print "SOLUTION FOUND"
        return True

Answer 1

The trouble you're having is that some of your recursive calls are not returning the results properly, so your solution, when it is found, gets forgotten about a few levels up the recursive stack. Here's the first fix that you need, adding return to the recursive calls made in mover:

def mover(self, row, col):
    if col + 1 != 9:
        return self.solve_helper(row, (col+1))  # added return
    elif row + 1 != 9:
        print "Moving to row" + str(row + 1)
        return self.solve_helper((row+1),0)     # here too
    else:
        print "SOLUTION FOUND"
        return True

You also need something similar in the special case of your solve_helper function where you skip over pre-solved cells. The end of the function should be:

else:
    return self.mover(row, col)  # added return
return False

Edit:

Ok, I've found a few more issues in the code. Two of them are logic issues with the solver, and one is a display issue that doesn't cause any real problems other than looking strange during the solving.

The issues:

1. First, you're latest code has solve_helper calling itself, rather than calling mover. This makes it take an extra function call before moving (though I think it may not actually break the solver).
2. Second, if solve_helper sets a cell to 9, but then in backtracked to (after some later cells couldn't be solved), the 9 doesn't get reset to zero before backtracking further.
3. And lastly, the display issue. Setting cells to 0 doesn't stop their old value from being displayed. This looked a lot like the issue in #2, (with 9s being left behind after backtracking) but in fact it is only cosmetic.

The first issue is easy to fix. Just change the solve_helper call to a mover call instead. That's actually what you had in the original code you put in the question. Calling solve_helper directly doesn't actually get the wrong result (since solve_helper will skip the already filled out cell the second time), but it adds an unnecessary extra function call to each level of your recursion.

The second issue is a little more complicated, and this is where you are getting stuck on some boards. What you need to do is move the line that does self.set_cell(row, col, 0) out of the else block it is currently in. In fact, you can actually move it outside of the loop entirely, if you want (since it only really is necessary if you're backtracking after none of the values for the current cell worked). Here is what I think this is the best arrangement of the for loop (also moving the return False statement up):

for i in range(1,10):
    print("Setting value ") + str (i) + (" at " ) + str(row) + ", " + str(col)
    self.set_cell(row, col, i)
    self.guesses = self.guesses + 1
    if self.check_cell(row, col):
        if self.mover(row, col):
            return True
print "Backtracking"
self.set_cell(row, col, 0)
return False

Finally, fixing the display issue requires two changes. First, get rid of the conditional in set_cell. You want to update the display always. Next, in update_textfield, move the delete call outside of the if block so that it always happens (leave the insert under the if). This makes it so that setting a cell to zero will erase the previous value, but not make it display an actual 0 character (it will show nothing).

I think this should do it. Note that the algorithm you're using is still pretty slow. Solving a board I found on the internet in a quick Google search took 122482 guesses and more than 5 minutes, but it did finally work. Other boards (especially those that require 8s or 9s in the first few open spaces) may take even longer.