import numpy as np
import time

#grid = [
#        [0,0,0,0,0,0,0,0,0],
#        [0,0,0,0,0,0,0,0,0],
#        [0,0,0,0,0,0,0,0,0],
#        [0,0,0,0,0,0,0,0,0],
#        [0,0,0,0,0,0,0,0,0],
#        [0,0,0,0,0,0,0,0,0],
#        [0,0,0,0,0,0,0,0,0],
#        [0,0,0,0,0,0,0,0,0],
#        [0,0,0,0,0,0,0,0,0]
#       ]
grid =  [
        [3,0,6,8,4,0,0,5,0],
        [0,5,1,0,0,0,0,0,7],
        [8,0,0,0,0,9,0,0,0],
        [0,0,0,0,8,0,0,3,9],
        [0,0,0,0,5,6,0,0,0],
        [0,0,0,7,0,0,0,0,0],
        [0,0,8,0,0,0,0,6,0],
        [0,0,2,0,0,0,5,0,1],
        [4,6,0,0,0,0,0,7,0]
        ]
print (np.matrix(grid))
level = 0
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
    global level
# loop through rows
    for y in range(0,9):
# loop through columns
        for x in range(0,9):
# check for blank space
            if grid[y][x] == 0:
# Loop through 1-9            
                for n in range(1,10):
# check if this number is allowed in this empty space & store the number
                    if possible(y,x,n):
                        grid[y][x] = n
                        if (x==0 and y ==0):
                            print(n)
# recursive call to this function
                        level=level+1
                        print("level-",level)
                        solve()
# if return from the function (no available spaces for this number) clear the space & check the next number
                        grid[y][x] = 0
                        level=level-1
                        print("level-",level)
# if all numbers have been checked return from the function - back to the previous recursion & set the available space to 0 (timey wimey).
                return
#        print (np.matrix(grid))
#        input ("NEXT")
#        time.sleep(5)
    print (np.matrix(grid))
    input("NEXT")
    
solve()