fork(1) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/W9Kj9E
language:
Python (cpython 2.7.16)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!