Является ли SUDOKU np-complete?

Question

Я прошел это .

Я не понимаю этого.

Судоку является NP-полным, когда обобщено на сетку × n, однако стандарт 9× 9 Судоку не является NP-завершенным.

Answer 1

Вы анализируете проблему в O(N), когда N стремится к бесконечности.Но ваша входная задача не меняется с N до бесконечности, у вас есть конечная верхняя граница.Эта верхняя граница постоянна.

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

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

Answer 2

Корректное;Любое Судоку 9x9 может быть решено за O (1) время (как и Судоко 1x1, или Судоко 4x4, или даже Судоку 1000x1000), потому что размер ввода фиксирован.NP-полнота - это концепция, которая применима к решению проблем с переменная размер ввода, так что вы можете анализировать время выполнения алгоритма при асимптотическом росте размера ввода.

Разница заключается в том,алгоритм может принимать размер ввода или должен ждать, пока он не получит вход, чтобы увидеть, насколько он велик.

Вход не имеетбыть закодированным в двоичном виде;ему просто нужно использовать алфавит конечного размера.Для судоку фиксированного размера вы можете выбрать алфавит, который имеет один уникальный символ для каждой возможной головоломки.(В практическом плане вы можете кодировать теоретический алфавит в двоичном виде, с двоичной строкой фиксированного размера для каждого символа алфавита. Вот как работает ASCII. Размер входного сигнала все еще постоянен; это просто константа, которая больше единицы.)Затем алгоритм использует жестко закодированную таблицу, которая связывает каждый символ во входном алфавите с его решением.Алгоритм с постоянным временем, который решает загадку, - это просто поиск по таблице.

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

1. Нельзя хранить решения для всех возможных входных данных в ограниченном объеме пространства, поэтому вашему алгоритму необходимо выполнить реальную работу для решения головоломки, как только он увидит входные данные.

2. Не все входы будут иметь одинаковый размер, поскольку фиксированная строка символов из конечного алфавита может кодировать только конечное число головоломок.Когда входные данные имеют разные размеры, вы можете рассмотреть, сколько работы должен выполнять ваш алгоритм, как функцию от входного размера.(Просто , читая , ввод теперь является операцией O (n); работа, необходимая для решения проблемы, может быть, и обычно больше).