Program to solve a Sudoku using simple backtracking

Sudoku Backtracking

import sys
import curses


def sudoku(grid):
    global times
    global row_cache
    global col_cache
    times = 0

    row_cache = [False] * 9
    col_cache = [False] * 9
    sqr_cache = [False] * 9

    for row in xrange(len(grid)):
        row_cache[row] = [False] * 10
        col_cache[row] = [False] * 10
        sqr_cache[row] = [False] * 10

    for row in xrange(len(grid)):
        for col in xrange(len(grid)):
            if grid[row][col] > 0:
                row_cache[row][grid[row][col]] = True
                col_cache[col][grid[row][col]] = True

                sqr_number = col // 3 * 3 + row // 3
                sqr_cache[sqr_number][grid[row][col]] = True

    def is_complete(s):
        complete = True

        for row in xrange(len(s)):
            complete = complete and s[row].count(0) == 0

        return complete

    def is_valid(s):

        valid = True

        for row in xrange(len(s)):
            for n in xrange(1, 10):
                valid = valid and s[row].count(n) == 1

        for col in xrange(len(s)):
            c = [0] * 9
            for row in xrange(len(s)):
                c[row] = s[row][col]
            for n in xrange(1, 10):
                valid = valid and c.count(n) == 1

        for i in [0, 3, 6]:
            square = []
            for x in xrange(i, i + 3):
                for y in xrange(i, i + 3):
                    square.append(s[x][y])
            for n in xrange(1, 10):
                valid = valid and square.count(n) == 1

        return valid

    def is_promising(n, x, y):
        sqr_number = y // 3 * 3 + x // 3
        if row_cache[x][n] or col_cache[y][n] or sqr_cache[sqr_number][n]:
            return False
        return True

    def solve(s, x, y):
        if is_complete(s):
            inc_time(s)
            if is_valid(s):
                return s
            else:
                return None
        else:
            if s[x][y] == 0:
                for n in xrange(1, 10):
                    if is_promising(n, x, y):
                        s[x][y] = n
                        row_cache[x][n] = True
                        col_cache[y][n] = True
                        sqr_number = y // 3 * 3 + x // 3
                        sqr_cache[sqr_number][n] = True
                        solution = solve(s, x, y)
                        if solution is not None:
                            return solution
                        row_cache[x][n] = False
                        col_cache[y][n] = False
                        sqr_cache[sqr_number][n] = False
                    else:
                        inc_time(s)
                s[x][y] = 0
                print_grid(s)
                return None
            else:
                x += 1
                if x >= len(s):
                    x = 0
                    y += 1
                if y >= len(s):
                    return None
                return solve(s, x, y)

    def inc_time(s):
        global times
        times += 1
        print_grid(s, "{0} combinations tried".format(times))

    def print_grid(grid, subtitle=""):

        def print_line(x, i):
            line = ""
            for y in xrange(len(grid)):
                if y % 3 == 0:
                    line += "| "
                if grid[x][y] == 0:
                    line += "  "
                else:
                    line += str(grid[x][y]) + " "
            line += "|"
            stdscr.addstr(i, 0, line)

        if grid is not None:
            stdscr.addstr(0, 0, "-------------------------")
            print_line(0, 1)
            print_line(1, 2)
            print_line(2, 3)
            stdscr.addstr(4, 0, "-------------------------")
            print_line(3, 5)
            print_line(4, 6)
            print_line(5, 7)
            stdscr.addstr(8, 0, "-------------------------")
            print_line(6, 9)
            print_line(7, 10)
            print_line(8, 11)
            stdscr.addstr(12, 0, "-------------------------")
            stdscr.addstr(13, 0, subtitle)
            stdscr.refresh()
        else:
            stdscr.addstr(13, 0, "There's no solution!     ")
            stdscr.refresh()

    print_grid(solve(grid, 0, 0), "Found after {0} combinations".format(times))


if __name__ == "__main__":
    stdscr = curses.initscr()
    curses.noecho()
    curses.cbreak()

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

    sudoku(grid)

    curses.echo()
    curses.nocbreak()
    curses.endwin()