В качестве разминки и дополнительной практики в программировании решил предложить Андрею попробовать написать программу для решения судоку (числовой головоломки). Их в последнее время регулярно публикуют в районной газете, которую периодически кладут в почтовый ящик. А для дополнительной мотивации и в качестве примера решил и сам написать такую программу.
В итоге, я выбрал Python, а Андрей изучаемую им сейчас Java. Получилось своего рода соревнование (или как сейчас говорят "батл" или "челендж").
Моё решение (на Python) уже готово, хотя, конечно, можно ещё поработать над оформлением кода и вывода найденного решения (посмотреть код).
-
- __author__ = 'Stelletskiy_vv'
-
- print(u"2023 Stelletsky V.")
- print(u"Решение СУДОКУ
- ")
-
- numbers = frozenset({1, 2, 3, 4, 5, 6, 7, 8, 9})
- debug = False
-
- class Ceil():
- def __init__(self, r, c):
- self.r = r
- self.c = c
-
- if r <= 2:
- nr = 0
- elif r > 5:
- nr = 2
- else:
- nr = 1
-
- if c<=2:
- nc = 0
- elif c > 5:
- nc = 2
- else:
- nc = 1
-
- self.square = nc + nr * 3
- self.value = set()
-
- def __repr__(self):
- return '(r=%s, c=%s, q=%s)' % (self.r, self.c, self.square)
-
-
- def row(r):
- return set(su[r])
-
-
- def col(c):
- s = set()
- for i in range(9):
- s.add(su[i][c])
- return s
-
-
- def square(r, c):
- s = set()
- if r<=2:
- r1 = 0
- r2 = 2
- elif r>5:
- r1 = 6
- r2 = 8
- else:
- r1 = 3
- r2 = 5
-
- if c<=2:
- c1 = 0
- c2 = 2
- elif c>5:
- c1 = 6
- c2 = 8
- else:
- c1 = 3
- c2 = 5
- while r1<= r2:
- cc = c1
- while cc<= c2:
- s.add(su[r1][cc])
- cc += 1
- r1 += 1
- return s
-
- fields = []
- su = []
- wl = []
- r = 0
- c = 0
- with open("test9.su", "r") as f:
- for line in f:
- line = line.strip()
- print(line)
- su.append([])
- c = 0
- for char in line:
- if char.isdigit() and 0 < int(char) <= 9:
- su[r].append(int(char))
- else:
- su[r].append(None)
- wl.append((r,c))
- c += 1
- r += 1
- all_cnt = len(wl)
- print('Надо заполнить %s клеток' % all_cnt)
-
- cc = 0
- f = 0
- answ = 0
- fields.append(su)
- while len(fields) > 0:
- if cc != 0:
- print('Решаем последний сохранённый вариант:')
- f += 1
- su = fields.pop()
- err = False
-
- while True:
- wl = []
-
- for r in range(9):
- if r > 0 and r % 3 == 0:
- print('---+---+---')
- s = ''
- for c in range(9):
- if c > 0 and c % 3 == 0:
- s += '|'
- if su[r][c] == None:
- s += '.'
- wl.append((r,c))
- else:
- s += str(su[r][c])
- print(s)
-
-
- ceils = []
- for (r, c) in wl:
- ceil = Ceil(r, c)
- ceil.value = set(numbers) - square(r, c) - row(r) - col(c)
- if debug:
- print(ceil, ceil.value)
- ceils.append(ceil)
-
-
- cnt = 0
- squares = {}
- for c in ceils:
- if len(c.value) == 0:
- print('Ошибка! - Нет значений для ячейки %s' % c)
- err = True
- break
- if len(c.value) == 1:
-
- v = c.value.pop()
- print('Однозначная позиция %s в %s' % (v, c))
- if v in square(c.r, c.c) or v in row(c.r) or v in col(c.c):
- print('Ошибка! - значение %s уже добавлено (заполнение ячейки %s)' % (v, c))
- for ceil in ceils:
- print(ceil, ceil.value)
- print(su)
- err = True
- break
- else:
- su[c.r][c.c] = v
- cnt += 1
- else:
- if c.square in squares:
- squares[c.square] = squares[c.square] + list(c.value)
- else:
- squares[c.square] = list(c.value)
-
- if err:
- break
-
-
- if cnt == 0:
- if debug:
- print(squares)
-
- for q in squares:
- if err:
- break
- for v in set(squares[q]):
- if err:
- break
- if squares[q].count(v) == 1:
- print('Нашли %s в квадрате %s' % (v, q))
- for c in ceils:
- if len(c.value) == 0:
- print('Ошибка! - Нет значений для ячейки %s' % c)
- err = True
- break
- elif c.square == q and v in c.value:
- su[c.r][c.c] = v
- cnt += 1
-
- if err:
- break
-
-
- if cnt == 0:
-
- for c in ceils:
- if len(c.value) == 0:
- print('Ошибка! - Нет значений для ячейки %s' % c)
- err = True
- break
- if len(c.value) == 2:
- print('Начинаем перебор для ячейки %s значения %s' % (c, c.value))
- new = []
- for r in range(9):
- new.append(su[r][:])
- print(su)
- su[c.r][c.c] = c.value.pop()
- new[c.r][c.c] = c.value.pop()
- print(su)
- print(new)
- fields.append(new)
- cnt += 1
- break
-
- if err:
- break
-
- cc += 1
- if len(wl) == 0:
- print('Решено за %s проходов
- ' % cc)
- answ +=1
- break
-
- print('Заполнили %s (осталось %s из %s клеток):' % (cnt, len(wl)-cnt, all_cnt))
-
- if cnt == 0:
- print('Решить не получилось (%s проходов)' % cc)
- break
-
- if f != 1 or answ != 1:
- print('Найдено %s решений' % answ)
# -*- coding: utf-8 -*-
__author__ = 'Stelletskiy_vv'
print(u"2023 Stelletsky V.")
print(u"Решение СУДОКУ
")
numbers = frozenset({1, 2, 3, 4, 5, 6, 7, 8, 9})
debug = False
class Ceil():
def __init__(self, r, c):
self.r = r
self.c = c
if r <= 2:
nr = 0
elif r > 5:
nr = 2
else:
nr = 1
if c<=2:
nc = 0
elif c > 5:
nc = 2
else:
nc = 1
self.square = nc + nr * 3
self.value = set()
def __repr__(self):
return '(r=%s, c=%s, q=%s)' % (self.r, self.c, self.square)
def row(r):
return set(su[r])
def col(c):
s = set()
for i in range(9):
s.add(su[i][c])
return s
def square(r, c):
s = set()
if r<=2:
r1 = 0
r2 = 2
elif r>5:
r1 = 6
r2 = 8
else:
r1 = 3
r2 = 5
if c<=2:
c1 = 0
c2 = 2
elif c>5:
c1 = 6
c2 = 8
else:
c1 = 3
c2 = 5
while r1<= r2:
cc = c1
while cc<= c2:
s.add(su[r1][cc])
cc += 1
r1 += 1
return s
fields = []
su = []
wl = []
r = 0
c = 0
with open("test9.su", "r") as f:
for line in f:
line = line.strip()
print(line)
su.append([])
c = 0
for char in line:
if char.isdigit() and 0 < int(char) <= 9:
su[r].append(int(char))
else:
su[r].append(None)
wl.append((r,c))
c += 1
r += 1
all_cnt = len(wl)
print('Надо заполнить %s клеток' % all_cnt)
cc = 0
f = 0
answ = 0
fields.append(su)
while len(fields) > 0:
if cc != 0:
print('Решаем последний сохранённый вариант:')
f += 1
su = fields.pop()
err = False
while True:
wl = []
# заполняем новый рабочий список
for r in range(9):
if r > 0 and r % 3 == 0:
print('---+---+---')
s = ''
for c in range(9):
if c > 0 and c % 3 == 0:
s += '|'
if su[r][c] == None:
s += '.'
wl.append((r,c))
else:
s += str(su[r][c])
print(s)
# обрабатываем рабочий список (пустые ячейки)
ceils = []
for (r, c) in wl:
ceil = Ceil(r, c)
ceil.value = set(numbers) - square(r, c) - row(r) - col(c)
if debug:
print(ceil, ceil.value)
ceils.append(ceil)
# пробегаемся по списку ячеек и пытаемся заполнить те, где нет вариантов (одно значение)
cnt = 0
squares = {}
for c in ceils:
if len(c.value) == 0:
print('Ошибка! - Нет значений для ячейки %s' % c)
err = True
break
if len(c.value) == 1:
# проверяем, что вставить можно
v = c.value.pop()
print('Однозначная позиция %s в %s' % (v, c))
if v in square(c.r, c.c) or v in row(c.r) or v in col(c.c):
print('Ошибка! - значение %s уже добавлено (заполнение ячейки %s)' % (v, c))
for ceil in ceils:
print(ceil, ceil.value)
print(su)
err = True
break
else:
su[c.r][c.c] = v
cnt += 1
else:
if c.square in squares:
squares[c.square] = squares[c.square] + list(c.value)
else:
squares[c.square] = list(c.value)
if err:
break
# если ячеек с единичным значением не найдено, то проверяем ячейки, где есть единственная возможность установить
if cnt == 0:
if debug:
print(squares)
# пробуем найти уникальные позиции
for q in squares:
if err:
break
for v in set(squares[q]):
if err:
break
if squares[q].count(v) == 1:
print('Нашли %s в квадрате %s' % (v, q))
for c in ceils:
if len(c.value) == 0:
print('Ошибка! - Нет значений для ячейки %s' % c)
err = True
break
elif c.square == q and v in c.value:
su[c.r][c.c] = v
cnt += 1
if err:
break
# если решить всё равно не получается - включаем перебор
if cnt == 0:
# ищем ячейку с двумя вариантами
for c in ceils:
if len(c.value) == 0:
print('Ошибка! - Нет значений для ячейки %s' % c)
err = True
break
if len(c.value) == 2:
print('Начинаем перебор для ячейки %s значения %s' % (c, c.value))
new = []
for r in range(9):
new.append(su[r][:])
print(su)
su[c.r][c.c] = c.value.pop()
new[c.r][c.c] = c.value.pop()
print(su)
print(new)
fields.append(new)
cnt += 1
break
if err:
break
cc += 1
if len(wl) == 0:
print('Решено за %s проходов
' % cc)
answ +=1
break
print('Заполнили %s (осталось %s из %s клеток):' % (cnt, len(wl)-cnt, all_cnt))
if cnt == 0:
print('Решить не получилось (%s проходов)' % cc)
break
if f != 1 or answ != 1:
print('Найдено %s решений' % answ)
Андрей же пока реализовал только часть алгоритма, но простые судоку из газеты его программа уже тоже решает. Осталось сделать возможность перебора вариантов, когда нет логически однозначного решения (надеюсь доделает).
Теперь думаю чтобы ещё ему предложить.
PS: А ещё подумываю о реализации решения этой же задачи на Go, чтобы освежить в голове синтаксис этого языка программирования.