CODEWITHSUNDEEP
pythonrecursionbacktracking
Karl Olufsen
Karl Olufsen

Reputation: 186

backtracking sudoku solver always returns initial board

Like many beginners, I'm trying this simple project, but my algorithm, in the end, returns the initial board I started with, meaning, that there is no viable solution, although for a while it seems to be progressing just fine. I know for a fact that I'm providing it with a valid and solvable sudoku board. I can't seem to figure out my mistake, any input and criticism are greatly appreciated!

test_sudoku = [[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]]

class Solver:
    def __init__(self, grid):
        self.grid = grid

    def check_validity(self, i, j, n):
        if n in self.grid[i]:
            return False

        for row in self.grid:
            if n == row[j]:
                return False

        if i <= 2:
            i = 0
        elif i > 2 and i <= 5:
            i = 3
        else:
            i = 6

        if j <= 2:
            j = 0
        elif j > 2 and j <= 5:
            j = 3
        else:
            j = 6

        box = []
        for row in range(i+3):
            box+= self.grid[row][j:j+3]

        if n in box:
            return False

        return True

    def is_empty(self, i, j):
        if self.grid[i][j] == 0:
            return True
        else:
            return False

    def solve(self):
        for i in range(len(self.grid)):
            for j in range(len(self.grid)):
                if self.is_empty(i,j):
                    for n in range(1, len(self.grid)+1):
                        if self.check_validity(i,j,n):
                            self.grid[i][j] = n
                            self.solve()
                            self.grid[i][j] = 0
                    return 
        for row in self.grid:
            print(row)





if __name__ == "__main__":
    solver = Solver(test_sudoku)
    for row in test_sudoku:
        print(row)
    solver.solve()

Most likely I messed up with recursive calls, but I can't find the mistake.

Upvotes: 0

Views: 85

Answers (1)

Kenneth Andersen
Kenneth Andersen

Reputation: 51

I stumbled in here because I have a similar problem trying to solve the same sudoku in JavaScript. First I changed the box+= to box= and got a slightly better result, but it was very slow and gave lots of answers that were incorrect. Replace your box part with the following:

        for q in range(i,i+3) :
            for w in range(j,j+3) :
                if self.grid[q][w] == n :
                    return False

Upvotes: 1

Related Questions