Судоку – это игра, в которой игровое поле представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые подсказками. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.
Процесс решения мы разобьём на несколько этапов:
Определение границ судоку и выравнивание поля (OpenCV)
Распознание исходных данных (подсказок) (EasyOCR)
Решение задачи (PuLP)
Отображение ответа на исходном изображении
Для решения первой задачи мы воспользуемся OpenCV.
Сначала открываем изображение и находим на нём все контуры. Для этого необходимо перевести изображение в серые тона, наложить размытие (чтобы сгладить шум) и при помощи функции порога adaptiveThreshold на изображении оставляем только главные контуры:
Чтобы найти на фото квадрат с судоку предположим, что он будет являться самым большим квадратом на изображении. Для этого при помощи аппроксимации контуров возьмём наибольший по площади контур с 4 сторонами и отсортируем координаты углов по часовой стрелке:
# Для поиска сетки судоку находим наибольший квадрат на изображении
location = None
for cnt in cnts:
approx = cv2.approxPolyDP(cnt, 15, True)
if len(approx) == 4:
# Сортировка углов по часовой стрелке
rect = np.zeros((4, 2), dtype = "float32")
cutt = approx[:,0]
diag_1 = cutt.sum(axis = 1)
rect[0] = cutt[np.argmin(diag_1)]
rect[2] = cutt[np.argmax(diag_1)]
diag_2 = np.diff(cutt, axis = 1)
rect[1] = cutt[np.argmin(diag_2)]
rect[3] = cutt[np.argmax(diag_2)]
location = rect
break
Далее создаём квадрат и при помощи getPerspectiveTransform и warpPerspective вписываем в него наш квадрат с судоку:
Теперь нам необходимо распознать подсказки, с чем нам поможет EasyOCR:
# Загружаем модель OCR
import easyocr
reader = easyocr.Reader(['en'])
# Создаём датафрейм и список для записи распознанных результатов
df = pd.DataFrame(index=range(1, 10), columns=range(1, 10))
sudoku_map = []
# Создаём оси для отрисовки разделённых изображений
fig, ax = plt.subplots(9, 9, figsize=(8,8))
Для будущего решения нам потребуется знать значение подсказки, его номер строки и столбца. Так как мы конвертировали изображение в размер 900х900, мы можем получить столбцы судоку просто разделив изображение на 9, а затем разделить каждый столбец на 9 для получения ячеек. Передадим модели параметр allowlist=’0123456789’, чтобы она распознавала только числа:
# Разделяем наш судоку на 9 строк и 9 столбцов и распознаём каждое значение
split = np.split(board, 9, axis=1)
for col,j in enumerate(split):
digs = np.split(j, 9)
for row,d in enumerate(digs):
# Обрежем по 10 пикселей с каждой стороны ячейки, чтобы убрать рамки
d = d[10:90,10:90]
cv2.copyMakeBorder(d,10,10,10,10,cv2.BORDER_CONSTANT)
ax[row][col].imshow(d)
ax[row][col].axis('off')
# Распознаём число в ячейке и записываем его в датафрейм и список с координатами
text = reader.readtext(d, allowlist='0123456789', detail=0)
if len(text) > 0:
df.iloc[row, col] = text[0]
sudoku_map.append([text[0], str(row+1), str(col+1)])
df.fillna('', inplace=True)
df
Результат распознавания:
Как мы видим, все числа распознались корректно.
Остался последний этап – решить судоку. Для этого мы воспользуемся библиотекой PuLP.
PuLP – библиотека линейного программирования на Python. В нашем случае, мы будем искать оптимальное значение для каждой ячейки основываясь исключительно на ограничениях, так как целевой функции в решении судоку нет.
Создаём списки с числами от 1 до 9 (возможные значения для самой ячейки, номера столбца и номера строки) и создаём из них PuLP переменную LpVariable. В нашем случае это словарь значений от 1 до 9, в котором значением может быть 0 или 1, в зависимости от истинности утверждения. Затем объявляем задачу с любой целевой функцией (минимизация или максимизация), вместо формулы задаём 0:
# Создаём списки для перебора в Pulp
nums = [*map(str, [*range(1,10)])] # список чисел от 1 до 9 со строковым типом
rows = nums
cols = nums
vals = nums
# Создаём Pulp словарь с переменными возможных ответов
choices = LpVariable.dicts("Choice", (vals, rows, cols), 0, 1, LpInteger)
# Создаём задачу для Pulp
prob = LpProblem("Судоку", LpMaximize)
prob += 0, "Целевая функция" # Задаётся нулём, так как нас интересует только подбор значения согласно ограничениям
Добавляем в модель ограничения о подборе чисел. Для этого циклами добавляем условия, что сумма значений словаря для каждого числа, строки и столбца будет равна 1:
# Задаём ограничениями условие, что каждое число в каждой строке и каждом столбце должно повторяться не более 1 раза
for r, c in product(rows, cols):
prob += lpSum([choices[v][r][c] for v in vals]) == 1, ""
for v, r in product(vals, rows):
prob += lpSum([choices[v][r][c] for c in cols]) == 1, ""
for v, c in product(vals, cols):
prob += lpSum([choices[v][r][c] for r in rows]) == 1, ""
# Задаём аналогичные ограничения для малых квадратов 3х3
grid = (range(3), range(3))
subs = [[(rows[3*i+k],cols[3*j+l]) for k,l in product(*grid)] for i,j in product(*grid)]
for v,s in product(vals, subs):
prob += lpSum([choices[v][r][c] for (r, c) in s]) == 1, ""
Добавляем подсказки из ранее созданного списка с распознанными значениями. В указанных строке и столбце для значения подсказки ставим 1 (например, для 1 строки и 2 столбца проставим истину для значения 7):
# Добавляем в задачу известные значения, распознанные OCR
for num in sudoku_map:
prob += choices[num[0]][num[1]][num[2]] == 1, ""
На этом подготовка модели завершена и для решения нам осталось добавить всего одну строчку:
# Решаем задачу
prob.solve()
Модель оптимизирует значения ячеек в судоку в соответствии с установленными ограничениями, осталось только посмотреть результат!
# Отрисовка конечного результата
fig, ax = plt.subplots(1,2, figsize=(15,15))
for a in ax:
a.axis('off')
a.imshow(board)
ax[0].set_title('Задача', fontsize=25)
ax[1].set_title('Решение', fontsize=25)
# Пишем решение поверх изображения
y = 50
for r in rows:
x = 50
for c,v in product(cols, vals):
if choices[v][r][c].value() == 1:
if [v,r,c] not in sudoku_map: # Пишем только подобранные значения
ax[1].text(x,y,v, ha='center', va='center', fontsize=25, color='tab:green')
x += 100
y += 100
В заключение хотелось бы сказать, что в рамках поста рассмотрен только один из вариантов решения. Распознавание символов может быть ускорено при наличии GPU с поддержкой CUDA, так как EasyOCR построен на базе PyTorch, либо можно обучить свою модель. Алгоритм подстановки может быть реализован без помощи PuLP, но в рамках поста хотелось показать именно необычный способ использования данной библиотеки для линейного программирования.
