Brute Force Sudoku Recursion in Python

Question

I have tried to implement the brute force approach to solving a Sudoku puzzle using Python, as explained in the following link: http://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Brute-force_algorithm

I am aware there are other threads with the same question. I have read through all of them and still keep having problems.

Here is my code for recursion:

def recurse(x, k, grid):
    if x > 8:
        for line in grid:
            print line
        raw_input()
    if grid[x][k] == '0':
        for number in '123456789':
            if clear(number, x, k, grid):
                grid[x] = grid[x][0:k] + number + grid[x][k+1:]           
                k += 1
                if k > 8:
                    x += 1
                    k = 0
                recurse(x, k, grid)
                k -= 1
                if k < 0:
                    x -= 1
                    k = 8
    else:
        k += 1
        if k > 8:
            x += 1
            k = 0
        recurse(x, k, grid)  

Basically I keep the Sudoku in an array of 9x9 slots, where grid[x] accesses the xth line of the entire Sudoku and grid[x][k] accesses the kth number at the xth line.

There is a function up there called 'clear' which finds out whether a certain number can fit in that slot or not. I have tested it many times and it works properly. Problem here is that the value 'x' never goes above 8, which means the Sudoku never reaches the end. The recursion stops before all the slots are filled in correctly. I am quite inexperienced in writing recursive methods so please bear with me.

I figured, if a number fits in a slot, then that number is placed within that slot and then k is incremented. If k is above 8, then it means it is end of the line so we skip to the next line. Then the recurse function is called again. If a recurse function ends without being able to call itself again, then this means no number fits in that slot so we have to go back. In that case, k is decremented.

So what is the problem here exactly?

Answer 1

You forgot to reset the cells before backtracking. You're leaving wrong numbers all over the place, and at some point there is no valid number to fill in any more, and execution stops.

---

Add grid[x] = grid[x][0:k] + '0' + grid[x][k+1:] after

k -= 1
if k < 0:
    x -= 1
    k = 8

to fix this.

---

To stop recursing when a solution has been found:

def recurse(x, k, grid):
    if x>8:
        return grid

    if grid[x][k] == '0':
        for number in '123456789':
            if clear(number, x, k, grid):
                grid[x] = grid[x][0:k] + number + grid[x][k+1:]           
                k += 1
                if k > 8:
                    x += 1
                    k = 0
                solution= recurse(x, k, grid)
                if solution:
                    return solution
                k -= 1
                if k < 0:
                    x -= 1
                    k = 8
                grid[x] = grid[x][0:k] + '0' + grid[x][k+1:]      
    else:
        k += 1
        if k > 8:
            x += 1
            k = 0
        return recurse(x, k, grid)