Судоку, также называемое Number Place, представляет собой логическую комбинаторную головоломку с расстановкой чисел. Цель состоит в том, чтобы заполнить сетку 9x9 цифрами, чтобы каждый столбец, каждая строка и каждая из девяти подсеток 3x3, составляющих сетку, содержали все цифры от 1 до 9.
В этом руководстве мы собираемся разработать решатель судоку на Java с помощью Eclipse. Мы будем использовать рекурсивный подход BackTracking. Простой, почти наивный подход. В следующем уроке вы научитесь применять более умный подход.
Обратите внимание, что вы также можете посмотреть это руководство в видео на YouTube:
Проектирование доски
Первый шаг - спроектировать доску, представляющую собой сетку судоку. Это будет двумерный массив целых чисел. Числа будут храниться от 1 до 9. Ноль будет указывать на то, что ячейка сетки не назначена.
В конструкторе класса Sudoku мы скопируем 2D-массив целых чисел, введенный в параметрах свойства 2D-массива нашего класса:
Проверка правил судоку
Чтобы сетка судоку считалась решенной, она должна соответствовать некоторым ограничениям:
- Каждая строка, составляющая сетку, должна содержать все цифры от 1 до 9.
- Каждый столбец, составляющий сетку, должен содержать все цифры от 1 до 9.
- Каждые девять подсеток 3x3, составляющие сетку, должны содержать все цифры от 1 до 9.
Итак, после каждого шага нашего алгоритма обратного отслеживания мы будем проверять, остается ли сетка действительной или нет. Если да, мы продолжим пробовать другие назначения для других ячеек сетки. В противном случае мы попробуем новое значение для текущей ячейки.
Реализация проверки этих 3-х правил сделана так:
Реализация алгоритма обратного отслеживания
Как поясняют в Википедии:
Отслеживание с возвратом - это общий алгоритм для поиска всех (или некоторых) решений некоторых вычислительных проблем, в частности проблем удовлетворения ограничений, который постепенно создает кандидатов для решений и оставляет кандидата ( backtracks ), как только он определит, что кандидат не может быть доработан до действительного решения.
В нашем классе Sudoku мы создаем метод solution для реализации этого алгоритма. В нашей реализации мы остановим алгоритм после того, как будет найдено одно решение. Это хорошо, потому что правильная сетка судоку имеет уникальное решение.
Мы выполняем итерацию по сетке, а затем пытаемся присвоить значение пустой ячейке. Если сетка правильная после этого назначения, мы рекурсивно вызываем метод resolve и возвращаем true. В противном случае мы возвращаем false , а затем алгоритм может попробовать другое назначение для текущей ячейки.
Этот рекурсивный подход дает нам следующий полный код для нашего класса судоку:
В конце занятия вы должны были отметить наличие метода display, который используется для отображения сетки на экране в режиме консоли.
Наш решатель судоку в действии!
Последний шаг - запустить наш Решатель Судоку в действии!
Мы вводим сетку для решения, а затем вызываем метод решения в основной точке входа нашего класса. Как только разрешение будет выполнено, на экране должен появиться следующий результат с решенной сеткой:
Идти дальше
Вот и все для этого урока. В следующем уроке вы узнаете, как создать более умный решатель судоку с помощью алгоритма танцующей ссылки.
В ожидании этого урока, почему бы не поиграть в судоку напрямую на Android-устройстве? Вы можете бесплатно попробовать это приложение для Android судоку в магазине Google Play:
Если у вас есть вопросы по этому руководству, не стесняйтесь использовать раздел комментариев ниже.
Если вы хотите открыть для себя книги по изучению программирования на Java, я советую вам прочитать следующую статью с моей подборкой из 6 лучших книг по программированию на Java:
Другие статьи о Java, которые могут вам понравиться
Дорожная карта для разработчиков Java
10 вещей, которые должны изучить Java и веб-разработчики
10 инструментов тестирования, которые следует изучить разработчикам Java. Знайте
5 фреймворков, которые должны изучить Java-разработчики
5 курсов по изучению больших данных и Apache Spark на Java
10 курсов по DevOps для разработчиков Java
10 книг, которые должен прочитать каждый Java-программист
10 инструментов, которые Java-разработчики используют в своей повседневной работе
10 советов, как стать лучшим Java-разработчиком
Хотите большего? Вот и другие наши лучшие статьи для чтения
