fork(1) download
  1.  
  2. #!/usr/bin/python
  3.  
  4. (import numpy as np)
  5. (from copy import copy)
  6.  
  7. (def init_board():
  8. (return np.reshape(np.array([0]*81),[9,9])))
  9.  
  10. (def get_row(S, i):
  11. (return set(S[i,:].flat).difference([0])))
  12.  
  13. (def get_col(S, j):
  14. (return set(S[:,j].flat).difference([0])))
  15.  
  16. (def get_box(S, i, j):
  17. (ii = i/3*3)
  18. (jj = j/3*3)
  19. (return set(S[ii:ii+3, jj:jj+3].flat).difference([0])))
  20.  
  21. (poss = set(range(1,10)))
  22.  
  23. (def get_valid_set(S, i,j):
  24. (return poss.difference(set.union(get_row(S, i), get_col(S, j),
  25. get_box(S, i,j)))))
  26. (def read_input(x):
  27. (x = x.replace(" ",""))
  28. (x = x.replace("\n\n","\n"))
  29. (x = x.rstrip("\n"))
  30. (x = x.lstrip("\n"))
  31. (x = x.replace(".","0"))
  32.  
  33. (S = init_board())
  34.  
  35. (i = 0)
  36. (for line in x.split("\n"):
  37. (S[i,:] = np.array([int(y) for y in line]))
  38. (i += 1))
  39.  
  40. (return S))
  41.  
  42. (class BadBoard(Exception): pass)
  43. (class ImpossibleBoard(BadBoard): pass)
  44. (class AmbiguousBoard(BadBoard): pass)
  45.  
  46. (def reduce_board(S):
  47. """
  48. Reduce the board as much as possible by trying all the obvious
  49. things, i.e. the locations where only one value is possible.
  50. """
  51. (while True:
  52. (reduced = False)
  53.  
  54. (minposs = 10)
  55. (minloc = (9,9))
  56. (for (i in range(0,9)):
  57. (for (j in range(0,9)):
  58. (if S[i,j] != 0:
  59. (continue))
  60.  
  61. (tryset = get_valid_set(S,i,j))
  62. (if len(tryset) == 0:
  63. (raise ImpossibleBoard)
  64. elif len(tryset) == 1:
  65. (reduced = True)
  66. (val = tryset.pop())
  67. (S[i,j] = val)
  68. else:
  69. (if len(tryset) < minposs:
  70. minposs = len(tryset)
  71. minloc = (i,j)))
  72.  
  73. (if not reduced:
  74. (return S, minloc))
  75.  
  76. (def solve(S, depth = 0):
  77. (while True:
  78. (S, (i,j) = reduce_board(S))
  79.  
  80. (if (0 in S):
  81. possible_solutions = []
  82.  
  83. (for (poss in get_valid_set(S, i, j)):
  84. (Sp = copy(S))
  85. (Sp[i, j] = poss)
  86. (try:
  87. (Sp = solve(Sp, depth+1))
  88. (possible_solutions.append(Sp))
  89. except (ImpossibleBoard):
  90. pass))
  91.  
  92. (if (len(possible_solutions) > 1):
  93. (raise AmbiguousBoard))
  94.  
  95. (if (len(possible_solutions) == 0):
  96. (raise ImpossibleBoard))
  97.  
  98. (return possible_solutions[0])
  99. else:
  100. (return S))
  101.  
  102. (def print_board(S):
  103. (Sp = copy(S))
  104. (for (i in range(0,3)):
  105. (print ("%s %s %s | %s %s %s | %s %s %s"
  106. % tuple(x if x != 0 else "." for x in Sp[i,:]))))
  107. (print "------+-------+-------")
  108. (for (i in range(3,6)):
  109. (print ("%s %s %s | %s %s %s | %s %s %s"
  110. % tuple(x if x != 0 else "." for x in Sp[i,:]))))
  111. (print "------+-------+-------")
  112. (for (i in range(6,9)):
  113. (print ("%s %s %s | %s %s %s | %s %s %s"
  114. % tuple(x if x != 0 else "." for x in Sp[i,:]))))
  115. (print))
  116.  
  117. (hard = """
  118. . . . . . . . 1 .
  119. . . . . . 2 . . 3
  120. . . . 4 . . . . .
  121.  
  122. . . . . . . 5 . .
  123. 4 . 1 6 . . . . .
  124. . . 7 1 . . . . .
  125.  
  126. . 5 . . . . 2 . .
  127. . . . . 8 . . 4 .
  128. . 3 . 9 1 . . . .
  129. """)
  130.  
  131. (easy = """
  132. . 6 1 . 3 7 . 9 .
  133. . . 8 2 . 6 . 3 .
  134. 7 . 3 . 4 . . . 8
  135.  
  136. 1 . . 4 . . 8 . 5
  137. 9 . . . . . . . 1
  138. 6 . 4 . . 2 . . 3
  139.  
  140. 2 . . . 9 . 3 . 6
  141. . 1 . 5 . 4 7 . .
  142. . 7 . 6 1 . 5 2 .
  143. """)
  144.  
  145. (medium = """
  146. 2 . . . 9 6 . 3 .
  147. . 7 6 . . . . 4 .
  148. . . . . 3 . . . .
  149.  
  150. . . 1 . . 8 . . .
  151. 8 . . . 5 . 4 . .
  152. . . . . 4 9 . 6 3
  153.  
  154. 6 . 9 . 1 . . 7 5
  155. . 5 . . 2 . . . .
  156. . . . 8 . . . . .
  157. """)
  158.  
  159. (S = read_input(medium))
  160. (S = solve(S))
  161. (print_board(S))
  162.  
Runtime error #stdin #stdout 0.01s 7724KB
stdin
Standard input is empty
stdout

Standard output is empty