from numpy import * 
def isValid(grid):
    count = 0
    for x in range(0,9):
        for y in range(0,9):
            if grid[x][y] == 0:
                # tell it to skip rest of code in function and keep going through for loop
            a, b = x, y
            x = 0
            for i in range(0,9):
                if grid[a][b] == grid[x+i][b]:
                    count += 1
            if count != 1:
                return 2
            count = 0
    return 1
def isDone(grid):
    total = 0
    for r in range(0,9):
        for c in range(0,9):
            total += grid[r][c]
        if total != 45:
            return 2
        total = 0
    for c in range(0,9):
        for r in range(0,9):
            total += grid[r][c]
        if total != 45:
            return 2
        total = 0
    x, y = 1, 1
    for a in range(0,9):
        if y == 10:
            y = 1
            x += 3
        total += grid[x][y]+grid[x-1][y-1]+grid[x-1][y]+grid[x-1][y+1]+grid[x][y-1]+grid[x][y+1]+grid[x+1][y-1]+grid[x+1][y]+grid[x+1][y+1]
        if total != 45:
            return 2
        y += 3
        total = 0
    return 1
def solve(grid):
    if isValid(grid) == 2:
        return 2
    if isDone(grid) == 1:
        return 1
    for i in range(0,9):
        for j in range(0,9):
            if grid[i][j] == 0:
                for g in range(1,10):
                    grid[i][j] = g
                    if solve(grid) == 1:
                        return 1
                grid[i][j] = 0
                return 2
def display(g):
    for i in range(0,9):
        print str(g[i][0])+" "+str(g[i][1])+" "+str(g[i][2])+" "+str(g[i][3])+" "+str(g[i][4])+" "+str(g[i][5])+ " "+str(g[i][6])+" "+str(g[i][7])+" "+str(g[i][8])
grid = arange(81).reshape(9,9)
print "Time to input the grid!  Input 0 for blank space." 
# ENTER YOUR SUDOKU PUZZLE GRID HERE: #
# USE ZEROES FOR BLANK SPACES #
# A SAMPLE PUZZLE IS GIVEN: #
grid = [ [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,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] ]
#######################################
print "Here is what the Sudoku grid looks like: "
display(grid)
if isValid(grid) == 1:
    solve(grid)
    print "Here is the solved Sudoku Puzzle!: "
    print "----------------------------------"
    display(grid)
else:
    print "not valid"

def isValid(grid):
    count = 0
    for x in range(0,9):
        for y in range(0,9):
            if grid[x][y] != 0:
                print "infty"
                for i in range(0,9):
                    if grid[x][y] == grid[i][y]:
                        count += 1
                if count != 1:
                    return 2
                count = 0
        return 1