SHARE
TWEET

Untitled

a guest Jan 22nd, 2020 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from itertools import product, starmap
  2.  
  3. data = [
  4.  [1, 1, 2, 3, 3, 3, 3, 3],
  5.  [1, 2, 2, 3, 2, 3, 5, 3],
  6.  [1, 4, 2, 2, 2, 5, 5, 3],
  7.  [1, 4, 6, 6, 6, 7, 5, 3],
  8.  [1, 4, 6, 6, 7, 7, 5, 3],
  9.  [1, 4, 4, 8, 7, 7, 5, 5],
  10.  [4, 4, 8, 8, 8, 7, 7, 5],
  11.  [4, 4, 8, 8, 8, 7, 7, 7]
  12. ]
  13.  
  14. regions = [0] * 8
  15. for i in range(8):
  16.     regions[i] = []
  17.  
  18. for i in range(8):
  19.   for j in range(8):
  20.     regions[data[i][j] - 1].append([i, j])
  21.  
  22. def count_region(grid, row, col):
  23.   region = regions[data[row][col] - 1]
  24.   count = 0
  25.   for i in range(len(region)):
  26.     cell = region[i]
  27.     if grid[cell[0]][cell[1]] == 2: count += 1
  28.   return count
  29.  
  30. def count_neighbors(grid, row, col):
  31.  
  32.   #print("Checking at: " + str(row) + ":" + str(col))
  33.  
  34.   neighbors = list(starmap(lambda a, b: (row + a, col + b), product((0,-1,+1), (0,-1,+1))))[1:]
  35.  
  36.   #print("... neighbors are: " + str(neighbors))
  37.  
  38.   count = 0
  39.   for i in range(len(neighbors)):
  40.     cell = neighbors[i]
  41.     if cell[0] < 0 or cell[1] < 0 or cell[0] >= 8 or cell[1] >= 8: continue
  42.     #print("Cell is at: " + str(cell[0]) + ":" + str(cell[1]))
  43.     if grid[cell[0]][cell[1]] == 2: count += 1
  44.   return count
  45.  
  46. def count_row(grid, row):
  47.   count = 0
  48.   for i in range(8):
  49.     if grid[row][i] == 2: count += 1
  50.   return count
  51.  
  52. def count_col(grid, col):
  53.   count = 0
  54.   for i in range(8):
  55.     if grid[i][col] == 2: count += 1
  56.   return count
  57.  
  58. def is_safe(grid, row, col, num):
  59.   if count_neighbors(grid, row, col) >= 1: return False
  60.   # if count_region(grid, row, col) >= 2: return False
  61.   if count_row(grid, row) >= 2: return False
  62.   if count_col(grid, col) >= 2: return False
  63.   return True
  64.  
  65. def find_empty(grid):
  66.   #for i in range(8):
  67.   #  if count_col(grid, i) != 2: return False
  68.   #  if count_row(grid, i) != 2: return False
  69.   #  for j in range(8):
  70.   #    if count_neighbors(grid, i, j) != 0: return False
  71.   #  cell = regions[i][0]
  72.   #  if count_region(grid, cell[0], cell[1]) != 2: return False
  73.   for i in range(8):
  74.     for j in range(8):
  75.       if grid[i][j] == 0: return i, j, True
  76.   return 0, 0, False
  77.  
  78. def is_solved(grid):
  79.   for i in range(8):
  80.     if count_col(grid, i) != 2: return False
  81.     if count_row(grid, i) != 2: return False
  82.     for j in range(8):
  83.       if count_neighbors(grid, i, j) != 0: return False
  84.       cell = regions[i][0]
  85.     if count_region(grid, cell[0], cell[1]) != 2: return False
  86.  
  87. def solve(grid):
  88.   row, col, found = find_empty(grid)
  89.  
  90.   # if found: print("Empty: " + str(row) + ":" + str(col))
  91.   if not found and is_solved(grid): return True
  92.  
  93.   for num in range(1, 3):
  94.     #print("Trying: " + str(num) + ", " + str(row) + ":" + str(col))
  95.     if is_safe(grid, row, col, num):
  96.       grid[row][col] = num
  97.       if solve(grid):
  98.         return True
  99.       grid[row][col] = 0
  100.   return False
  101.  
  102. import sys
  103. sys.setrecursionlimit(200000000)
  104.  
  105. g = [0] * 8
  106. for i in range(8):
  107.     g[i] = [0] * 8
  108.  
  109. solve(g)
  110.  
  111. for i in range(8):
  112.   print(g[i])
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top