Программа которая решает судоку

Скачать Судоку Мастер 1.00b

Генератор кроссвордов — автоматическая система построения классических кроссвордов. Методом перебора делает 300 тысяч итераций.

Кроссворд — программа для автоматического составления классических кроссвордов. Есть.

Бесплатное приложение, которое представляет собой венгерский кроссворд (филворд), где.

КроссМастер — Составление кроссвордов разных типов — классический, СКАНВОРДЫ, циклические круговые, эстонские, двойные, линейные, линейные с пословицами.

Пирамида — Это новое слово в играх-головоломках! Теперь последовательное отгадывание слов.

КроссВорд — Программа создает классические кроссворды. Сетка генерируется случайным.

Решатель Судоку

В этой работе требуется написать решатель Судоку. Правила игры в Судоку достаточно простые, вот пояснения с Википедии:

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

Далее приведен пример Судоку и его решения:

Чтение пазлов

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

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

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

На текущий момент вашей задачей является написать функцию group() , которая принимает список значений произвольного типа T и размер группы n , а в качестве результата работы возвращает матрицу размера n*n :

Процесс выполнения работы такой же как и предыдущей, поэтому не забудьте активировать виртуальное окружение, создавать новую ветку homework02 , запускать тесты и делать коммиты.

Для решения ряда задач используйте списковые включения. Например, чтобы создать список из четных элементов в диапазоне от 0 до 10 можно использовать такую конструкцию:

Чтобы убедиться в том, что вы верно написали функцию group() воспользуйтесь юнит-тестами:

Обратите внимание как мы указали путь к конкретному тесту файл.ТестКейс.метод . Аналогично мы можем протестировать весь тест-кейс, указав файл.ТестКейс . Если ТестКейс является единственным в файле, то достаточно указать только имя файла.

Если вы корректно реализовали функцию group() , то давайте посмотрим как работает функция read_sudoku() . Запустите скрипт с заходом в интерактивный режим (все пазлы также в репозитории):

Вывод содержимого пазла grid не очень нагляден, поэтому для вас написана функция display() , которая выводит пазл в более человеко-наглядной форме:

Разбивка на строки, колонки и блоки

Так как при решении Судоку ставятся условия, что значения не могут повторяться ни в строке, ни в столбце, ни в квадрате, то следовательно нам эти значения нужно получить. Для этого от вас требуется написать три функции get_row() , get_col() и get_block() , каждая из которых принимает два аргумента: пазл ( grid ) и позицию ( pos ), для которой мы пытаемся найти верное число:

Разберемся с тем, как представлена позиция в программе. Каждая позиция однозначно определяется номером строки и номером столбца, поэтому для ее представления удобно использовать кортеж. Вспомним, что кортеж это неизменяемый список. Позиция создается следующим образом:

Обратите внимание, что для функций get_row() и get_col() приведены примеры в доктестах для доски размером 3*3 . У нас же доска 9*9 , но функции должны работать для доски любого размера. Функция get_block() возвращает все значения из квадрата, в который попадает позиция pos (всего 9 квадратов размером 3*3 ).

Не забудьте запустить тесты и сделать соответствующие коммиты:

Алгоритм решения Судоку

Давайте наконец перейдем к решению самого Судоку. В шаблоне вы найдете функцию solve() , которая принимает один аргумент — пазл, а возвращает заполненную значениями доску:

Мы будем решать Судоку методом перебора (поиска) с возвратом. Общая схема этого метода заключается в следующем:

Решение Судоку чем-то похоже на задачу о возможных комбинациях:

Каждый раз мы удерживаем один элемент и перебираем все остальные. В Судоку все происходит точно также, сначала мы подставляем одно из возможных значений (пункт 2) для свободной позиции (пункт 1) и перебираем все остальные (пункт 3.2), то есть решаем более простую задачу. Например, вот простейшее «Судоку» (это не совсем Судоку конечно), которое мы можем заполнять значениями 1 или 2:

Находим первую свободную позицию (это окажется (0, 1) ), затем значения которые можем на нее поставить (в данном случае только 2), вставляем это значение на указанную позицию и продолжаем решать уже более простое Судоку:

И так продолжаем, пока не заполним все пустые клетки. В конце мы должны получить решение Судоку.

Не забудьте про базовые случаи для выхода из рекурсии, подумайте над вопросами:

• Всегда ли есть свободная позиция?
• Всегда ли есть возможные значения?

Поиск возможных решений

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

Кроме поиска свободных позиций, также необходимо искать значения, которые на эту позицию можно поставить:

Для решения этого задания используйте множества set .

Помните, что всего значений, которые мы можем поставить на указанную позицию, ровно 9 , это числа 1,2,3,4,5,6,7,8,9 . Но не каждое из этих чисел мы можем использовать (см. правила Судоку). В этой функции вы можете пользоваться написанными ранее функциями get_row() , get_col() , get_block() .

К этому моменту функция solve() уже должна быть полностью рабочей:

Проверка решения

Мы получили решение, но является ли оно верным? Давайте напишем функцию check_solution() , которая проверяет наше решение:

Решение оказывается верным, если ни в одной строке, ни в одном столбце, ни в квадрате не повторяются значения:

Когда вы закончите работать над этой функцией, то запустите программу следующим образом:

Если вы встретили сообщение Ooops , то значит, что одно или все ваши решения оказались не верны. Если же вы уверены в своем решении, то проверьте корректность функции check_solution() .

Генерация новых пазлов

Напишите функцию generate_sudoku(N) , которая создает новый судоку, заполненный на N элементов:

Пример использования функции:

Приложение

Вы заметили, что второй пазл решается дольше остальных?

На моей машине результат получился таким (от запуска к запуску вы будете получать разные результаты):

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

Давайте попробуем воспользоватся модулем threading, чтобы каждый пазл решался в отдельном потоке:

Из результатов видно, что решение для puzzle3 мы получили раньше чем для puzzle2 , но тем не менее они не были решены параллельно, как можно было бы подумать, и связано это с таким понятием как GIL.

Чтобы решать пазлы параллельно (за исключением разных если) мы можем воспользоваться модулем multiprocessing:

Решение Судоку

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

#4 Нейронные сети для начинающих. Sudoku Solver. Судоку. Часть 1

Предыстория: одним зимним вечером, а скорее ночью, мне пришла в голову интересная идея. Почему бы не попробовать автоматизировать с помощью компьютерного зрения решение одной классической головоломки с числами, а если быть точнее — судоку. Дело в том, что мой дедушка — большой любитель разных кроссвордов, судоку и т. д. Зная это, я подумал, что было бы неплохо попробовать как-нибудь автоматизировать эту задачу. Конечно, до задачи автоматизации решения кроссвордов мне ещё далеко, но вот с задачей решения судоку, у которого есть чёткий алгоритм, можно поэкспериментировать.

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

Но перед всем этим я советую вам прочитать мои предыдущие статьи из серии «Нейронные сети для начинающих». Там их уже целых три:

• #1 Нейронные сети для начинающих. Решение задачи классификации Ирисов Фишера
• #2 Нейронные сети для начинающих. NumPy. MatplotLib. Операции с изображениями в OpenCV
• #3 Нейронные сети для начинающих. Работа с изображениями в OpenCV. Алгоритм Canny Edge Detector

▍ Немного теории

А как судоку появилась?

Хорошо, а что там с правилами игры? Давайте разберёмся:

Игровое поле представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые подсказками. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз. Сложность судоку зависит от количества изначально заполненных клеток и от методов, которые нужно применять для её решения. Самые простые решаются дедуктивно: всегда есть хотя бы одна клетка, куда подходит только одно число. Некоторые головоломки можно решить за несколько минут, на другие можно потратить часы.

Правильно составленная головоломка имеет только одно решение. Тем не менее, на некоторых сайтах в интернете под видом усложнённых головоломок пользователю предлагаются варианты судоку с несколькими вариантами решения, а также с ветвлениями самого хода решения.

Как я понял, задача обобщённого судоку на поле N 2 * N 2 является NP-полной, так как к ней сводится задача о заполнении латинского квадрата.

Количество различных судоку классического размера 9×9 с однозначным решением равно 6670903752021073000000 (последовательность A107739 в OEIS) — данные взяты из Википедии, или примерно 6.67 х 10 21 . Однако если считать одинаковыми те судоку, которые получаются друг из друга с помощью поворотов, отражений и перенумерации, то это количество уменьшается до 5 472 730 538 (последовательность A107739 в OEIS).

Долгое время оставался открытым вопрос о минимальном количестве подсказок, необходимых для решения судоку. В частности, не было известно, существует ли однозначно решаемый судоку с 16 подсказками. Проект распределённых вычислений Sudoku@vtaiwan на платформе BOINC занимался поиском такого. В январе 2012 года появилось доказательство того, что однозначно решаемых судоку с 16 подсказками не существует.

Итак, мы выяснили, что такое судоку и что существует по сути только 2 правила при решении этой головоломки:

1. Игровое поле можно заполнять только цифрами от 1 до 9. Существуют виды судоку, которые решают буквами или символами, но это совершенно отдельные игры со своими правилами и стратегией.
2. Цифру можно записывать лишь в том случае, если она не будет повторяться в строке, столбце и малом квадрате 3 х 3, в которых расположена пустая ячейка.

Выберите одну из фигур, в которой не заполнено меньше всего ячеек. Положим, левый центральный квадрат. Там нет цифр 1, 2 и 8.

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

Остаются только две клетки в верхней строке малого квадрата. Но 1 не может находиться в правой ячейке, поскольку уже есть во всём столбце. Поэтому ставим туда 8. Получается, для единицы доступно только одно место:

Рассмотрите следующую фигуру. Например, левую нижнюю, где не хватает трёх цифр — 7, 8 и 9. Теперь расставляем цифры в допустимые для них ячейки.

Берём 7. Она не должна стоять ни в первом, ни во втором столбце, поскольку в каждом из них уже есть семёрка. Значит, эту цифру можно вписать только в третий столбец.

Переходим к 8. Она не может находиться во втором столбце, потому что уже стоит в нём. Соответственно, единственное допустимое для этой цифры место — первый столбец.

Цифру 9 по остаточному принципу ставим в единственную свободную ячейку — в центральном втором столбце:

Пример выше взят отсюда, там же можно посмотреть другие примеры решения судоку.

▍ Шаг 1. Начинаем работу

Разобравшись с основной историей и теорией этой потрясающей по своей сути головоломки, приступим к работе над её решением с точки зрения кода.

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

Для себя я выработал следующий алгоритм работы с изображениями:

1. Предварительная обработка.
2. Нахождение контуров.
3. Нахождение поля судоку.
4. Классификация цифр или банальный поиск их на игровом поле.
5. Поиск решения судоку.
6. Наложение решения на изначальное изображение.

И вот что находится по этому пути:

Далее перейдём к подготовке изображения (смотрите комментарии к коду), но перед этим импортируем библиотеки и файлы:

Как видим, функция возвращает нам изображение, которое мы можем вывести следующим кодом:

Интересно, что выведет весь это код? Многие функции, если что, мы написали заранее и по факту не совсем используем, но всё же они нам понадобятся в будущем. А вот что он выведет:

И это всё? Ну пока что да, но давайте всё же продолжим.

А что же у нас за imgBlank? Давайте их заменим на наше img:

Интересный, но ожидаемый результат. Давайте продолжим!

Вернёмся к изначальному коду:

У нас уже есть изображение, пропущенное через Treshold. Вставим его на вторую позицию:

И вот что получим:

Как мы видим, теперь у нас есть только контуры объектов. Это нам и нужно — нам необходимо видеть цифры и границы поля. Давайте пойдём дальше!

▍ Шаг 2. Поиск контуров

Здесь мы будем искать контуры нашего поля. Для этого напишем ещё немного букв, т. е. кода. Но для начала советую почитать про поиск контуров в OpenCV.

Теперь код (смотрите комментарии, там я постарался объяснить что происходит):

Зачем в строчке в конце стоит [-2:]:

Можно посмотреть здесь или ниже:

Теперь возьмём переменную imgContours, в которой у нас хранится изображение с обрисованными контурами, и подставим в наш вывод вместо imgBlank:

После запуска мы получим следующую картинку с уже найденным нами контуром:

Замечание для людей, которые спросят: а почему не отображается внутренний контур? Отвечу: потому что мы специально выделяем его, чтобы «отбросить». Это можно проиллюстрировать на следующем примерах:

Как мы видим, не всегда у нас есть «чистое изображение» для работы, поэтому мы и «отсекаем» внешние контуры. Продолжим!

▍ Шаг 3. Поиск самого большого контура и использование его в качестве поля для судоку

Для этого всего нам необходимо будет написать две функции, которые помогут нам в этом.

Теперь давайте напишем функцию для переупорядочивания точек для искажения перспективы. Поясняю: мы не знаем позиции точек, которые мы получаем из переменной biggest, т. е. мы не знаем, какая точка сверху, какая снизу и т. д. Именно для понимания этого мы и напишем сейчас функцию reorder():

Суть работы функции вы можете увидеть ниже:

Теперь запишем функцию в основном файле:

Нам остаётся заменить imgBlank в нашем выводе на imgBigContours:

И вот что мы получим:

Разберёмся с этой частью:

Здесь «приближаем» наше поле, и если мы закомментируем последнюю строчку, предварительно вставив переменную imgWarpColored в наш код вывода:

Мы получим следующий результат (картинка будет в цвете):

А если раскомментируем, то получим следующие (картинка в оттенках серого):

▍ Шаг 4. Найдём на изображении каждую цифру

Для этого нам понадобится на imgWarpColored выделить каждый квадрат и предсказать там цифру (если она там есть).

Для данной задачи я обучил нейронную сеть на открытых данных MNIST. О том, как я обучал и как буду дорабатывать этот проект, я выпущу отдельную статью. Пока лишь могу показать скриншоты с кодом и получившейся точностью модели (она не сильно велика, порядка 0.7).

Итак, вернёмся к коду. Нам потребуется функция splitBoxes(), чтобы разбить imgWarpColored на 81 ячейку (мы производим сплит по горизонтали и вертикали):

Давайте посмотрим, как вырезались наши ячейки. Для этого нам потребуется написать:

И вот что мы получим:

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

Теперь нам нужно проинициализировать модель. Для этого мы напишем простенькую функцию загрузки модели (у меня модель называется mnist.h5):

Выше мы импортируем модуль «load_model» из tensorflow.keras.models (это может занять некоторое время, не пугайтесь).

Далее напишем функцию предсказания:

И вот что появится в итоге:

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

Как видим из изображений выше, результаты схожи. На этом моменте я столкнулся с проблемой, о которой писал ранее, а именно проблемой с моделью, поэтому я хотел бы взять для себя время на исправление этого недостатка и на этом закончить статью. В следующей статье мы допишем наш проект по распознаванию и решению судоку в реальном времени. А пока хотел бы у вас спросить, как улучшить модель распознавания чисел? Пишите в комментариях, я обязательно прочту и мы вместе доведём этот проект до хорошего результата!

А пока все файлы, которые есть на данный момент, вы можете найти на моём GitHub.