Судоку как CSP (согласованность дуги)

Question

Для задания исследования я воссоздал алгоритм Норвига на C#, чтобы решить проблему Sudoku как проблему ограничения ограничений (CSP) в сочетании с локальным поиском с эвристическим количеством возможных значений для квадрата. Теперь мне нужно создать расширение или его вариант, и я немного смущен тем, насколько алгоритм обеспечивает согласованность дуги. Для этого в настоящее время используется текущий алгоритм:

• Инициализировать возможные значения (домены) каждого квадрата как [1, ..., n * n].
• Каждое присваивание значения квадрату выполняется путем исключения каждого возможного значения из домена и обновления каждого равноправного (квадрата в той же подсписке/строке/столбце) путем удаления назначенного значения из их доменов. (Не полностью ли это обеспечивает согласованность дуги, поскольку они являются единственными ограничениями между одноранговыми узлами, что они могут не иметь одинакового значения?)
• При исключении значения из домена квадрата он также проверяет, осталось ли только 1 квадрат для этого значение в его единице. Если это так, он присваивает его этому квадрату (также путем устранения возможных значений, сводя его к этому значению).

Теперь мой вопрос: этот алгоритм обеспечивает полную согласованность дуги? А если нет, как я могу улучшить свой алгоритм CPS для этого?

Если бы кто-нибудь мог мне помочь, это было бы очень признательно!

Заранее спасибо.

С уважением.

Answer 1

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

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

• Установление согласованности дуги для ограничения: грубо означает удаление из каждой переменной всех значений, которые не принадлежат ни одному решению OF THE CONSTRAINT (независимо от остальной части модели). Это зависит от алгоритма фильтрации, который вы используете для ограничения (у вас может быть много разных компромиссов между мощностью фильтрации и временем выполнения).

• Установление согласованности дуги в задаче: представьте, что вы моделируете всю свою проблему, используя одно настраиваемое глобальное ограничение, а затем применяете предыдущее определение.

Итак, вы устанавливаете AC на всю проблему? Это означает, что все нефильтрованное присваивание переменной/значения относится к решению? Из того, что вы описали, ответ отрицательный.

Вы устанавливаете AC на каждом из ваших ограничений? Ну, это зависит от вашей модели. Если вы используете только двоичные ограничения, чтобы заявить о своей проблеме, я бы сказал «да». Если вы хотите улучшить фильтрацию, вы должны использовать глобальные ограничения, такие как AllDifferent. Алгоритм согласования дуги этого ограничения более сложный, чем то, что вы описываете, но он также более мощный!

Вы можете ознакомиться с этим example, который использует Choco Solver. Вы также можете использовать разные уровни согласованности (например, согласованность консистенции).