В проекте 1 искусственного интеллекта Nanodegree мы используем такие методы, как распространение ограничений и поиск в глубину, для решения головоломок судоку. Я предполагаю, что каждый, кто читает этот пост, понимает правила судоку - если нет, не волнуйтесь, я не был полностью знаком с игрой до проекта. Большая часть этого кода для проекта была предоставлена Udacity, поэтому в этот пост я не буду включать фрагменты кода. Весь мой код можно найти на GitHub здесь.
Настройка и кодирование платы
Первая задача проекта - назначить переменные и написать функции, которые могут кодировать плату. Короче говоря, цель состоит в том, чтобы написать функцию, которая может принимать ввод из 81 символа и сохранять значение столбца / строки и поля в словаре Python. Например,
Input: ..3.2.6..9..3.5..1..18.64….81.29..7.8..67.82.26.95..8..2.3..9..5.1.3..,
Output:
{'A1':'.','A2':'.','A3':'3','A4':'.','A5':'2',....}
К счастью, в проекте предусмотрена функция, которая отображает доску судоку, как только мы ее правильно закодируем.
. . 3 |. 2 . |6 . .
9 . . |3 . 5 |. . 1
. . 1 |8 . 6 |4 . .
------+------+------
. . 8 |1 . 2 |9 . .
7 . . |. . . |. . 8
. . 6 |7 . 8 |2 . .
------+------+------
. . 2 |6 . 9 |5 . .
8 . . |2 . 3 |. . 9
. . 5 |. 1 . |3 . .Следующим шагом является присвоение значения полям, имеющим нечисловое значение. В частности, замените все поля, содержащие "." На "123456789".
Ограничение распространения
Распространение ограничений - это метод удовлетворения ограничений, который сокращает пространство поиска за счет использования локальных ограничений. Как упоминалось в первом абзаце, мы собираемся реализовать поиск в глубину, поэтому уменьшение размера поиска очень важно для быстрого и эффективного решения головоломок. В этом проекте судоку каждая коробка имеет ограничения (я думаю, что это правила), которые могут привести нас к решенной головоломке судоку.
Ограничение: устранение
Согласно правилу судоку, поле не может иметь то же значение, что и одно из его сверстников (другие квадраты в его квадрате, строке и столбце 3x3). Мы можем начать использовать это правило в качестве ограничения и исключить возможности с помощью полей со значением «123456789».
Написание функции для этого ограничения мгновенно уменьшает значения на доске (см. Ниже).
Input:
. . 3 |. 2 . |6 . .
9 . . |3 . 5 |. . 1
. . 1 |8 . 6 |4 . .
------+------+------
. . 8 |1 . 2 |9 . .
7 . . |. . . |. . 8
. . 6 |7 . 8 |2 . .
------+------+------
. . 2 |6 . 9 |5 . .
8 . . |2 . 3 |. . 9
. . 5 |. 1 . |3 . .
Output:
45 4578 3 | 49 2 147 | 6 5789 57
9 24678 47 | 3 47 5 | 78 278 1
25 257 1 | 8 79 6 | 4 23579 2357
---------------------+---------------------+---------------------
345 345 8 | 1 3456 2 | 9 34567 34567
7 123459 49 | 459 34569 4 | 1 13456 8
1345 13459 6 | 7 3459 8 | 2 1345 345
---------------------+---------------------+---------------------
134 1347 2 | 6 478 9 | 5 1478 47
8 1467 47 | 2 457 3 | 17 1467 9
46 4679 5 | 4 1 47 | 3 24678 2467Очевидно, что этот метод не сводит значения всех ящиков к единственной возможности, поэтому мы должны использовать другие стратегии.
Ограничение: единственный выбор
Чтобы уменьшить возможные комбинации каждого блока, мы используем только стратегию выбора в качестве ограничения. Эта стратегия работает путем поиска ящиков с возможной комбинацией, которые не видны другим узлам.
Третье поле в третьем столбце содержит [1,4,7]. Наблюдая за другими квадратами в квадрате 3x3, вы можете заметить, что ни один из них не имеет возможности 1. Следовательно, третье поле в столбце 3 должно быть равно 1.
Теперь мы можем использовать исключение и итеративно использовать только выбор для решения головоломки судоку. Чтобы быстро и эффективно решить головоломку, мы применяем поиск в глубину.
Поиск
В этом проекте мы использовали поиск в глубину, чтобы решить головоломку судоку. Этот алгоритм поиска использует уменьшенный размер головоломки, возвращаемой методом исключения и единственного выбора, а затем перебором последних возможностей.
Udacity предоставляет отличные изображения для визуализации поиска в глубину. С помощью этой техники поиска мы, по сути, перебираем все ограниченные возможности решения головоломки судоку (начиная с ящиков с наименьшим количеством возможностей).
Ограничение: Обнаженные близнецы
Одним из требований проекта 1 было реализовать стратегию судоку «голые близнецы». Более конкретно, когда блок имеет две возможные комбинации и разделяет те же возможные комбинации с другим одноранговым узлом (отсюда голые близнецы), любое из этих значений комбинации может быть удалено из других одноранговых узлов. В приведенной ниже головоломке два партнера имеют и разделяют две одинаковые возможные комбинации [2,3].
Стратегия «голых близнецов» позволяет нам исключить 2 и 3 из других сверстников в этой колонке.
Вывод
Этот проект был приятным и довольно простым. Было приятно, что Udacity предоставил несколько обучающих колес (некоторые полные функции были предоставлены заранее). Если вы хотите ознакомиться с исходным кодом, посетите мою страницу на Github здесь.
