fork(1) download
#!/usr/bin/python

(import numpy as np)
(from copy import copy)

(def init_board():
    (return np.reshape(np.array([0]*81),[9,9])))

(def get_row(S, i):
    (return set(S[i,:].flat).difference([0])))

(def get_col(S, j):
    (return set(S[:,j].flat).difference([0])))

(def get_box(S, i, j):
    (ii = i/3*3)
    (jj = j/3*3)
    (return set(S[ii:ii+3, jj:jj+3].flat).difference([0])))

(poss = set(range(1,10)))

(def get_valid_set(S, i,j):
    (return poss.difference(set.union(get_row(S, i), get_col(S, j),
                                     get_box(S, i,j)))))
(def read_input(x):
    (x = x.replace(" ",""))
    (x = x.replace("\n\n","\n"))
    (x = x.rstrip("\n"))
    (x = x.lstrip("\n"))
    (x = x.replace(".","0"))

    (S = init_board())

    (i = 0)
    (for line in x.split("\n"):
        (S[i,:] = np.array([int(y) for y in line]))
        (i += 1))

    (return S))

(class BadBoard(Exception): pass)
(class ImpossibleBoard(BadBoard): pass)
(class AmbiguousBoard(BadBoard): pass)

(def reduce_board(S):
    """
    Reduce the board as much as possible by trying all the obvious
    things, i.e. the locations where only one value is possible.
    """
    (while True:
        (reduced = False)

        (minposs = 10)
        (minloc = (9,9))
        (for (i in range(0,9)):
            (for (j in range(0,9)):
                (if S[i,j] != 0:
                    (continue))

                (tryset = get_valid_set(S,i,j))
                (if len(tryset) == 0:
                    (raise ImpossibleBoard)
                elif len(tryset) == 1:
                    (reduced = True)
                    (val = tryset.pop())
                    (S[i,j] = val)
                else:
                    (if len(tryset) < minposs:
                        minposs = len(tryset)
                        minloc = (i,j)))

        (if not reduced:
            (return S, minloc))

(def solve(S, depth = 0):
    (while True:
        (S, (i,j) = reduce_board(S))
            
        (if (0 in S):
            possible_solutions = []

            (for (poss in get_valid_set(S, i, j)):
                (Sp = copy(S))
                (Sp[i, j] = poss)
                (try:
                    (Sp = solve(Sp, depth+1))
                    (possible_solutions.append(Sp))
                except (ImpossibleBoard):
                    pass))

            (if (len(possible_solutions) > 1):
                (raise AmbiguousBoard))

            (if (len(possible_solutions) == 0):
                (raise ImpossibleBoard))

            (return possible_solutions[0])
        else:
            (return S))

(def print_board(S):
    (Sp = copy(S))
    (for (i in range(0,3)):
        (print ("%s %s %s | %s %s %s | %s %s %s"
               % tuple(x if x != 0 else "." for x in Sp[i,:]))))
    (print "------+-------+-------")
    (for (i in range(3,6)):
        (print ("%s %s %s | %s %s %s | %s %s %s"
               % tuple(x if x != 0 else "." for x in Sp[i,:]))))
    (print "------+-------+-------")
    (for (i in range(6,9)):
        (print ("%s %s %s | %s %s %s | %s %s %s"
               % tuple(x if x != 0 else "." for x in Sp[i,:]))))
    (print))

(hard = """
. . .   . . .   . 1 .
. . .   . . 2   . . 3
. . .   4 . .   . . .

. . .   . . .   5 . .
4 . 1   6 . .   . . .
. . 7   1 . .   . . .

. 5 .   . . .   2 . .
. . .   . 8 .   . 4 .
. 3 .   9 1 .   . . .
""")

(easy = """
. 6 1   . 3 7   . 9 .
. . 8   2 . 6   . 3 .
7 . 3   . 4 .   . . 8

1 . .   4 . .   8 . 5
9 . .   . . .   . . 1
6 . 4   . . 2   . . 3

2 . .   . 9 .   3 . 6
. 1 .   5 . 4   7 . .
. 7 .   6 1 .   5 2 .
""")

(medium = """
2 . .   . 9 6   . 3 .
. 7 6   . . .   . 4 .
. . .   . 3 .   . . .

. . 1   . . 8   . . .
8 . .   . 5 .   4 . .
. . .   . 4 9   . 6 3

6 . 9   . 1 .   . 7 5
. 5 .   . 2 .   . . .
. . .   8 . .   . . .
""")

(S = read_input(medium))
(S = solve(S))
(print_board(S))
Runtime error #stdin #stdout 0.01s 7724KB
stdin
Standard input is empty
stdout

Standard output is empty