Составив круг статей по методам решения проблем на примерах для задач судоку, я в очередной раз решил пополнить свои знания в этой части, ознакомившись с тем, как развязывает подобного рода проблемы научный мир. Не найдя в интернете ничего более подходящего, я остановился на статье: Анализ игры "Судоку"
http://www.slideshare.net/msucsai/hz-5391511#14457776534921&fbinitialized
30 марта 2010 Сапрунов
Спецсеминар "Искусственный Интеллект" кафедры АЯ ВМК МГУ
Сначала идет описание приемов, которые я в своих статьях представил как обычные способы обработки рабочей таблицы. Рабочая таблица, напомню, строится первоначальным заполнением пустых клеток числами 123456789 и последующим "вычеркиванием", т.е. удалением, лишних цифр. Вот этим удалением, расписанным в развернутом виде, и завершается основной материал упомянутой статьи. Объяснения сопровождаются слайдами весьма неважного качества, но рассмотреть их все же возможно. А в остальном изложение построено четко и логично, и я привожу его здесь без слайдов, полагая, что слайды вовсе не обязательны для тех решателей судоку, которые сочтут для себя полезным прочесть данную мою статью, и в то же время материал Супрунова позволит мне напомнить в сжатом виде то, о чем уже говорилось в нескольких моих статьях. Материал Супрунова я привожу не в дословном виде и не в том порядке, как в его статье.
Приёмы решения судоку, упрощающие дерево поиска:
– Одиночки
– Скрытые одиночки
– Запертый кандидат
– Открытые пары (тройки, четвёрки)
– Скрытые пары(тройки, четвёрки)
– X-wing
1. Одиночки. Метод заключается в отыскании в таблице одиночек, т.е. ячеек, в которых возможна только одна цифра и никакая другая. Вписываем её и исключаем её из других клеток этой строки, таблицы и блока.
2. Скрытые одиночки. Цифра 4 в зелёном блоке на слайде есть только в одной клетке.
3. Запертый кандидат. В пределах блока цифра только в одной строке. Из других блоков исключаем.
4. Открытые пары. Если две ячейки в группе (строке, столбце, блоке) содержат идентичную пару кандидатов и ничего более, то никакие другие ячейки этой группы не могут иметь значения этой пары.
5. Скрытые пары. Если в двух ячейках в группе (строке, столбце, блоке) содержат кандидаты, среди которых идентичная пара, не встречающаяся ни в одной другой ячейке данного блока, то никакие другие ячейки этой группы не могут иметь значения этой пары.
6. X-wing. Если значение имеет только два возможных местоположения в какой-то строке (столбце), то оно обязательно должно быть назначено в одну из этих ячеек. Если же существует еще одна строка (столбец), где этот же кандидат также может быть только в двух ячейках и столбцы (строки) этих ячеек совпадают, то ни одна другая ячейка этих столбцов (строк) не может содержать данную цифру.
Похожие описания приемов решения судоку есть и на многих других сайтах.
Кроме этого, автор статьи сообщает, что задачи судоку решаются как задачи CSP:
"Множество переменных, Х1,Х2,...,Хn и множеством ограничений, C1,C2,...,Cm. Каждая Xi имеет непустую область определения Di (числа от 1 до 9) возможных значений.
Каждое Ci включает некоторое подмножество переменных и задаёт допустимые комбинации значений для этого подмножества. Состояние задачи - присваивание значений некоторым переменным.
Присваивание, которое не нарушает никаких ограничений, называется совместимым, или допустимым присваиванием.
Полным называется такое присваивание, в котором учавствует каждая переменная, а решением CSP задачи является полное присваивание, которое удовлетворяет всем ограничениям".
По части CSP я нашел следующее сообщение: http://www.dslib.net/mat-modelirovanie/ob-jeffektivnyh-algoritmah-dlja-zadachi-csp-i-ih-programmnoj-realizacii.html
"Мы будем использовать стандартные определения комбинаторной задачи, класса задач NP, сведения, полиномиальности и NP-полноты задачи, см. например [1, 56]. Данная работа относится к исследованию комбинаторной задачи CSP (От английского 'Constraint Satisfaction Problem', в немногочисленной русскоязычной литературе встречается также название 'Обобщенная выполнимость'). Цель данного направления — разработать эффективные универсальные алгоритмы для задач из класса NP. Задача CSP является лишь одной из многих известных NP-полных задач, однако в последнее десятилетие стало ясно, что она занимает особое место. Сведение задачи к NP-полной очень часто оказывается громоздким и искусственным. Преимущество задачи CSP состоит в том, что большинство комбинаторных задач может быть представлено в виде CSP просто и естественно. Многие комбинаторные задачи могут быть естественным образом охарактеризованы как подклассы задачи CSP. Теория задачи CSP находит свое применение в таких областях как теория реляционных баз данных [43, 65], временная и пространственная логика [62], распознавание зрительных образов [52], автоматическое доказательство теорем [16], техническое проектирование [55], анализ языков программирования [54] и естественных языков [4], биоинформатика [45] и многих других".
Обещания по части CSP конечно впечатляют. Но реально все заканчивается примерно так, как и в статье Сапрунова, имеющей – ни много, ни мало – некое отношение к спецсеминару "Искусственный Интеллект" кафедры АЯ ВМК МГУ:
"Методы решения таких задач:
Поиск в ширину (n!*dn ветвей дерева)
Поиск в глубину
Поиск в глубину может быть усовершенствован:
Эвристики (Minimum Remaining Values - MRV)
Предварительная проверка (распространение ограничений)
Хронологический поиск с возвратами (при неудаче возврат к предыдущей переменной, либо к переменной из конфликтного множества. Его определяет предварительная проверка)".
Вот так-то, как и во многих прочих статьях: куча довольно общих подходов и соображений относительно необходимости учета ограничений и, собственно, жалкая кучка этих простейших ограничений применительно к задачам судоку. А далее – "метод тыка" или перебора вариантов: "Хронологический поиск с возвратами (при неудаче возврат к предыдущей переменной, либо к переменной из конфликтного множества...)".
Как-то, при всех сверхумных рассуждениях и построениях, наука не доросла до того, чтобы установить все возможные ограничения, позволяющие устранить или сократить перебор вариантов в решении задач судоку.
Поискал, есть ли что-то по части ограничений для судоку в интернете. Все же нашлось, но не густо: статья "Таблица комбинаций" http://www.playsudoku.ru/table.html
Там приводятся допустимые комбинации цифр для двух, трех и более ячеек судоку. Для обработки таблиц вручную использование подобных комбинаций накладно, хотя и возможно, а для машинной обработки – вполне приемлемый подход для учета дополнительных ограничений, сокращающий слепой перебор.
Ограничения на возможное расположение цифр в таблице, почему-то до сих пор наукой видимо не выявленные, обусловлены самой структурой таблиц судоку. Большинство таблиц для супер сложных судоку, в т.ч. "самая сложная в мире" таблица Арто Инкала, строится по определенному повторяющемуся принципу. Для его представления условимся, что нумерация блоков "квадратиков" таблицы идет слева-направо и сверху-вниз. Тогда для первых трех блоков можем записать:
Первый блок (х1+х2)+х3; (х4+х5)+х6; (х7+х8)+х9
Второй блок (х7+х8)+х6; (х1+х2)+х9; (х4+х5)+х3
Третий блок (х4+х5)+х9; (х7+х8)+х3; (х1+х2)+х6
То есть, пара (х1+х2) переходит из первой строки блока 1 во вторую строку блока 2, затем в третью строку блока 3. Пары (х4+х5) и (х7+х8) из второй и третьей строки блока 1 двигаются синхронно с парой (х1+х2), если это движение представить как своего рода вращение барабана. При этом три одиночки х3, х6 и х9 вращаются асинхронно трем парам. Вращение по столбцам (колонкам) происходит аналогично: чтобы это представить, достаточно повернуть таблицу на 90 градусов, сделав столбцы строками. Правда, взаимное расположение цифр в парах и одиночек и пар не упорядочено. Так, запись (х1+х2)+х3 отвечает также вариантам (х2+х1)+х3, х3+(х1+х2) и х3+(х2+х1). Кроме того, вращение может происходить и в другом, кроме описанного, порядке: пара (х1+х2) переходит из первой строки блока –1 в третью строку блока 2, затем во вторую строку блока 3 и т.п. для остальных пар. Тем не менее, описанное расположение является ограничением на взаимное расположение цифр, которое, в частности, можно учесть и Таблицей комбинаций, о которой выше шла речь.
Для тройки цифр х3+х6+х6, т.е. для наших трех одиночек установлены следующие ограничения по сумме цифр:
Для пар (х1+х2), (х4+х5) и (х7+х8) также найдены подобные ограничения:
Но реально, допустимых комбинаций цифр в судоку оказывается меньше, чем представляется на первый взгляд. В особенности если учесть, что сочетания вида (х1+х2)+х3 – см. выше – тоже представляется неупорядоченными лишь на первый взгляд. На самом же деле, их порядок предопределен "законами", предписанными структурой таблицы: законом расположения цифр по строкам и законом расположения цифр по столбцам.
Что касается других, кроме вышеприведенных, допустимых в судоку комбинаций по сумме цифр, то их можно найти в упомянутой Таблице комбинаций.
Интересный, на мой взгляд, материал о судоку я нашел в статье С.Л. Василенко "Числовая гармония Судоку" www.sciteclibrary.ru/texsts/rus/stat/st4689.pdf
Приведу пару выдержек:
"Часто говорят, что для заполнения Судоку не нужно никакой математики. Достаточно иметь навыки аргументации и логики. Отчасти это так. Но сама по себе тема и методы синтеза подобных числовых структур выходят далеко за пределы только логики. Они могут распространяться и на 4-мерное векторное пространство, а решения, удовлетворяющие некоторым дополнительным условиям, могут быть найдены с помощью закономерностей проективной и аффинной геометрии, теории кодирования [5], теории графов [6, 7], в частности метода раскрашивания карт, целочисленного программирования [8] и др.
В работе [9] показано, что эти головоломки могут быть сформулированы и решены в виде линейной системы уравнений. Как математическая задача.
Судоку представлена в работах [10–14] и естественно связана с матричным анализом [15].
... Неразгаданные тайны. Даже простая стандартная форма Судоку таит в себе неизвестности, что вызвало несколько проблем математической природы, пока не решенных.
1) Самый элементарный вопрос: сколько различных вариантов? – По расчетам Б. Фельгенхауэра с использованием компьютерного алгоритма и учетом определенной эквивалентности некоторых задач, количество возможных комбинаций в Судоку 9×9 составляет 6 670 903 752 021 072 936 960 ≈ 6,7∙1021 [18]. За вычетом разных групп симметрии остается 2 297 902 829 591 040 ≈ 2,3∙1015 значимо различных сеток [19]. В то же время пока неизвестно формальное доказательство данного положения без применения компьютера.
2) Неизвестным является и минимальное количество изначально заполненных клеток, при котором существует единственное решение. Эта задача до сих пор остается открытой математической проблемой в комбинаторике. Гордон Ройл, автор книги по алгебраической теории графов, собрал коллекцию из более 36 тыс. различных головоломок Судоку с 17 ключами [20]. Никто еще не нашел ни одного примера, головоломки Судоку с 16 начальными числами, что наводит на мысль-ответ по нашему вопросу: все-таки 17. Но теоретического доказательства этому нет. А потому остаётся ещё один открытый в математике вопрос".
Что касается аффинной геометрии, теории графов и т.п., то каких-либо указаний на то, что эти подходы позволяют полностью устранить перебор в сложных задачах судоку, я не нашел. Аналогично и с матричным анализом. Но когда я смотрю на таблицу судоку, то в ней просматриваются некоторые закономерности, которые, как мне представляется, возможно обобщить статистическим путем: вернее, путем построения аппроксимирующих уравнений. Аппроксимирующими уравнениями я занимался, в практическом плане, несколько десятков лет, так что мог бы попытаться что-то в этом плане извлечь и из таблиц судоку, но оставляю эту идею более молодым.
Относительно решения задачи судоку в виде линейной системы уравнений, я действительно нашел такой подход, описанный в одной из статей в интернете. Но он годится лишь для задач, не требующих перебора вариантов с подстановкой предполагаемых цифр. Там же где требуется перебор, либо не удается построить полную систему уравнений, либо нужно знать для этого точную структуру таблицы (расположение пар и одиночек), а это уже почти то же, что решить задачу судоку другим путем, потому что если известна структура таблицы, то процесс заполнения ее пустых ячеек становится тривиальным.
На нескольких сайтах в интернете я нашел переписываемые друг у друга сообщения о том, что Торожкай и Эркси-Раваз предложили универсальный аналоговый алгоритм, который абсолютно детерминирован (не использует предположение или перебор) и всегда находит правильное решение задачи, причем довольно быстро. Конкретную информацию о сути этого метода мне найти не удалось. Но приведенные в статьях слова Торожкая свидетельствуют о том, что он использовал не детерминированный, а вероятностный подход, с оценкой вероятностей машинным способом или подсчетом их с карандашом.
О применимости вероятностного подхода в решении задач судоку говорил и я в своих статьях.