Python Recursive Sudoku Solver

Question

This is recursive Sudoku solve code, this isn't a school assignment. I can't figure out how to get it to "back up" through my previous moves. It gets stuck at the end of the first row since there isn't a valid number for that spot and just keeps trying to find one that fits there. The function I am having problems with is check.

After reading your answers I've gotten closer with this, but it's not quite there. It backs all the way up and exits the recursion

import sys

class Board:

    def __init__(self, grid):
        self.grid = grid
        self.ogrid = grid

    def get_col(self, col):
        column = []
        for i in self.grid:
           column.append(str(i[col]))
        return column

    def get_row(self, row):
        return self.grid[row]

    def check_row(self, r, val):
        row = self.grid[r]
        for i in range(0,9):
            if str(val) in row:
                return False

        return True

    def check_col(self, column, val):
        col = self.get_col(column)
        for i in range(0,9):
            if str(val) in col:
                return False

        return True

    def check_square(self, x, y, val):
        col = (y//3)*3
        row = (x//3)*3
        s = ''
        for i in range(row, row+3):
            for j in range(col, col+3):
                s += str(self.grid[i][j])
        if str(val) in s:
                return False

        return True       

    def check_cell(self, x, y, val):
    if self.check_col(y, val) == False:

        return False
    elif self.check_row(x, val) == False:

        return False
    elif self.check_square(x, y, val) == False:

        return False
    return True


def check(self, x, y):

        if y == 9:
            y = 0
            x += 1

        if x == 9:  
            self.print_board()
            sys.exit()

        if self.ogrid[x][y] == '.':
            for val in range(1,10):
                if self.check_cell(x, y, val): 
                    self.grid[x][y] = str(val)
                    self.check(x, y+1)
                ##I don't think the reset is working and I'm not sure why
                if self.ogrid[x][y] == '.': #reset index
                    self.grid[x][y] = '.'
                    self.print_board() #Notice it never prints a '.' in spots that have changed
        else:
            self.check(x,y+1)
        return

    def print_board(self):
        for i in range(0,9):
            for j in range(0,9):
                sys.stdout.write(self.grid[i][j])
                if j == 2 or j == 5:
                    sys.stdout.write(' ')
            if i == 2 or i == 5:
                sys.stdout.write('\n')
            print('')

def main():

    f = open("./easySudoku.txt",'r')
    s = ''

    grid = []
    row = []
    for line in f:
        s += line
        print line
    s = s.replace(' ','')
    s = s.replace('\n','')

    for i in range(0,9):
        row = []
        for j in range(0,9):
            row.append(s[(i*9) + j])
        grid.append(row)

    sudoku = Board(grid)
    sudoku.check(0,0, 1)

if __name__ == "__main__":
    main()

Here is how the check function is supposed to work

check takes an x and y coordinate for the board and starts at 0,0 it runs through a for loop from 1-9 and sets the first value that works at that index and then moves to the next index. When it reaches the end of a row it moves down one row and back to the first column. If no values work at an index then reset current index to '.' and move index back one and continue counting towards 9. i.e. if current value at index 0,0 is 2 then continue to 3. If 3 works then move forward one index so on and so forth until the board has been filled. For the simplistic answer it tries every value, 1-9, at every empty index

If that's unclear then let me know

Also here is the board that I am using

..6 ..7 3..
.18 ..9 .5.
5.. ... .64

92. .8. ...
... 763 ...
... .9. .75

63. ... ..8
.9. 3.. 52.
..2 4.. 6..

Answer 1

The problem is that you seem to recurse one step for each number you try, that will consume every sane stack. I'd suggest that you use iteration as well and use return in order to do back up (that way you should only use 81 stack frames or so - here it fails when you get a thousand levels of stack frames).

I've done a solver before and it will find the solution quite fast...

Answer 2

What I did to check your code: add this line as the first line of your check method:

raw_input('x: %d, y: %d, val: %d' % (x,y,val))

and print the board after inserting a number.

It looks like your solver makes its first mistake at (x,y) = (0,3). It checks all numbers up to 9 and then puts a 9 there. Per your algorithm, it should put a 1. The hang up is your check_square method. You should have

col = (y//3)*3
row = (x//3)*3

After fixing that, the next bug crops up at (x,y) = (1,8), starting with self.check(1, 8, 1). There are no legal values (using your algorithm up to this point) for this square (all the way up to self.check(1, 8, 9)). So next is called self.check(1, 8, 10). Since val==10, it returns, and then within the call to self.check(1, 8, 9), the final line, self.check(x, y-1, val+1), is called, i.e. self.check(1, 7, 10). It, of course immediately returns as well because val == 10. And we are back to self.check(1, 8, 8) and calling the final line of the method definition. Next to execute is self.check(1, 7, 9), which spawns the next self.check(1, 8, 1). Look familiar? We were here already and have had no state change in the meanwhile. Without even realizing it, this becomes an endless loop.

Was that confusing? Of course it was. There is a reason programmers try to avoid recursion, except when teaching about the concept of recursion. Tracking down these types of recursion bugs is difficult, but with a few print lines, it can be done.

P.S. Your algorithm is interesting. I wonder where you found it... It is definitely not how humans play (with all the guessing and editing). FWIW, I would firstly only insert a value into the board if that value were the only legal move for the square and guess only when all blank squares on the board were ambiguous.

EDIT AFTER YOUR EDITS

Add import copy, part of the standard library, at the top and change in __init__ to self.ogrid = copy.deepcopy(grid). Should solve your problem. See https://stackoverflow.com/a/2612815/2100286. Your method of creating a duplicate version of the grid achieves the same thing.

Answer 3

I don't get this snippet:

        if y == -1:
            y = 8
            x -= 1

If y equals the last position in the row you're setting it to 8, which is the index of the last position in the row? Could this be the reason of why it doesn't proceed properly?

Answer 4

Alright, I fixed my problem!

Here's what I did. I took the advice @Skyking gave me by recursing on index only and not by values per index which I had originally. Second thing I changed was to take @James Pringles advice on how to fix my check_square function and copying grid so ogrid would not change when grid changed. Since I can't give two green checks I gave it to @James Pringle since he/she helped me the most, but I couldn't have gotten it without @Skyking's advice

Here's the finished code

import sys
import copy

class Board:

    def __init__(self, grid):
        self.grid = grid
        self.ogrid = copy.deepcopy(grid)

    def get_col(self, col):
        column = []
        for i in self.grid:
           column.append(str(i[col]))
        return column

    def get_row(self, row):
        return self.grid[row]

    def check_row(self, r, val):
        row = self.grid[r]

        if str(val) in row:
            return False
        return True

    def check_col(self, column, val):
        col = self.get_col(column)

        if str(val) in col:
            return False
        return True

    def check_square(self, x, y, val):
        col = (y//3)*3
        row = (x//3)*3
        s = ''
        for i in range(row, row+3):
            for j in range(col, col+3):
                s += str(self.grid[i][j])

        if str(val) in s:
            return False
        return True       

    def check_cell(self, x, y, val):
        if self.check_col(y, val) == False:
            return False
        elif self.check_row(x, val) == False:
            return False
        elif self.check_square(x, y, val) == False:
            return False
        return True


    def check(self, x, y):

            if y == 9:
                y = 0
                x += 1

            if x == 9:  
                self.print_board()
                sys.exit()

            if self.ogrid[x][y] == '.':
                for val in range(1,10):
                    if self.check_cell(x, y, val): 
                        self.grid[x][y] = str(val)
                        self.check(x, y+1)

                    if self.ogrid[x][y] == '.':
                        self.grid[x][y] = self.ogrid[x][y]                    
            else:
                self.check(x,y+1)
            return True

    def print_board(self):
        for i in range(0,9):
            for j in range(0,9):
                sys.stdout.write(self.grid[i][j])
                if j == 2 or j == 5:
                    sys.stdout.write(' ')
            if i == 2 or i == 5:
                sys.stdout.write('\n')
            print('')

def main():

    f = open("./easySudoku.txt",'r')
    s = ''

    grid = []
    row = []

    for line in f:
        s += line

    s = s.replace(' ','')
    s = s.replace('\n','')

    for i in range(0,9):
        row = []
        for j in range(0,9):
            row.append(s[(i*9) + j])
        grid.append(row)

    sudoku = Board(grid)
    sudoku.check(0,0)
    print('shouldn\'t be here')

if __name__ == "__main__":
    main()