fork download
copy 
  1. PROBREM = '''\
  2. 530070000
  3. 600195000
  4. 098000060
  5. 800060003
  6. 400803001
  7. 700020006
  8. 060000280
  9. 000419005
  10. 000080079
  11. '''
  12.  
  13.  
  14. def main():
  15.     cells, flags = load(PROBREM)
  16.     try:
  17.         i = initialize(flags)
  18.         while True:
  19.             if increment(cells, i):
  20.                 if validate(cells, i):
  21.                     i = find_next(flags, i)
  22.             else:
  23.                 i = back_track(flags, i)
  24.     except Exception:
  25.         print_cells(cells)
  26.  
  27.  
  28. def load(probrem):
  29.     cells = []
  30.     for line in probrem:
  31.         cells.extend([int(n) for n in line.strip()])
  32.     return cells, [bool(n) for n in cells]
  33.  
  34.  
  35. def initialize(flags):
  36.     return find_next(flags, -1)
  37.  
  38.  
  39. def increment(cells, i):
  40.     if cells[i] == 9:
  41.         cells[i] = 0
  42.         return False
  43.     else:
  44.         cells[i] += 1
  45.         return True
  46.  
  47.  
  48. def validate(cells, i):
  49.     x = i % 9
  50.     y = i // 9
  51.     return (validate_impl(cells, column(x)) and
  52.             validate_impl(cells, row(y)) and
  53.             validate_impl(cells, block(x, y)))
  54.  
  55.  
  56. def column(x):
  57.     return (x + n * 9 for n in range(9))
  58.  
  59.  
  60. def row(y):
  61.     return (n + y * 9 for n in range(9))
  62.  
  63.  
  64. def block(x, y):
  65.     _x = x // 3 * 3
  66.     _y = y // 3 * 3
  67.     for X in range(_x, _x + 3):
  68.         for Y in range(_y, _y + 3):
  69.             yield X + Y * 9
  70.  
  71.  
  72. def validate_impl(cells, indices):
  73.     indices = list(indices)
  74.     s = set()
  75.     for i in indices:
  76.         c = cells[i]
  77.         if c != 0:
  78.             if c in s:
  79.                 return False
  80.             s.add(c)
  81.     return True
  82.  
  83.  
  84. def validate_row(cells, y):
  85.     s = set()
  86.     for i in range(9):
  87.         c = cells[x + i * 9]
  88.         if c != 0:
  89.             if c in s:
  90.                 return False
  91.             s.add(c)
  92.     return True
  93.  
  94.  
  95. def find_next(flags, i):
  96.     _i = i + 1
  97.     return _i + flags[_i:].index(False)
  98.  
  99.  
  100. def back_track(flags, i):
  101.     return list_rindex(flags[:i], False)
  102.  
  103.  
  104. def list_rindex(_list, value):
  105.     for i in range(len(_list) - 1, -1, -1):
  106.         if _list[i] == value:
  107.             return i
  108.     raise ValueError()
  109.  
  110.  
  111. def print_cells(cells):
  112.     for i in range(9):
  113.         print(''.join(str(n) for n in cells[i*9:i*9+9]))
  114.  
  115.  
  116. main()
Success #stdin #stdout 0.18s 28384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
https://ideone.com/TSJo4P
language:
Python 3 (python  3.9.5)
created:
7 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!