Решалка судоку: сам не представляю, как она у меня получилась

В этой статье мы разберём, как написать программу для решения судоку. Предполагается, что ранее читатель не пробовал алгоритмически решать судоку, тем более — с применением нейронных сетей.

Я легко увлекаюсь. Мои пристрастия меняются, но сейчас на первых ролях — многопользовательские партии в Call of Duty: Modern Warfare 3 и судоку. Что касается второй — мне нравится, как она разгружает мне голову и умиротворяет меня. Здесь только вы, числа и достаточно очевидные стратегии, позволяющие выиграть.

В какой-то момент я решил, что пора завязывать с этой вредной привычкой, которая калечит жизни людям и разбивает семьи. У меня выдались свободные выходные, когда не было срочных дел, поэтому мне показалось, что лучше всего потратить это время на разработку решалки для судоку. Она будет работать так: делаем скриншот или фото партии в судоку, парсим изображение, решаем задачу, отображаем решение, получаем порцию дофамина посреди мучительной опустошённости и живём дальше.

❯ Кстати: а что такое судоку?

Начнём с основ. Что такое судоку? Вероятно, всем читателям знакома эта простая игра с числами. Есть большой квадрат, состоящий из 81 квадрата поменьше. В каждом квадрате может содержаться число. Также внутри большого квадрата выстраиваются девять квадратов размером 3×3 клетки каждый. В каждой строке и в каждом ряду числа повторяться не могут, причём, это могут быть лишь цифры от 1 до 9. Некоторые квадраты пусты, и суть игры в том, чтобы угадать недостающие числа, придерживаясь заданных ограничений.

Вот картинка для гроссмейстеров: в каждой из областей, обведённых красным, может содержаться не более одной цифры 8.

Существуют различные вариации этой игры (может отличаться форма поля, количество квадратов, действующие ограничения, но ради простоты мы не будем здесь их рассматривать).

❯ Продумываем решение ദ്ദി(˵ •̀ ᴗ – ˵ ) ✧

Каждое решение нужно сначала обрисовать в общих чертах. Вот как это сделал я:

Нам понадобится механизм для взаимодействия с решалкой судоку (естественно, для этой цели я напишу телеграмм-бота — другого варианта просто нет), распознаватель судоку и, собственно, решалка. Вот и всё.

Задача кажется лёгкой, наверное, решается быстро.

Но это только кажется L. На самом деле, она достаточно лёгкая, но мне не хотелось просто взять и скопипастить одно из тех отличных решений, что выложены в Интернете. Напротив, я хотел их понять и повторно реализовать сам! Серые клеточки заводятся гррррр!

❯ Как бездушные машины решают судоку?

Первым делом я решил исключительно своими силами написать алгоритм для решения судоку, так как почему нет? Потом я осознал, почему, и стал как следует копать тему. Под «копать тему» я имею в виду, что изучил два первых источника из поисковой выдачи Google — и выяснил, что эта задача уже хорошо известна, а также качественно решена и описана в отличной статье Питера Норвига «Solving Every Sudoku Puzzle», причём, она существует и в новой версии в виде ноутбука для ipython.

В основе статьи заложены достаточно простые идеи: в ней используется поиск в глубину и распространение/удовлетворение ограничений.

Ограничения игры в судоку нам известны: каждая цифра может лишь раз фигурировать в каждом столбце, каждом ряду и каждом квадрате 3×3. Таким образом, мы рекурсивно проходим представление игрового поля, содержащееся в оперативной памяти, исключаем те числа, которые уже встречались и, соответственно, больше встретиться не могут, а затем снова применяем алгоритм. Мы побеждаем, если все ограничения соблюдены, и в каждую клетку подходит ровно одно значение. В случае, если победить не удалось, мы рекурсивно возвращаемся по стеку к тому этапу, на котором это было возможно и пробуем какой-нибудь другой вариант. Если на всех итерациях мы не нашли нужных цифр и вернулись к самому началу — значит, эта судоку нерешаема.

Можете сразу взглянуть на мою реализацию, но лучше загляните в исходную работу Питера — там всё изложено по-настоящему ясно и просто.

Я анализировал решение, копировал и вставлял фрагменты кода и несколько раз всё переписывал, пока не обнаружил, что забываю применить ограничения перед началом поиска. Осенило меня лишь через несколько часов работы, но, в конце концов, у меня получился интерфейс, имеющий примерно следующий вид:

>>> input_str = "..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3.."
>>> puzzle = Sudoku.from_string(input_str)
>>> solution = puzzle.solve()
>>> print(solution.cli_display())

4 8 3|9 2 1|6 5 7
9 6 7|3 4 5|8 2 1
2 5 1|8 7 6|4 9 3
-----+-----+-----
5 4 8|1 3 2|9 7 6
7 2 9|5 6 4|1 3 8
1 3 6|7 9 8|2 4 5
-----+-----+-----
3 7 2|6 8 9|5 1 4
8 1 4|2 5 3|7 6 9
6 9 5|4 1 7|3 8 2

❯ Обработка изображений в судоку

Обнаружение полей

Далее началась часть, в которой я не очень-то ориентируюсь: распознавание изображений. Да, я прошёл несколько курсов по машинному обучению и даже вёл пару пет-проектов по распознаванию лиц в потоковом видео, но я в самом деле не утруждал себя этой работой, довольствуясь готовыми примерами (спойлер: именно так всё сложилось и на этот раз (¬_¬”)).

Получившийся у меня конвейер обработки изображений выглядел так:

• Загружаем картинку

• Преобразуем её в градации серого и применяем к ней некоторое размытие по Гауссу

• Применяем детектор границ Кэнни, чтобы подчеркнуть на картинке границы, разделяющие сильно контрастные области

• Применяем нахождение контуров, чтобы извлечь из объектов информацию об их границах

• Находим самый крупный прямоугольник на картинке (предполагаем, что это будет самый большой квадрат, то есть, игровое поле судоку)

• Деформируем перспективу найденного изображения, так, чтобы можно было уверенно извлекать из него клетки и далее применять преобразование, чтобы поле выглядело плоским.

Результаты просто восхитительны!

До:

После:

❯ Извлекаем цифры

Теперь у нас есть квадрат. Хорошо. Мы знаем, как он скомпонован, так что далее остаётся заняться простой математикой: разбиваем квадрат на множество из 81 равновеликого изображения.

 def extract_cells(self, squared_image_path: pathlib.Path, cell_size=50):
        # Читаем изображение в градациях серого
        gray_image = cv2.imread(squared_image_path, cv2.IMREAD_GRAYSCALE)

        if gray_image is None:
            raise ValueError("Could not load the image, check the path.")

        # Предполагаем, что всё изображение — это сетка судоку, находим размер сетки 
        grid_size = gray_image.shape[0]  # Assuming the image is a square

        # Находим размер каждой клетки
        cell_height = grid_size // 9
        cell_width = grid_size // 9

        # Инициализируем массив, где клетки будут содержаться в итоге
        cells = np.zeros((81, cell_size, cell_size), dtype=np.uint8)

        for i in range(9):
            for j in range(9):
                #Вычисляем исходную точку актуальной клетки
                y = i * cell_height
                x = j * cell_width

                cell = gray_image[y : y + cell_height, x : x + cell_width]
                cell_resized = cv2.resize(
                    cell, (cell_size, cell_size), interpolation=cv2.INTER_AREA
                )
                cells[i * 9 + j] = cell_resized

        return cells

❯ Распознавание цифр!

Нейронные сети MNIST

Теперь у нас есть 81 квадрат, и в каждом из квадратов могут быть некоторые цифры. Мы должны понять, что это будут за цифры, и какие клетки останутся пусты, а потом преобразовать эту информацию в такой вид, в котором её можно было бы передать нашей решалке. Я полагал, что задача распознавания изображений уже так хорошо проработана, что найдётся куча подключаемых решений, с которыми можно работать — но ошибался.

Мне попадалась какая-то информация о датасете MNIST, и я собирался просто подобрать наилучшее из имеющихся решений, которое сработает и в моём случае. Я погуглил, нашёл несколько нейронных сетей, которые, как представлялось, хорошо распознают цифры. Далее я решил следовать инструкциям и обучить этому мою собственную нейронную сеть!

Модель

# Эта модель была взята откуда-то из Kaggle, но мне в самом деле не удаётся найти точную ссылку
# на неё :(
def create_model():
    model = tf.keras.models.Sequential([
        tf.keras.layers.Conv2D(32, (5,5), padding='same', activation='relu', input_shape=(28, 28, 1)),
        tf.keras.layers.Conv2D(32, (5,5), padding='same', activation='relu'),
        tf.keras.layers.MaxPool2D(),
        tf.keras.layers.Dropout(0.25),
        tf.keras.layers.Conv2D(64, (3,3), padding='same', activation='relu'),
        tf.keras.layers.Conv2D(64, (3,3), padding='same', activation='relu'),
        tf.keras.layers.MaxPool2D(strides=(2,2)),
        tf.keras.layers.Dropout(0.25),
        tf.keras.layers.Flatten(),
        tf.keras.layers.Dense(128, activation='relu'),
        tf.keras.layers.Dropout(0.5),
        tf.keras.layers.Dense(num_classes, activation='softmax')
    ])
    model.compile(
        optimizer=tf.keras.optimizers.RMSprop(epsilon=1e-08),
        loss=tf.keras.losses.SparseCategoricalCrossentropy(from_logits=True),
        metrics=[tf.keras.metrics.SparseCategoricalAccuracy()]
    )
    return model

Процесс обучения

Я вдохновился и сразу применил её с моими данными, но разочаровался. Я полагал, что она будет прямо «из коробки» как по волшебству распознавать цифры судоку — но она этого не делала.

Красные цифры на картинке — это догадки нейронной сети, а чёрные — те, что исходно были на поле.

Я немного поэкспериментировал с предобработкой изображения, корректировкой размера и прочими ухищрениями, но ничего не получилось

❯ Старый добрый OCR

Я был разочарован, но вскоре вспомнил, что технология распознавания изображений давно отработана, и для этого существуют OCR-решения, например, Tesseract. Его я сразу и попробовал. Потребовалось подобрать параметры, но даже при максимально качественной предобработке, которую я мог выполнить, он не справился с задачей. Я также попытался применить сразу несколько конфигураций распознавания и выбрал ту, которая работала примерно так:

def tesseract_image(image) -> int:
    """
    BIG BRAIN MOVE
    """
    vals = []
    configs = [
        "-l osd --psm 10 --oem 1",
        "--psm 10 --oem 1",
    ]
    for config in configs:
        try:
            output = pytesseract.image_to_string(image, config=config).strip()
            val = int(output[:1])
            return val
        except ValueError:
            vals.append(-1)

    return max(vals)

Это решение работало лучше предыдущего, но некоторые цифры всё равно не распознавались. Кроме того, выполнять 81*2=164 попыток распознать через tesseract каждую цифру было непозволительно медленно.

При некоторых попытках модель распознавала все цифры, иногда неверно интерпретировала одну из ячеек, тем самым ставя крест на решении всей головоломки. Так что от этой идеи я отказался.

❯ Настройка модели

Оставалось неиспробованным всего одно решение: подогнать мои исходные данные к тем цифрам, которые попадались в головоломках, решённых ранее. Я сделал набор скриншотов и фотографий, сложил все квадраты с цифрами в один каталог, а потом вручную их разметил.

Затем я взял сохранённую модель и настроил её на материале имеющихся данных (Это совсем не сложно!):

# Создаём датасет изображений и меток из каталога
train_dataset = tf.keras.utils.image_dataset_from_directory(
    "for_fitting",
    image_size=(28, 28),
    color_mode="grayscale",
    batch_size=32,
    label_mode="int",
    shuffle=True,
)

# Нормируем значения пикселей до [0,1]
normalization_layer = tf.keras.layers.Rescaling(1.0 / 255)
train_dataset = train_dataset.map(lambda x, y: (normalization_layer(x), y))

model = tf.keras.models.load_model("mnist.keras")
# Настраиваем модель с учётом новых данных
model.fit(train_dataset, epochs=10)

model.save("mnist-fit.keras")

Попробовал – сработало. И во второй раз. И в третий. Всё работало молниеносно и безошибочно, модель с лёгкостью разгадывала любую судоку. Меня озарило лучами счастья, и я почувствовал, что приблизился к Богу.

❯ Телеграм-бот

Проще всего было написать телеграм-бот и развернуть его в контейнере Docker. В какой-то момент возникла единственная проблема — как собрать его из разных безумных библиотек, которые предварительно нужно было установить в среде Poetry для Docker. Это мне не удалось, так что я просто воспользовался Rye, которая сработала на удивление хорошо.

❯ Результаты

Занимаясь этим проектом, я не раз чувствовал себя тупым. Я ничего не знаю об OpenCV, поэтому обычно просто находил нужный код, копировал его и вставлял куда нужно. В данном случае я логически понял его структуру и все шаги в рамках проекта, но, думаю, без доступа к Google не смог бы его воспроизводить. Я был шокирован, что задача распознавания цифр даже в наше время остаётся, скажем так, нетривиальной.

Кроме того, я удивился, в каком направлении сейчас развивается инструментарий Python со всеми этими Rye и UV, а также другими вещами, которые пока в разработке.

Определённо, это был приятный опыт. Я не жалею о потраченном времени и решительно рекомендую всем завести такой пет-проект, который можно самостоятельно проделать от начала и до конца примерно за неделю.

Конечно, моё решение игрушечное. В нём требуется ещё массу всего улучшить и откорректировать. Для выполнения этой работы в режиме реального времени можно было бы попробовать фреймворк Vision от Apple и сделать всё в специальном приложении на Swift, но об этом как-нибудь в следующий раз!

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале