Какова сложность времени для Алгоритма 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) вполне разумно.