1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
| class Sudoku:
sudoku_digits = set('123456789')
block_size = 3
grid_size = block_size * block_size
rows_sets = []
cols_sets = []
blocks_sets = []
cells_arr = [0] * grid_size * grid_size
task_cells = set()
#==========================================================================
def __init__(self):
for k in range(Sudoku.grid_size):
self.rows_sets.append(set())
self.cols_sets.append(set())
self.blocks_sets.append(set())
#==========================================================================
def get_block_row(i):
return i // Sudoku.block_size
#==========================================================================
def get_block_col(j):
return j // Sudoku.block_size
#==========================================================================
def get_block_ind(i, j):
return Sudoku.get_block_row(i) * Sudoku.block_size + Sudoku.get_block_col(j)
#==========================================================================
def good_add_task_row(self, row, i):
row = row.replace(' ', '')
row = row.replace('\t', '')
if len(row) == 0:
return True
res = row.isdigit()
if not res:
print('Строка должна содержать только цифры и пробелы.')
return res
res = len(row) == Sudoku.grid_size
if not res:
print('Строка должна содержать', Sudoku.grid_size, 'цифр.')
return res
row_without_zeros = row.replace('0','')
set_without_zeros = set(row_without_zeros)
res = len(row_without_zeros) == len(set_without_zeros)
if not res:
print('Ненулевые цифры в строке не должны повторяться.')
return res
for j in range(Sudoku.grid_size):
if row[j] == '0':
continue
res = row[j] not in self.cols_sets[j]
if not res:
print('В столбце', j + 1, 'уже есть цифра', row[j])
return res
block_ind = Sudoku.get_block_ind(i, j)
res = row[j] not in self.blocks_sets[block_ind]
if not res:
block_row_begin = Sudoku.get_block_row(i) * Sudoku.block_size + 1
block_row_end = block_row_begin + Sudoku.block_size - 1
block_col_begin = Sudoku.get_block_col(j) * Sudoku.block_size + 1
block_col_end = block_col_begin + Sudoku.block_size - 1
print('В блоке со строками', block_row_begin, '-', block_row_end,\
'и столбцами', block_col_begin, '-', block_col_end, 'уже есть цифра', row[j], '.')
return res
for jj in range(Sudoku.grid_size):
if row[jj] != '0':
self.cols_sets[jj].add(row[jj])
self.blocks_sets[Sudoku.get_block_ind(i, jj)].add(row[jj])
self.task_cells.add((i, jj))
self.cells_arr[Sudoku.get_cells_arr_ind(i, jj)] = '\033[4m' + row[jj] + '\033[0m'
self.rows_sets[i] = set_without_zeros
return res
#==========================================================================
def input_task(self):
print('Введите строки-задания из 9 цифр (можно с пробелами), на месте пустых клеток ставьте нули,')
print('например: 400 803 001. \nЕсли строка с каким-то номером не содержит цифр-заданий - просто нажмите Enter.')
i = 0
while i < self.grid_size:
s = 'строка ' + str(i + 1) + ': '
row = input(s)
if not self.good_add_task_row(row, i):
print('Повторите ввод.')
else:
i += 1
print()
#==========================================================================
def get_cells_arr_ind(i, j):
return i * Sudoku.grid_size + j
#==========================================================================
def remove_and_get_dig_from_cell(self, i, j):
old_dig = self.cells_arr[Sudoku.get_cells_arr_ind(i, j)]
self.cells_arr[Sudoku.get_cells_arr_ind(i, j)] = 0
self.rows_sets[i].remove(old_dig)
self.cols_sets[j].remove(old_dig)
self.blocks_sets[Sudoku.get_block_ind(i, j)].remove(old_dig)
return old_dig
#==========================================================================
def insert_dig_in_cell(self, dig, i, j):
self.cells_arr[Sudoku.get_cells_arr_ind(i, j)] = dig
self.rows_sets[i].add(dig)
self.cols_sets[j].add(dig)
self.blocks_sets[Sudoku.get_block_ind(i, j)].add(dig)
#==========================================================================
def good_insert_min_dig_in_cell_greater_than(self, old_dig, i, j):
cell_dig_set = \
Sudoku.sudoku_digits - \
(self.rows_sets[i] | self.cols_sets[j] | self.blocks_sets[Sudoku.get_block_ind(i, j)])
res = len(cell_dig_set) != 0
if res:
cell_dig_list = list(cell_dig_set)
cell_dig_list.sort()
for dig in cell_dig_list:
res = dig > old_dig
if res:
self.insert_dig_in_cell(dig, i, j)
break
return res
#==========================================================================
def good_inc_dig_in_cell_or_remove(self, i, j):
old_dig = self.remove_and_get_dig_from_cell(i, j)
return self.good_insert_min_dig_in_cell_greater_than(old_dig, i, j)
#==========================================================================
def good_insert_min_dig_in_cell(self, i, j):
cell_dig_set = \
Sudoku.sudoku_digits - \
(self.rows_sets[i] | self.cols_sets[j] | self.blocks_sets[Sudoku.get_block_ind(i, j)])
res = len(cell_dig_set) != 0
if res:
cell_dig_list = list(cell_dig_set)
min_good_dig = min(cell_dig_list)
self.insert_dig_in_cell(min_good_dig, i, j)
return res
#==========================================================================
def create_solution(self):
cell_ind = 0
inserting_digits = True
while 0 <= cell_ind < Sudoku.grid_size * Sudoku.grid_size:
i, j = divmod(cell_ind, Sudoku.grid_size)
if inserting_digits:
if (i, j) not in self.task_cells and not self.good_insert_min_dig_in_cell(i, j):
inserting_digits = False
cell_ind -= 1
continue
else:
cell_ind += 1
continue
else: #Увеличиваем цифры в клетках.
if (i, j) not in self.task_cells and self.good_inc_dig_in_cell_or_remove(i, j):
inserting_digits = True
cell_ind += 1
continue
else:
cell_ind -= 1
#==========================================================================
def print_solution(self):
print('РЕШЕНИЕ (заданные цифры подчеркнуты):')
for i in range(Sudoku.grid_size):
cells_arr_row = self.cells_arr[ i * Sudoku.grid_size : (i + 1) * Sudoku.grid_size ]
cells_arr_row.insert(Sudoku.block_size * 2, '|')
cells_arr_row.insert(Sudoku.block_size * 1, '|')
cells_arr_row.insert(Sudoku.block_size * 0, '|')
str_row = ' '.join(cells_arr_row)
str_row = 'Строка ' + str(i + 1) + ':\t' + str_row
if i > 0 and i % Sudoku.block_size == 0:
print('----------------------------------------------')
print(str_row)
#=============================================================================
def main():
sudoku = Sudoku()
sudoku.input_task()
sudoku.create_solution()
sudoku.print_solution()
#=============================================================================
main() |
(
Сообщение было отмечено aana как решение
