Lion писал(а):
Это с непривычки. Поверьте, 99% всех судоку разгадывается за 5 минут. Если хотите. я могу привести действительно сложные судоку.
Это если процессор хороший. А головой — не получается. Что такое 99% судоку — см. ниже.
Lion писал(а):
Скорее всего --- нет. Можно придумать конкретный алгоритм, который в 99 % случаев не использует перебор вообще.
Лично мое впечатление, что существует заметное количество судоку, не решаемое без перебора. В определенном смысле.
Lion писал(а):
1. Придумать алгоритм, который будет строить судоку.
Таких алгоритмов — несть числа. Правильная постановка задачи: придумать алгоритм, который будет строить судоку без перебора (то есть, не добавляя новую клетку и потом проверяя, судоку ли это).
Lion писал(а):
2. Каково минимальное количество цифр, необходимое для того, чтобы соответствующая судоку имела единственное решение?
Тут несколько неточностей.
(а) судоку, по определению, должна иметь единственное решение. Хотя возможны начальные конфигурации, принципиально не разрешимые, они просто не судоку. Минимальное количество свободных клеток в неоднозначной конфигурации — четыре.
(б) Что такое цифры? Если это 1, 2, … 9, то ответ 8. В судоку (в постановке, в начальной конфигурации) может отсутствовать одна цифра, и такое я встречал. Если отсутствует больше чем одна, то, очевидно, решение неоднозначно (отсутствующие цифры можно менять местами).
(в) Если речь идет о количестве первоначально данных клеток, то вопрос, по-моему, открыт. Вроде известны примеры с 16 клетками, построенные вручную. На ответ накладывается вопрос о симметрии. Традиционно, судоку центрально симметричен. Очевидно, что если отказаться от симметрии, то может быть удастся уменьшить количество заполненных клеток.
Brukvalub писал(а):
Интересно было бы, на мой взгляд, оценить сверху и снизу сложность алгоритма решения судоку (речь я веду о нетривиальной оценке с использованием алгоритма,заранее отбрасывающего заведомо неприемлемые варианты, а не о количестве вариантов при прямом переборе всех, даже явно невозможных, случаев)
Константа
Потому, что судоку конечная задача. Можно ставить вопрос, например, заменяя 3 на
. Но тут неизвестно даже как растет количество первоначально заполненых клеток.
~~~
Lion писал(а):
Насчет решения на компьютере: один мой друг утверждает, что он написал макрос для решения судоку.
Написать такой макрос не хитро. Займет он не более сотни строк, особенно если делать только перебор с возвратами. И, из-за маленького пространства задачи, будет решать все как паровоз.
Гораздо хитрее написать макрос, который решает логически, как человек. То есть, смотрит: в этой клетке не может быть ничего, кроме тройки. А в этой строке семерка может быть только здесь. И т.д. Такой макрос тоже пишется, и тоже невелик. Более того, этот макрос — ядро оценки сложности судоку при автоматической генерации задачи на компьютере. Поскольку он позволяет оценить, насколько сложные манипуляции придется делать человеку.
Всего существует порядка десятка логических правил, подобных приведенным выше. (Одно из них, имеющих спорный статус: пусть возможные цифры приведены в фрагменте
. Тогда если можно исключить 3, то судоку неоднозначен. Поэтому выбираем три.) По опыту, заметное количество автоматически сгенерированных судоку (порядка 10%, или даже больше), в какой-то момент утыкаются в ситуацию, когда ни одно из правил не применимо. Тогда остаются перебор и его замаскированные разновидности (например, раскраска). Их мало кто-может сделать устно за 5 минут. Итого: нормальным считается решение судоку за 10–40 минут в зависимости от сложности.
Основная проблема при программной генерации судоку — сделать их похожими на ручные, составленные человеком.
Некоторое количество
ссылок (все английские, японский продолжает ржаветь).
Добавлено спустя 54 минуты 16 секунд:Lion писал(а):
Привожу пример достаточно сложного судоку:
У меня получился с одной точкой перебора (догадкой). Кто-нибудь может без догадок?
Наш ответ Чемберлену:
. Среднее у этих судоку отклоняется от 5 в противоположные стороны на одну и ту же величину. Поэтому, любое систематическое отклонение — результат влияния человека на обозначения (выбор цифр).
