Использование гигантской хэш-таблицы для решения судоку за полиномиальное время

Question

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

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

Разве это не считается решателем судоку, который работает за полиномиальное время?

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

Answer 1

Я думаю, что вы неправильно понимаете проблему. Из Википедии:

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

Несмотря на то, что игра чаще всего бывает в варианте 9x9, общепризнанная проблема характеризует взаимосвязь между размером сетки и сложностью поиска решения, а не какой-либо отдельной сеткой. Если ваша гипотеза верна, это принципиально не изменит классификацию проблемы.

Кроме того, подумайте, как бы вы получили решение-кандидат из такой хеш-таблицы. Если вы используете в качестве ключей последовательность всех начальных значений и их местоположения, вам потребуется сохранить все возможные наборы начальных значений (81 выберите 30, 1.4e22) - для каждого уникального решения (6.7e21). (И это только для решений, которые начинаются с тридцати значений, показывающих...)