Хаос внутри судоку

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



    Этап 0. Формулировка задачи


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


    Этап 1. Формализация задачи


    Опишем математически, что такое корректно заполненное поле. У нас есть сетка размером 9x9, в каждой клетке может располагаться только одно число от 1 до 9. Было бы разумным ввести 81 целочисленную переменную, но вместо этого мы будем оперировать булевыми значениями. Это позволит использовать формальный логический подход.


    Введём множество image логических переменных, наделив их следующим смыслом: image в клетке image записано число image. Определение корректного поля в судоку диктует нам ряд ограничений, которые мы введём на множестве наших переменных.


    Для простоты сперва введём q-местный предикат image, истинный только в том случае, если ровно один из его параметров истинен. Вот его формальное описание:


    image


    С его помощью запишем 4 вида ограничений, описанных нами ранее:


    • в каждой клетке может находиться только одно из 9 чисел:

    image


    • в каждой строке каждое число встречается ровно 1 раз:

    image


    • в каждом столбце каждое число встречается ровно 1 раз:

    image


    • наиболее неприятный для описания случай — каждый из 9 блоков 3x3 содержит каждое число ровно 1 раз:

    image


    Если объединить все приведённые формулы, избавившись от кванторов, мы получим вот это:


    image
    image


    Данная формула имеет Конъюнктивную Нормальную Форму (поскольку предикат image тоже записан в КНФ), что является весьма удобным способом для программной обработки.


    У нас на руках есть общая формула, которая описывает все возможные поля судоку. На практике же в поле судоку есть несколько подсказок. Если в клетке image стоит число image, то мы знаем, что image. Помимо этого мы можем легко определить множество переменных, которые в этих условиях обязаны быть ложными. Подставим все эти величины и упростим каждый из дизъюнктов. Далее мы вправе удалить из формулы повторяющиеся дизъюнкты (если они появились) и заявить, что полученная функция (всё ещё в КНФ) полностью определяет наш расклад, а каждое решение уравнения image даёт нам уникальное решение исходной задачи. Так что, по большому счёту, мы свели судоку к классической задаче выполнимости из математической логики. Она является NP-полной, что в какой-то степени объясняет нам сложность исходной головоломки.


    Поправка

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


    Этап 2. Немного математического анализа


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


    Предположим, что есть формула, состоящая из N логических переменных image и M дизъюнктов. Введём матрицу image размера MxN, такую, что:


    • image=1, если m-й дизъюнкт содержит image;
    • image=-1, если m-й дизъюнкт содержит отрицание image;
    • image=0, если m-й дизъюнкт не содержит image.

    Далее введём вектор image такой, что image = {количество переменных в дизъюнкте с номером m}.
    И, в конце концов, каждому image поставим в соответствие вещественное число image. image это непрерывная величина, которая для image равна -1, а для image равна 1. В каком-то смысле image.


    Теперь можно разобраться, зачем всё это нужно. Каждому из M дизъюнктов поставим в соответствие функцию image, определённую следующим образом:


    image


    Эти функции хороши тем, что обращаются в 0 (если один из множителей равен нулю) image соответствующий им дизъюнкт с соответствующими значениями image является истинным. Более того, добавление множителей с image гарантирует, что каждая из функций принимает значения из отрезка image в области своего определения. Но интереснее будет сумма их квадратов:


    image


    Эта сумма примечательна тем, что обращается в нуль исключительно на тех векторах s, которые соответствуют решениям изначального уравнения на image. И все эти нули являются локальными минимумами нашей функции (в силу области значений).


    Этап 3. Система дифференциальных уравнений


    Уравнение, несмотря на кажущуюся простоту записи, по факту оказывается весьма неприятным. Это полином большой степени от очень большого числа аргументов. Можно даже не пытаться искать его минимум аналитически.


    Давайте сделаем несколько добавлений:


    • представим каждый image как функцию image;
    • введём ещё ряд функций image;
    • вместо нашей image будем рассматривать image

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


    image


    ∇ в этой записи — оператор градиента.


    image


    Первое уравнение явно намекает нам на метод сопряжённых градиентов для поиска экстремумов.
    Со вторым немного хитрее, его я оставлю на совести авторов. Если вкратце — оно нужно для того, чтобы система быстрее сходилась к решению. Я сам не проверял, является ли это правдой.


    Уравнение на image можно переписать в явном виде, продифференцировав V:


    image


    image


    Начальные условия в точке 0 берутся произвольными. Ну а решение мы в итоге получаем по такой формуле: image


    Поправка

    Высказывание о произвольности начальных условий, вообще говоря, ложно. Авторы метода утверждают, что на множестве начальных условий нулевой меры ответ найти не получится. Но, поскольку множество "маленькое", на практике его можно игнорировать.


    Этап 4. Наконец-то численное решение


    Одним из самый простых и удобных способов решать системы обыкновенных дифференциальных уравнений является метод Рунге-Кутты. Нами будет использован вариант метода, носящий фамилии Кэша-Карпа. Сейчас я коротко о нём расскажу.


    Итак, пусть у нас есть уравнение image. x в списке параметров мы опускаем, поскольку в наших уравнениях значения производных image и image не зависят явно от t. Нам же проще.


    Считаем, что задано начальное условие image, а требуется нам найти значение image.
    Для поиска ответа мы построим последовательность image и будем вычислять значения image.


    image и image нам известны, считаем их базой индукции. Далее, пусть мы находимся на шаге n<N, обозначим image. Будем искать image, исходя из следующей формулы:


    image, в которой последовательность image находится как:


    image


    Числа image, image и image являются фиксированными константами, от которых сильно зависит точность метода (в каноничном методе есть ещё константы image, но в нашем случае они попросту не нужны).
    Вместе набор этих коэффициентов называется "таблицей Бутчера":


    image


    Для метода Кэша-Карпа у нас есть такая таблица:


    image


    Здесь у нас два вектора b. Если использовать первый из них, то на каждом шаге ошибка вычисления оценивается как image. А если взять второй вектор b, то оценка погрешности будет image. Посчитав менее точное значение image, мы можем эвристически оценить абсолютную ошибку на шаге как image (разница решений 4-го и 5-го порядков). И в случае, если ошибка нас не устраивает, мы можем заменить текущий шаг h на другое значение и пересчитать текущую итерацию. В частности, возможно 2 варианта:


    • слишком большая ошибка — уменьшаем шаг, запускаем итерацию с начала;
    • слишком маленькая ошибка — увеличиваем шаг, запускаем следующую итерацию (тем самым уменьшаем суммарное время вычислений).

    Остановить же процесс поиска можно тогда, когда все вычисленные image по модулю станут мало отличаться от единицы (разницы в 0.1 вполне достаточно).


    Заключение


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


    Работает ли всё выше описанное на практике? Авторы кодом не поделились, так что мне пришлось написать свой.


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


    Если вас действительно заинтересовала эта тема, то настоятельно советую почитать оригинал. Я затронул не весь материал, рассматриваемый авторами метода. И спасибо, что дочитали до конца!


    Ссылки:


    1. оригинальная публикация на тему решения судоку
    2. общий метод решения задачи выполнимости
    3. метод Кэша-Карпа
    4. моя реализация на гитхабе (Java)
    Share post

    Comments 26

    • UFO just landed and posted this here
        0
        Быстрей ли вышло, чем считать перебором?
          0

          Сложно сказать с уверенностью.
          Для простых судоку время слишком мало, чтобы заметить невооружённым глазом. Для сложных перебор находит решение намного быстрее.

          0
          С чего это судоку решается перебором? Она решается наложением ограничений.
            +2

            В сложных судоку всегда наступает момент, когда ограничения не позволяют сделать более ни одного хода. Для решения таких судоку приходится перебирать варианты. То есть метод смешанный, ограничения + немного перебора.

            • UFO just landed and posted this here
                +1

                Я тоже писал разные решатели судоку. :) И таки да, бывает, что ограничения не работают, а правильное решение все равно единственное. Пару лет назад даже на эту тему спорил с учеником-студентом и где-то даже можно откапать пример такого судоку.

                  +1
                  Это значит, что просто не все ограничения использовались.
                    0

                    Немного повспоминал. Тут вопрос лишь в сложности этих ограничений. Если рассматривать лишь базовые: «здесь может быть только X» и «X может быть только здесь», то перебор нужен. Если вводить более сложные, то да, можно без перебора. Пример более сложного:


                    8 _ _ _ _ _ _ _ _
                    _ _ 3 6 _ _ _ _ _
                    _ 7 _ _ 9 _ 2 _ _
                    _ 5 _ _ _ 7 _ _ _
                    _ _ _ _ 4 5 7 _ _
                    _ _ _ 1 _ _ _ 3 _
                    _ _ 1 _ _ _ _ 6 8
                    _ _ 8 5 _ _ _ 1 _
                    _ 9 _ _ _ _ 4 _ _
                0
                Уверен, что если наступает такой момент значит берем любую клетку и можем там поставить любое число из множества оставшихся доступных — оно подойдет в любом случае и это будет одним из вариантов решения поля.
                  +1

                  Это не является правдой. Хотя скорее так — нужно уточнить понятие "доступных".
                  В этапе 1 я перечислил в сумме 4x9x9 ограничений (в нумерованных пунктах). По факту это есть классические правила судоку. Если "доступностью" считать логическую выполнимость всех этих ограничений по отдельности, то уж точно не каждый ход приведёт к правильному решению.
                  Пример с судоку приводить не буду, так как для этого нужно сидеть и решать, а вот аналогичный с логическими формулами — легко:
                  1) (a || b) && (!a || b)
                  2) (a || b) && (!a || !b)
                  Обе формулы выполнимы по отдельности при "a == true", но вот их конъюнкция при этом будет ложной.


                  P.S. естественно именно такой конфигурации, как в моём примере, в реальных судоку не возникнет. Ситуация неоднозначиности на практике бывает тогда, когда неизвестных как минимум несколько десятков.

              0
              Мама дорогая!
                0
                Спасибо!

                А какие есть более простые методы для несложных судоку? И еще, какие есть методы генерации судоку (кроме тупого перебора)?
                  0

                  Некоторые более простые методы хорошо описаны в этой статье: https://habrahabr.ru/post/173795/
                  А вот насчёт генерации лично я ничего подсказать не смогу.

                0
                Осталось только нейросеть запилить.
                • UFO just landed and posted this here
                  0
                  Интересно, а как будет соотноситься производительность перебора и этого метода при увеличении размерности судоку?
                    0

                    Действительно интересный вопрос, я бы тоже рад был знать ответ. Мне вообще не понятно, как можно адекватно оценить трудоёмкость описанного алгоритма.
                    Сразу можно сказать одно — чем больше будет размерность, тем больше будет погрешность вычислений на последнем этапе, поскольку коэффициенты am экспоненциально растут по мере нахождения ответа. Рано или поздно мы выбьемся из точности double, после этого ни о какой эффективности и говорить не стоит.

                      0
                      Тогда остается вариант со смешанным методом нахождения верного решения. Но тут возникает проблема динамического выбора способа решения.
                        0
                        Есть способ оценить сложность алгоритма-черного-ящика экспериментально:
                        Пусть время выполнения алгоритма — это f(n). Если это полиномиальное время, т.е. f(n) =a*n^b, в этом случае a и b можно найти следующим путем:
                        * запускаем алгоритм на 1000*n входных данных. Засекаем время.
                        * запускаем алгоритм на 2000*n входных данных. Засекаем время.
                        * запускаем алгоритм на 4000*n входных данных. Засекаем время.
                        * запускаем алгоритм на 8000*n входных данных. Засекаем время.
                        * запускаем алгоритм на 16000*n входных данных. Засекаем время.

                        В случае судоку можно взять меньшие размеры взодных данных: 1n, 2n, 4n, 8n, etc…

                        Затем строим таблицу:
                        _n_|__время выполнения__|__rate________|__b=log(rate)__|
                        1 * n| t1 = a * 1^b * n^b | |
                        2 * n| t2 = a * 2^b * n^b | t2/t1 = t2' = 2^b | log(t2') |
                        4 * n| t3 = a * 4^b * n^b | t3/t2 = t3' = 2^b | log(t3') |
                        8 * n|… |… |… |

                        По идее все строчки последнего столбика — это одно и то же число b. Но из-за погрешностей значение b будет стабилизироваться лишь со временем при больших объемах входных данных.
                        Если же b не стабилизировалось, но медленно растет, вероятно f(n)= a*n^b*log(n).
                        Не стабилизировалось и быстро расте, вероятно f(n) степенная функция или «факториальная».
                          0

                          Способ хороший. Использовать я его, конечно, не буду)
                          А если серьёзно, я бы с удовольствием, но тут встаёт большой вопрос определения размера входа задачи. 2 раскладки судоку легко могут привести к формулам в КНФ с количествами дизъюнктов, отличающимися на порядки. И эту величину сложно прогнозировать заранее, когда ты просто выбираешь/генерируешь задачу. Это первая проблема.
                          Вторая проблема — случайный выбор начальных данных для системы ОДУ. Это приводит к непредсказуемому времени выполнения, а значит эксперимент придётся запускать очень много раз, чтобы узнать среднее значение. Будь алгоритм полностью детерминированным (не зависел бы от рандома), всё стало бы куда проще.
                          В общем, для данного конкретного алгоритма определение сложности станет той ещё головной болью.


                          Так или иначе, большое спасибо за развёрнутый комментарий!

                      0
                      Интересно, а с помощью нейронных сетей судоку еще не решали?
                      Может градиентный спуск сходился бы быстрее, и мат.аппарат такой не нужен
                        0

                        А вы задавались вопросом: Всегда ли в каждой конкретной исходной задаче есть всегда один правильный ответ? Я не силен так математике как вы, но когда занимался с ребёнком программированием чуть в сторону от школьной программы, то применял конечно же простой перебор. Так вот если начинать с 1 или с 9 подбирать, то попадались задачи из газет и журналов где было два решения. Смотря с какой цифры начинать подбирать.

                          0

                          Скажем так, единственность решения обычно подразумевается. Если находится два допустимых решения, то это ошибка издателя, такая раскладка не должна быть допущена до конечного потребителя. Но в теории, конечно, легко составить судоку, которое будет иметь 10 решений, или вообще ни одного. Простейший вариант — неоднозначность типа
                          1 2
                          2 1

                            0

                            Таким образом у добросовестного издателя должен быть метод (например программа) который даст ответ на вопрос: Данное судоку имеет только один вариант решения? И если 1, то в тираж. Я так понимаю, что сейчас издатель мягко говоря "не замарачивается". Ну да ладно. Это не относится к статье. Вам спасибо, статья интересная и поучительная.

                        Only users with full accounts can post comments. Log in, please.