sudoku solver solve incomplete valid sudoku matrix using recursive backtrack ,little clever(find valid numbers group once instead validating each [1-9] number) as it could solve hard sudoku puzzle without getting timeout on udacity's sever .(created for u

sudoku_solver.py

# CHALLENGE PROBLEM: 
#
# Use your check_sudoku function as the basis for solve_sudoku(): a
# function that takes a partially-completed Sudoku grid and replaces
# each 0 cell with a number in the range 1..9 in such a way that the
# final grid is valid.
#
# There are many ways to cleverly solve a partially-completed Sudoku
# puzzle, but a brute-force recursive solution with backtracking is a
# perfectly good option. The solver should return None for broken
# input, False for inputs that have no valid solutions, and a valid
# 9x9 Sudoku grid containing no 0 elements otherwise. In general, a
# partially-completed Sudoku grid does not have a unique solution. You
# should just return some member of the set of solutions.
#
# A solve_sudoku() in this style can be implemented in about 16 lines
# without making any particular effort to write concise code.

# solve_sudoku should return None
ill_formed = [[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],  # <---
              [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]]

# solve_sudoku should return valid unchanged
valid = [[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,0,0,0,0],
         [9,6,1,5,3,0,0,0,0],
         [2,8,7,4,1,0,0,0,0],
         [3,4,5,2,8,0,0,0,0]]

# solve_sudoku should return False
invalid = [[5,3,4,6,7,8,9,1,2],
           [6,7,2,1,9,5,3,4,8],
           [1,9,8,3,8,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]]

# solve_sudoku should return a 
# sudoku grid which passes a 
# sudoku checker. There may be
# multiple correct grids which 
# can be made from this starting 
# grid.
easy = [[2,9,0,0,0,0,0,7,0],
        [3,0,6,0,0,8,4,0,0],
        [8,0,0,0,4,0,0,0,2],
        [0,2,0,0,3,1,0,0,7],
        [0,0,0,0,8,0,0,0,0],
        [1,0,0,9,5,0,0,6,0],
        [7,0,0,0,9,0,0,0,1],
        [0,0,1,2,0,0,3,0,6],
        [0,3,0,0,0,0,0,5,9]]

# Note: this may timeout 
# in the Udacity IDE! Try running 
# it locally if you'd like to test 
# your solution with it.
# 
hard = [[1,0,0,0,0,7,0,9,0],
         [0,3,0,0,2,0,0,0,8],
         [0,0,9,6,0,0,5,0,0],
         [0,0,5,3,0,0,9,0,0],
         [0,1,0,0,8,0,0,0,2],
         [6,0,0,0,0,4,0,0,0],
         [3,0,0,0,0,0,0,1,0],
         [0,4,0,0,0,0,0,0,7],
         [0,0,7,0,0,0,3,0,0]]
#dec represents list of 10 elements of type boolean,
#which represents set i.e if dec[3] is True then, set contains 3. 
def solve_sudoku (grid):
    c = check_sudoku(grid)
    if c:
        solved = solve_sudoku_recursive_backtrack(grid)
	if solved <> False: draw_grid(solved)
        #print solved
        return solved
    return c
def solve_sudoku_recursive_backtrack(grid):
    for i,row in enumerate(grid):
        for j,d in enumerate(row):
            if d == 0:
                ld = leftdec(i, j, grid)
                pd = [d for d,e in enumerate(ld[1:],start = 1) if e == False]
                for d in pd:
                    grid[i][j] = d
                    ngrid = solve_sudoku_recursive_backtrack(grid)
                    if ngrid:
                        return ngrid
                #draw_grid(grid)
                grid[i][j] = 0
                return False
    return grid
#leftdec returns dec which is valid
def leftdec(i, j, grid):
    icol = grid[i]
    jcol = [grid[p][j] for p in xrange(9)]
    si, sj  = 3*int(i/3), 3*int(j/3)
    sgrid = [grid[m][n] for m in xrange(si, si+3) for n in range(sj, sj+3)]
    dec = [False]*10
    dec = dec_line(icol, dec)
    dec = dec_line(jcol, dec)
    dec = dec_line(sgrid, dec)
    return dec
# returns valid dec after setting to dec[each line_element] to True
def dec_line(line, dec):
    #dec = [False]*10
    for d in line:
        #if d <> 0 and dec[d] == True:
            #return False
        dec[d] = True
    return dec
def draw_grid(grid):
    for e in grid:
        print e
    print "next"
def check_sudoku(grid):
    try:
        if len(grid) <> 9:
            return None
    except TypeError:
        return None
    for row in grid:
        try:
            if len(row) <> 9:
                return None
        except TypeError: return None
        for d in row:
            if d not in range(0,10):
                return None
        t = check_line(row)
    #rule check
    if not t: return False
    for row in transpose(grid):
        if not check_line(row):
            return False
    #i,j = 0,0
    for i in range(0,9,3):
        for j in range(0,9,3):
            line = [grid[p][q]  for p in xrange(i,i+3) for q in xrange(j,j+3)]
            if not check_line(line):
                return False
    return True
def check_line(line):
    dec = [False]*10
    for d in line:
        d = int(d)
        if d <> 0 and dec[d] == True:
            return False
        dec[d] = True
    return True
def transpose(matrix):
    "Transpose e.g. [[1,2,3], [4,5,6]] to [[1, 4], [2, 5], [3, 6]]"
    # or [[M[j][i] for j in range(len(M))] for i in range(len(M[0]))]
    return map(list, zip(*matrix))
solve_sudoku(hard)