#!/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))
CiMhL3Vzci9iaW4vcHl0aG9uCgooaW1wb3J0IG51bXB5IGFzIG5wKQooZnJvbSBjb3B5IGltcG9ydCBjb3B5KQoKKGRlZiBpbml0X2JvYXJkKCk6CiAgICAocmV0dXJuIG5wLnJlc2hhcGUobnAuYXJyYXkoWzBdKjgxKSxbOSw5XSkpKQoKKGRlZiBnZXRfcm93KFMsIGkpOgogICAgKHJldHVybiBzZXQoU1tpLDpdLmZsYXQpLmRpZmZlcmVuY2UoWzBdKSkpCgooZGVmIGdldF9jb2woUywgaik6CiAgICAocmV0dXJuIHNldChTWzosal0uZmxhdCkuZGlmZmVyZW5jZShbMF0pKSkKCihkZWYgZ2V0X2JveChTLCBpLCBqKToKICAgIChpaSA9IGkvMyozKQogICAgKGpqID0gai8zKjMpCiAgICAocmV0dXJuIHNldChTW2lpOmlpKzMsIGpqOmpqKzNdLmZsYXQpLmRpZmZlcmVuY2UoWzBdKSkpCgoocG9zcyA9IHNldChyYW5nZSgxLDEwKSkpCgooZGVmIGdldF92YWxpZF9zZXQoUywgaSxqKToKICAgIChyZXR1cm4gcG9zcy5kaWZmZXJlbmNlKHNldC51bmlvbihnZXRfcm93KFMsIGkpLCBnZXRfY29sKFMsIGopLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZ2V0X2JveChTLCBpLGopKSkpKQooZGVmIHJlYWRfaW5wdXQoeCk6CiAgICAoeCA9IHgucmVwbGFjZSgiICIsIiIpKQogICAgKHggPSB4LnJlcGxhY2UoIlxuXG4iLCJcbiIpKQogICAgKHggPSB4LnJzdHJpcCgiXG4iKSkKICAgICh4ID0geC5sc3RyaXAoIlxuIikpCiAgICAoeCA9IHgucmVwbGFjZSgiLiIsIjAiKSkKCiAgICAoUyA9IGluaXRfYm9hcmQoKSkKCiAgICAoaSA9IDApCiAgICAoZm9yIGxpbmUgaW4geC5zcGxpdCgiXG4iKToKICAgICAgICAoU1tpLDpdID0gbnAuYXJyYXkoW2ludCh5KSBmb3IgeSBpbiBsaW5lXSkpCiAgICAgICAgKGkgKz0gMSkpCgogICAgKHJldHVybiBTKSkKCihjbGFzcyBCYWRCb2FyZChFeGNlcHRpb24pOiBwYXNzKQooY2xhc3MgSW1wb3NzaWJsZUJvYXJkKEJhZEJvYXJkKTogcGFzcykKKGNsYXNzIEFtYmlndW91c0JvYXJkKEJhZEJvYXJkKTogcGFzcykKCihkZWYgcmVkdWNlX2JvYXJkKFMpOgogICAgIiIiCiAgICBSZWR1Y2UgdGhlIGJvYXJkIGFzIG11Y2ggYXMgcG9zc2libGUgYnkgdHJ5aW5nIGFsbCB0aGUgb2J2aW91cwogICAgdGhpbmdzLCBpLmUuIHRoZSBsb2NhdGlvbnMgd2hlcmUgb25seSBvbmUgdmFsdWUgaXMgcG9zc2libGUuCiAgICAiIiIKICAgICh3aGlsZSBUcnVlOgogICAgICAgIChyZWR1Y2VkID0gRmFsc2UpCgogICAgICAgIChtaW5wb3NzID0gMTApCiAgICAgICAgKG1pbmxvYyA9ICg5LDkpKQogICAgICAgIChmb3IgKGkgaW4gcmFuZ2UoMCw5KSk6CiAgICAgICAgICAgIChmb3IgKGogaW4gcmFuZ2UoMCw5KSk6CiAgICAgICAgICAgICAgICAoaWYgU1tpLGpdICE9IDA6CiAgICAgICAgICAgICAgICAgICAgKGNvbnRpbnVlKSkKCiAgICAgICAgICAgICAgICAodHJ5c2V0ID0gZ2V0X3ZhbGlkX3NldChTLGksaikpCiAgICAgICAgICAgICAgICAoaWYgbGVuKHRyeXNldCkgPT0gMDoKICAgICAgICAgICAgICAgICAgICAocmFpc2UgSW1wb3NzaWJsZUJvYXJkKQogICAgICAgICAgICAgICAgZWxpZiBsZW4odHJ5c2V0KSA9PSAxOgogICAgICAgICAgICAgICAgICAgIChyZWR1Y2VkID0gVHJ1ZSkKICAgICAgICAgICAgICAgICAgICAodmFsID0gdHJ5c2V0LnBvcCgpKQogICAgICAgICAgICAgICAgICAgIChTW2ksal0gPSB2YWwpCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIChpZiBsZW4odHJ5c2V0KSA8IG1pbnBvc3M6CiAgICAgICAgICAgICAgICAgICAgICAgIG1pbnBvc3MgPSBsZW4odHJ5c2V0KQogICAgICAgICAgICAgICAgICAgICAgICBtaW5sb2MgPSAoaSxqKSkpCgogICAgICAgIChpZiBub3QgcmVkdWNlZDoKICAgICAgICAgICAgKHJldHVybiBTLCBtaW5sb2MpKQoKKGRlZiBzb2x2ZShTLCBkZXB0aCA9IDApOgogICAgKHdoaWxlIFRydWU6CiAgICAgICAgKFMsIChpLGopID0gcmVkdWNlX2JvYXJkKFMpKQogICAgICAgICAgICAKICAgICAgICAoaWYgKDAgaW4gUyk6CiAgICAgICAgICAgIHBvc3NpYmxlX3NvbHV0aW9ucyA9IFtdCgogICAgICAgICAgICAoZm9yIChwb3NzIGluIGdldF92YWxpZF9zZXQoUywgaSwgaikpOgogICAgICAgICAgICAgICAgKFNwID0gY29weShTKSkKICAgICAgICAgICAgICAgIChTcFtpLCBqXSA9IHBvc3MpCiAgICAgICAgICAgICAgICAodHJ5OgogICAgICAgICAgICAgICAgICAgIChTcCA9IHNvbHZlKFNwLCBkZXB0aCsxKSkKICAgICAgICAgICAgICAgICAgICAocG9zc2libGVfc29sdXRpb25zLmFwcGVuZChTcCkpCiAgICAgICAgICAgICAgICBleGNlcHQgKEltcG9zc2libGVCb2FyZCk6CiAgICAgICAgICAgICAgICAgICAgcGFzcykpCgogICAgICAgICAgICAoaWYgKGxlbihwb3NzaWJsZV9zb2x1dGlvbnMpID4gMSk6CiAgICAgICAgICAgICAgICAocmFpc2UgQW1iaWd1b3VzQm9hcmQpKQoKICAgICAgICAgICAgKGlmIChsZW4ocG9zc2libGVfc29sdXRpb25zKSA9PSAwKToKICAgICAgICAgICAgICAgIChyYWlzZSBJbXBvc3NpYmxlQm9hcmQpKQoKICAgICAgICAgICAgKHJldHVybiBwb3NzaWJsZV9zb2x1dGlvbnNbMF0pCiAgICAgICAgZWxzZToKICAgICAgICAgICAgKHJldHVybiBTKSkKCihkZWYgcHJpbnRfYm9hcmQoUyk6CiAgICAoU3AgPSBjb3B5KFMpKQogICAgKGZvciAoaSBpbiByYW5nZSgwLDMpKToKICAgICAgICAocHJpbnQgKCIlcyAlcyAlcyB8ICVzICVzICVzIHwgJXMgJXMgJXMiCiAgICAgICAgICAgICAgICUgdHVwbGUoeCBpZiB4ICE9IDAgZWxzZSAiLiIgZm9yIHggaW4gU3BbaSw6XSkpKSkKICAgIChwcmludCAiLS0tLS0tKy0tLS0tLS0rLS0tLS0tLSIpCiAgICAoZm9yIChpIGluIHJhbmdlKDMsNikpOgogICAgICAgIChwcmludCAoIiVzICVzICVzIHwgJXMgJXMgJXMgfCAlcyAlcyAlcyIKICAgICAgICAgICAgICAgJSB0dXBsZSh4IGlmIHggIT0gMCBlbHNlICIuIiBmb3IgeCBpbiBTcFtpLDpdKSkpKQogICAgKHByaW50ICItLS0tLS0rLS0tLS0tLSstLS0tLS0tIikKICAgIChmb3IgKGkgaW4gcmFuZ2UoNiw5KSk6CiAgICAgICAgKHByaW50ICgiJXMgJXMgJXMgfCAlcyAlcyAlcyB8ICVzICVzICVzIgogICAgICAgICAgICAgICAlIHR1cGxlKHggaWYgeCAhPSAwIGVsc2UgIi4iIGZvciB4IGluIFNwW2ksOl0pKSkpCiAgICAocHJpbnQpKQoKKGhhcmQgPSAiIiIKLiAuIC4gICAuIC4gLiAgIC4gMSAuCi4gLiAuICAgLiAuIDIgICAuIC4gMwouIC4gLiAgIDQgLiAuICAgLiAuIC4KCi4gLiAuICAgLiAuIC4gICA1IC4gLgo0IC4gMSAgIDYgLiAuICAgLiAuIC4KLiAuIDcgICAxIC4gLiAgIC4gLiAuCgouIDUgLiAgIC4gLiAuICAgMiAuIC4KLiAuIC4gICAuIDggLiAgIC4gNCAuCi4gMyAuICAgOSAxIC4gICAuIC4gLgoiIiIpCgooZWFzeSA9ICIiIgouIDYgMSAgIC4gMyA3ICAgLiA5IC4KLiAuIDggICAyIC4gNiAgIC4gMyAuCjcgLiAzICAgLiA0IC4gICAuIC4gOAoKMSAuIC4gICA0IC4gLiAgIDggLiA1CjkgLiAuICAgLiAuIC4gICAuIC4gMQo2IC4gNCAgIC4gLiAyICAgLiAuIDMKCjIgLiAuICAgLiA5IC4gICAzIC4gNgouIDEgLiAgIDUgLiA0ICAgNyAuIC4KLiA3IC4gICA2IDEgLiAgIDUgMiAuCiIiIikKCihtZWRpdW0gPSAiIiIKMiAuIC4gICAuIDkgNiAgIC4gMyAuCi4gNyA2ICAgLiAuIC4gICAuIDQgLgouIC4gLiAgIC4gMyAuICAgLiAuIC4KCi4gLiAxICAgLiAuIDggICAuIC4gLgo4IC4gLiAgIC4gNSAuICAgNCAuIC4KLiAuIC4gICAuIDQgOSAgIC4gNiAzCgo2IC4gOSAgIC4gMSAuICAgLiA3IDUKLiA1IC4gICAuIDIgLiAgIC4gLiAuCi4gLiAuICAgOCAuIC4gICAuIC4gLgoiIiIpCgooUyA9IHJlYWRfaW5wdXQobWVkaXVtKSkKKFMgPSBzb2x2ZShTKSkKKHByaW50X2JvYXJkKFMpKQo=