Какова сложность времени для Алгоритма X для судоку?

Question

Я нашел здесь утверждение, что алгоритм X для судоку имеет O(N^3) временную сложность, где N - размер платы.

Это может быть логично, поскольку для судоку двоичная матрица для вычисления имеет N ^ 3 строки. Но это делает проблему судоку разрешимой за полиномиальное время, и судоку, как известно, является проблемой NP, то есть (насколько я понимаю)

• не всегда можно решить за полиномиальное время

• можно проверить решение за полиномиальное время

Так какова временная сложность алгоритма X для судоку, и возможно ли решить судоку за полиномиальное время или нет?

Спасибо!

Answer 1

Математика Судоку объясняет это довольно хорошо:

Известно, что общая задача решения головоломок судоку на n^2×n^2 сетках из n×n блоков является NP-полной.

Таким образом, сложность во время выполнения любого алгоритма, решающего судоку, является по меньшей мере экспоненциальной по n. Для нормального судоку (n = 3) это означает, что O(N^3) вполне разумно.

Answer 2

Полный анализ времени работы см: https://11011110.github.io/blog/2008/01/10/analyzing-algorithm-x.html

Там говорится, что

даже самая глупая версия алгоритма X, которая избегает любой возможности вернуться назад и всегда выбирает свои опорные точки таким образом, чтобы максимизировать время работы, занимает не более O (3^{n/ 3})

что переводит алгоритм в экспоненциальное время работы (EXPTIME).