Этот проект был частью моего курса искусственного интеллекта. В этом проекте я реализовал некоторые расширения алгоритма судоку. Первое расширение будет реализацией метода naked twins
. Вторым будет модификация алгоритма для решения задачи diagonal sudoku
.
голые близнецы
Техника голых близнецов следующая. Рассмотрите следующую загадку и посмотрите на два выделенных прямоугольника, 'F3'
и 'I3'
.
Как мы видим, оба принадлежат одному и тому же столбцу и оба допускают значения 2 и 3. Теперь мы не знаем, какой из них имеет 2, а какой — 3, но мы знаем точно одно — значения 2 и 3 заблокированы в этих двух полях, поэтому никакое другое поле в той же единице (третьем столбце) не может содержать значения 2 или 3.
Таким образом, мы проходим по всем ящикам в одном и том же блоке и удаляем значения 2 и 3 из их возможных значений.
Как видите, мы удалили значения 2 и 3 из полей 'D3'
и 'E3'
. Это техника голых близнецов. В этом проекте вы напишете функцию, реализующую этот прием.
Диагональ судоку
Диагональная судоку похожа на обычную судоку, за исключением того, что среди двух основных диагоналей числа от 1 до 9 должны встречаться ровно один раз. В этом проекте вы будете изменять функции, которые мы написали в лекции (или вы можете написать свои собственные!), чтобы решать все диагональные судоку.
Обзор
В этом проекте я написал код для реализации двух расширений нашего решателя судоку.
- Первым будет реализация техники под названием «голые близнецы».
- Второй будет заключаться в изменении нашего существующего кода для решения диагональной судоку.
Цели состоят в том, чтобы реализовать функцию голых близнецов и написать агента ИИ, который будет решать игру Diagonal Sudoku.
инструкции
- С требованиями к этим проектам можно ознакомиться здесь.
- Клонируйте репозиторий.
Вопрос 1 (голые близнецы)
В: Как мы используем распространение ограничений для решения проблемы голых близнецов?
Сначала нужно перебрать все возможные единицы и выбрать первую единицу, длина значения которой равна 2, в качестве основного близнеца, а затем найти другие ячейки, для которых они имеют значение равным основному близнецу, у которого их идентификатор не совпадает, и сохранить их как возможного близнеца. Затем я просматриваю все возможные единицы и нахожу единицы, у которых есть цифры от основного близнеца, и они не являются возможными близнецами, затем заменяю основные цифры-близнецы их значением.
Распространение ограничений здесь было настолько ясным, так как мы ищем близнецов, а затем ограничиваем поиск их парами, затем для всех пар, у которых есть константа (длина их значения больше 2), мы удаляем цифры. также с помощью рекурсивных функций (search и reduce_puzzle) мы решили судоку.
Вопрос 2 (Диагональная судоку)
В: Как мы используем распространение ограничений для решения диагональной задачи судоку? Как и в старых ограничениях, здесь мы просто добавляем новые единицы ко всем единицам, что говорит о том, что среди двух основных диагоналей числа от 1 до 9 должны встречаться ровно один раз.