Решение судоку с помощью эвристики: хорошая идея?

Question

Я пытался решить частично инициализированную головоломку судоку (вид, который появляется в газетах) с пакетом «Планировщик слюней». Хотя он может генерировать (случайную) головоломку с нуля за 3 секунды, он застревает в цикле, решая частично инициализированную головоломку.

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

Мое сомнение связано с тем фактом, что головоломка судоку всегда имеет точное и единственное решение , а эвристические алгоритмы (AFAIK) не предназначены для их "достижения".

Answer 1

Мой ответ на ваш вопрос «да / нет», если эвристики, такие как поиск по табу и симуляция отжига, являются плохим выбором для решения судоку, - да.

Проблема имеет слишком много ограничений для стратегий локального поиска, чтобыБудьте эффективны.

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

Answer 2

Являются ли эвристики, такие как поиск по табу и имитированный отжиг, принципиально плохим выбором для судоку?

Да, хотя бы потому, что хороший алгоритм распространения ограничений может очень быстро решить судоку, поэтому нетнужна эвристика вообще.Кроме того, вы (действительно) не хотите частичного решения судоку.

Answer 3

Для такой проблемы, как судоку 9x9, поиск в грубой кодировке с жестким кодом находит решение очень быстро.Кроме того, поскольку он может быть уверен в нахождении ВСЕХ решений, он также определит, правильно ли сформировано судоку в том смысле, что у него есть уникальное решение.