Название судоку происходит из Японии и переводится как «число» (Су) и «сингл» (Доку). Однако, хотя название указывает на японское наследие, создателем головоломки в основном считается Леонард Эйлер; очень известный швейцарский математик 18 века. С тех пор головоломка получила широкое международное распространение, даже среди компьютеров!

Так как же играть в судоку? Для начала головоломка представлена ​​в виде доски (например, крестики-нолики) из 81 квадрата, и, в зависимости от сложности головоломки, в ней есть несколько квадратов, заполненных числами, а остальные оставлены пустыми. Ниже вы можете увидеть доску головоломки судоку слева, которая не была решена, и ту же доску справа, которая была решена.

Чтобы решить головоломку, вам нужно заполнить пустые квадраты числами от 1 до 9. Уловка состоит в том, что каждый квадрат должен содержать значение, уникальное для этой строки, столбца и поля. Эти строки, столбцы и прямоугольники будут называться регионами. Ряд состоит из девяти квадратов слева направо, столбец состоит из девяти квадратов сверху вниз, а коробка состоит из девяти квадратов 3x3, равномерно распределенных по доске.

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

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

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

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

Ограничение распространения

Теперь, чтобы научить компьютер делать это, нам нужно использовать обычный метод искусственного интеллекта, который называется распространение ограничений. Проще говоря, это метод, который позволяет компьютеру двигаться к вероятному решению (распространять), следуя правилам некоторого пространства и возможных значений для каждой переменной (ограничений). В этом случае наши ограничения представляют собой квадраты, которые могут содержать только одно значение в диапазоне от 1 до 9 и должны быть уникальными для каждого региона.

Итак, как этот метод выглядит в действии? Что ж, давайте начнем с рассмотрения следующей доски судоку. Не волнуйтесь, эта головоломка довольно проста и даже проще для компьютера при использовании распространения ограничений.

Для начала мы хотели бы перечислить все возможные значения, которые может принимать каждый квадрат, чтобы мы могли сузить возможные варианты, а также найти «уже решенные» квадраты (т. Е. Квадраты, которые имеют только одно возможное значение). Основываясь на таблице ниже, вы можете видеть, что все возможные значения указаны для каждого квадрата, и что некоторые из них имеют только одно значение.

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

Например, давайте посмотрим на верхнее среднее поле, окрашенное в красный цвет на изображении ниже. Вы можете видеть, что мы почти решили эту область, но не совсем. Поскольку каждый квадрат в этом поле должен быть уникальным, мы знаем, что ни 2, 3, 5, 6 и 8 не являются возможными значениями для неразрешенных квадратов. Однако мы можем видеть, что значение 1 возможно только в верхнем правом квадрате этой области, в то время как каждый нерешенный квадрат в области содержит 4, 7 или 9.

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

Используя распространение ограничений, мы можем научить компьютер решать практически любую головоломку судоку, сосредоточившись на локальных ограничениях. Но вы, возможно, знаете по опыту, что бывают случаи, когда доска достигает застопоренного состояния, когда есть квадраты, которые могут принимать несколько значений. Возможно, наименьшее количество значений для любого нерешенного квадрата - два или более! Что ж, это будет случай, когда вы столкнетесь с голыми близнецами, что указывает на то, что есть несколько путей, из которых можно выбрать, когда вы на пути к величию (решение головоломки). Приступим к величию.

Поиск

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

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

Теперь BST состоит из корневого узла, от которого отходят два направления, а сами эти последующие точки могут иметь два ответвления от них, и так далее.

Теперь представьте, что узел A - это момент времени, когда мы должны принять одно из двух решений, которые в конечном итоге окажутся либо B, либо C. В судоку это та же проблема, что и столкновение с голыми близнецами (а?); вы должны выбрать один из двух путей, которые могут привести или не привести к правильному решению.

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

И кто знает, может быть, мы столкнемся с ДРУГОЙ партией голых близнецов (э-э…) после того, как сделаем выбор из 8 или 9, что приведет к другому набору возможностей и, следовательно, к другому набору ветвей в нашем дереве! Моделируя это как BST, мы можем заставить компьютер просматривать эти возможные решения, используя поиск в глубину, что в конечном итоге приведет нас к действительному решению.

Это интеллект?

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

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

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

Заворачивать

Мы рассмотрели, как распространение ограничений в сочетании с поиском в глубину BST так хорошо подходит для решения древней головоломки судоку, которая лучше информирует нас о том, как научить компьютер делать это самостоятельно. Если вы хотите узнать больше по этой теме, я настоятельно рекомендую вам прочитать Сообщение Питера Норвига, где он дает более глубокий взгляд на проблему с фрагментами кода. Вы также можете взглянуть на код, который я написал для решения этой проблемы для моей Udacity Artificial Intelligence Nanodegree, которую вы можете найти в моем репозитории GitHub.

Привет, я Грант! Я внештатный разработчик и писатель. Посетите мой сайт по адресу https://grantbartel.com. Ваше здоровье!