Comments 26
В сложных судоку всегда наступает момент, когда ограничения не позволяют сделать более ни одного хода. Для решения таких судоку приходится перебирать варианты. То есть метод смешанный, ограничения + немного перебора.
Я тоже писал разные решатели судоку. :) И таки да, бывает, что ограничения не работают, а правильное решение все равно единственное. Пару лет назад даже на эту тему спорил с учеником-студентом и где-то даже можно откапать пример такого судоку.
Немного повспоминал. Тут вопрос лишь в сложности этих ограничений. Если рассматривать лишь базовые: «здесь может быть только X» и «X может быть только здесь», то перебор нужен. Если вводить более сложные, то да, можно без перебора. Пример более сложного:
8 _ _ _ _ _ _ _ _
_ _ 3 6 _ _ _ _ _
_ 7 _ _ 9 _ 2 _ _
_ 5 _ _ _ 7 _ _ _
_ _ _ _ 4 5 7 _ _
_ _ _ 1 _ _ _ 3 _
_ _ 1 _ _ _ _ 6 8
_ _ 8 5 _ _ _ 1 _
_ 9 _ _ _ _ 4 _ _
Это не является правдой. Хотя скорее так — нужно уточнить понятие "доступных".
В этапе 1 я перечислил в сумме 4x9x9 ограничений (в нумерованных пунктах). По факту это есть классические правила судоку. Если "доступностью" считать логическую выполнимость всех этих ограничений по отдельности, то уж точно не каждый ход приведёт к правильному решению.
Пример с судоку приводить не буду, так как для этого нужно сидеть и решать, а вот аналогичный с логическими формулами — легко:
1) (a || b) && (!a || b)
2) (a || b) && (!a || !b)
Обе формулы выполнимы по отдельности при "a == true", но вот их конъюнкция при этом будет ложной.
P.S. естественно именно такой конфигурации, как в моём примере, в реальных судоку не возникнет. Ситуация неоднозначиности на практике бывает тогда, когда неизвестных как минимум несколько десятков.
А какие есть более простые методы для несложных судоку? И еще, какие есть методы генерации судоку (кроме тупого перебора)?
Некоторые более простые методы хорошо описаны в этой статье: https://habrahabr.ru/post/173795/
А вот насчёт генерации лично я ничего подсказать не смогу.
Действительно интересный вопрос, я бы тоже рад был знать ответ. Мне вообще не понятно, как можно адекватно оценить трудоёмкость описанного алгоритма.
Сразу можно сказать одно — чем больше будет размерность, тем больше будет погрешность вычислений на последнем этапе, поскольку коэффициенты am экспоненциально растут по мере нахождения ответа. Рано или поздно мы выбьемся из точности double, после этого ни о какой эффективности и говорить не стоит.
Пусть время выполнения алгоритма — это 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) степенная функция или «факториальная».
Способ хороший. Использовать я его, конечно, не буду)
А если серьёзно, я бы с удовольствием, но тут встаёт большой вопрос определения размера входа задачи. 2 раскладки судоку легко могут привести к формулам в КНФ с количествами дизъюнктов, отличающимися на порядки. И эту величину сложно прогнозировать заранее, когда ты просто выбираешь/генерируешь задачу. Это первая проблема.
Вторая проблема — случайный выбор начальных данных для системы ОДУ. Это приводит к непредсказуемому времени выполнения, а значит эксперимент придётся запускать очень много раз, чтобы узнать среднее значение. Будь алгоритм полностью детерминированным (не зависел бы от рандома), всё стало бы куда проще.
В общем, для данного конкретного алгоритма определение сложности станет той ещё головной болью.
Так или иначе, большое спасибо за развёрнутый комментарий!
Может градиентный спуск сходился бы быстрее, и мат.аппарат такой не нужен
А вы задавались вопросом: Всегда ли в каждой конкретной исходной задаче есть всегда один правильный ответ? Я не силен так математике как вы, но когда занимался с ребёнком программированием чуть в сторону от школьной программы, то применял конечно же простой перебор. Так вот если начинать с 1 или с 9 подбирать, то попадались задачи из газет и журналов где было два решения. Смотря с какой цифры начинать подбирать.
Скажем так, единственность решения обычно подразумевается. Если находится два допустимых решения, то это ошибка издателя, такая раскладка не должна быть допущена до конечного потребителя. Но в теории, конечно, легко составить судоку, которое будет иметь 10 решений, или вообще ни одного. Простейший вариант — неоднозначность типа
1 2
2 1
Таким образом у добросовестного издателя должен быть метод (например программа) который даст ответ на вопрос: Данное судоку имеет только один вариант решения? И если 1, то в тираж. Я так понимаю, что сейчас издатель мягко говоря "не замарачивается". Ну да ладно. Это не относится к статье. Вам спасибо, статья интересная и поучительная.
Хаос внутри судоку