• API
• FAQ
• Tools
• Archive
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))
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.
Top