Pull to refresh

Comments 26

UFO landed and left these words here

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

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

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

UFO landed and left these words here

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

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

Немного повспоминал. Тут вопрос лишь в сложности этих ограничений. Если рассматривать лишь базовые: «здесь может быть только 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/
А вот насчёт генерации лично я ничего подсказать не смогу.

UFO landed and left these words here
Интересно, а как будет соотноситься производительность перебора и этого метода при увеличении размерности судоку?

Действительно интересный вопрос, я бы тоже рад был знать ответ. Мне вообще не понятно, как можно адекватно оценить трудоёмкость описанного алгоритма.
Сразу можно сказать одно — чем больше будет размерность, тем больше будет погрешность вычислений на последнем этапе, поскольку коэффициенты 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, то в тираж. Я так понимаю, что сейчас издатель мягко говоря "не замарачивается". Ну да ладно. Это не относится к статье. Вам спасибо, статья интересная и поучительная.

Only those users with full accounts are able to leave comments. Log in, please.