import os

class Sudoku:
    def __init__(self, puzzle):
        self.puzzle = puzzle

    def print(self):
        for i, row in enumerate(self.puzzle):
            cells = [' %s ' % c if c else ' . ' for c in row]
            print('|'.join([''.join(cells[j:j + 3]) for j in (0, 3, 6)]))
            if i in (2, 5):
                print('---------+---------+---------')

    def solve(self):
        def unused(i, j):
            i_, j_ = i // 3 * 3, j // 3 * 3
            cells = {(i, k) for k in range(9)}
            cells |= {(k, j) for k in range(9)}
            cells |= {(i, j) for i in range(i_, i_ + 3)
                             for j in range(j_, j_ + 3)}

            return set(range(1, 10)) - {self.puzzle[i][j] for i, j in cells}
        
        class SolutionFound(Exception):
            pass

        calls = 0
        histogram = {}

        def recursive_solve(depth = 0):
            nonlocal calls
            calls += 1
            histogram[depth] = 1 + histogram.get(depth, 0) 
            
            candidates = [(len(unused(i, j)), i , j)
                          for i in range(9)
                          for j in range(9)
                          if self.puzzle[i][j] == 0]

            if not candidates:
                raise SolutionFound

            _, i, j = sorted(candidates)[0]
            values = unused(i, j)
            for value in values:  # :WARNING: sorted(values) will increase the search space significantly!
                self.puzzle[i][j] = value

                # trace progress of state space search in Windows terminal
                #os.system('cls') 
                #self.print()
                #print(calls)

                recursive_solve(depth + 1)
            self.puzzle[i][j] = 0

        try:
            recursive_solve()
        except SolutionFound: 
            print("Found solution after %s calls" % calls)
            print("Recursion depth", histogram)

A = Sudoku([[5,1,7,6,0,0,0,3,4],
            [2,8,9,0,0,4,0,0,0],
            [3,4,6,2,0,5,0,9,0],
            [6,0,2,0,0,0,0,1,0],
            [0,3,8,0,0,6,0,4,7],
            [0,0,0,0,0,0,0,0,0],
            [0,9,0,0,0,0,0,7,8],
            [7,0,3,4,0,0,5,6,0],
            [0,0,0,0,0,0,0,0,0]])

B = Sudoku([[0,0,0,0,0,6,0,0,0],
            [0,5,9,0,0,0,0,0,8],
            [2,0,0,0,0,8,0,0,0],
            [0,4,5,0,0,0,0,0,0],
            [0,0,3,0,0,0,0,0,0],
            [0,0,6,0,0,3,0,5,4],
            [0,0,0,3,2,5,0,0,6],
            [0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0]])

C = Sudoku([[5, 0, 3, 0, 0, 2, 7, 0, 0],
            [0, 1, 0, 0, 0, 8, 2, 0, 0],
            [0, 7, 0, 6, 0, 1, 0, 0, 9],
            [0, 0, 4, 0, 0, 0, 0, 0, 8],
            [0, 0, 0, 1, 0, 5, 0, 0, 0],
            [2, 0, 0, 0, 0, 0, 3, 0, 0],
            [8, 0, 0, 3, 0, 6, 0, 9, 0],
            [0, 0, 9, 5, 0, 0, 0, 3, 0],
            [0, 0, 1, 9, 0, 0, 6, 0, 2]])

D = Sudoku([[0] * 9 for _ in range(9)])

for S in [A, B, C, D]:
    S.print()
    S.solve()
    S.print()
    print()