CODEWITHSUNDEEP
pythonrecursionbacktrackingsudoku
snatchysquid
snatchysquid

Reputation: 1352

How does the following recursive Sudoku solving function work?

I recently watched this video showing a recursive function to solve sudoku and this seems irrational, since at the end we always change the value back to zero in the end.

How come the function worked in the video but doesnt work for me? Should the grid remain the same for both of us since at the end we use grid[y][x] = 0 which resets the grid discarding all changes made?

The idea of this code is to iterate over each number cell and each number (1-9) and check if it is possible to put the number in that cell. if we reach a dead end we backtrack.

Here's the code I manually copied:

import numpy as np
global grid
grid = [[5,3,0,0,7,0,0,0,0],
        [6,0,0,1,9,5,0,0,0],
        [0,9,8,0,0,0,0,6,0],
        [8,0,0,0,6,0,0,0,3],
        [4,0,0,8,0,3,0,0,1],
        [7,0,0,0,2,0,0,0,6],
        [0,6,0,0,0,0,2,8,0],
        [0,0,0,4,1,9,0,0,5],
        [0,0,0,0,8,0,0,7,9]]

def possible(y,x,n):
    global grid
    for i in range(0, 9):
        if grid[y][i] == n:
            return False
    for i in range(0, 9):
        if grid[i][x] == n:
            return False
    x0 = (x//3)*3
    y0 = (y//3)*3
    for i in range(0, 3):
        for j in range(0, 3):
            if grid[y0+i][x0+j] == n:
                return False
    return True

def solve():
    global grid
    for y in range(9):
        for x in range(9):
            if grid[y][x] == 0:
                for n in range(1, 10):
                    if possible(y,x,n):
                        grid[y][x] = n
                        solve()
                        grid[y][x] = 0
                return


print(np.matrix(grid))
print("")
solve()
print(np.matrix(grid))

Upvotes: 1

Views: 103

Answers (2)

Oli
Oli

Reputation: 2602

The problem is that the solve function does indeed reset the grid back to its initial state after has finished executing, but it also solves the sudoku.

In the video, note that the grid is printed inside the solve function, not after it:

def solve():
    global grid
    for y in range(9):
        for x in range(9):
            if grid[y][x] == 0:
                for n in range(1, 10):
                    if possible(y,x,n):
                        grid[y][x] = n
                        solve()
                        grid[y][x] = 0
                return
    print(np.matrix(grid))

print(np.matrix(grid))
print("")
solve()

This works because it loops through every cell and only recurses if the cell does not yet have a value filled in, and then after it has tried every value, it returns. The only way it will complete the for y in range(9): loop is if it never finds a cell that is not 0, i.e. if the sudoku is solved, so by printing the matrix after the loop completes it will ensure that it prints the solved sudoku.

Upvotes: 2

ggorlen
ggorlen

Reputation: 56895

Your algorithm is working fine but you don't do anything with the grid when you find a solution. Once a solution is discovered, the backtracking zeroes out all of the cells it's filled in as it unwinds the call stack. By the time you get back to the main scope and print the result, it's back to its original state.

Your algorithm ends when you've iterated all of the rows and columns in a call to solve and find that there are no zeroes left to fill in. After your loops end, print (or better yet, return) the result and you'll see the completed puzzle.

Also, better to pass grid as a parameter to solve rather than use the global keyword. Sharing state like this makes it far too easy to introduce bugs.

Upvotes: 0

Related Questions