sudoku_solver.py

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

'''
 Should return
 [[5,3,4,6,7,8,9,1,2],
  [6,7,2,1,9,5,3,4,8],
  [1,9,8,3,4,2,5,6,7],
  [8,5,9,7,6,1,4,2,3],
  [4,2,6,8,5,3,7,9,1],
  [7,1,3,9,2,4,8,5,6],
  [9,6,1,5,3,7,2,8,4],
  [2,8,7,4,1,9,6,3,5],
  [3,4,5,2,8,6,1,7,9]]
  '''


class SudokuSolver():
    def __init__(self, puzzle):
        self.puzzle = puzzle
        self.remaining = self.count_remaining()

    def get(self, x, y):
        return(self.puzzle[y][x])

    def get_row(self, y):
        return [x for x in self.puzzle[y] if x != 0]

    def get_col(self, x):
        return [i[x] for i in self.puzzle if i[x] != 0]

    def get_sqaure(self, x, y):
        x = x // 3
        y = y // 3
        out = []
        for i in range(3 * y, 3 * y + 3):
            for j in range(3 * x, 3 * x + 3):
                if self.puzzle[i][j] != 0:
                    out.append(self.puzzle[i][j])
        return out

    def check(self, x, y):
        data = self.get(x, y)
        if data != 0:
            return data
        else:
            res = set(range(1, 10)) - set(self.get_row(y))
            res = res.intersection(set(range(1, 10)) - set(self.get_col(x)))
            res = res.intersection(set(range(1, 10)) -
                                   set(self.get_sqaure(x, y)))
            if len(res) == 1:
                return list(res)[0]
            else:
                return 0

    def count_remaining(self):
        zeros = 0
        for i in range(len(self.puzzle)):
            for j in range(len(self.puzzle)):
                if self.puzzle[i][j] == 0:
                    zeros += 1
        return zeros

    def solve(self):
        prev_count = self.remaining
        i = 0
        while 1:
            i += 1
            for i in range(0, 9):
                for j in range(0, 9):
                    self.puzzle[j][i] = self.check(i, j)
            count = self.count_remaining()
            if prev_count == count:
                return -1
            elif count == 0:
                return i
            prev_count = count

    def __str__(self):
        out = ''
        for i in range(len(puzzle)):
            for j in range(len(puzzle)):
                out += str(puzzle[i][j]) + ','
            out += '\n'
        return out


solver = SudokuSolver(puzzle)
print(solver.solve())