Сложность n-ферзей-доделок?

Классическая задача quens задает, учитывая положительное целое число , существует ли массив чисел удовлетворяющий следующим условиям:$n$$n$$Q[1..n]$

• $1\le Q[i] \le n$ для всех$i$
• $Q[i] \ne Q[j]$ для всех$i\ne j$
• $Q[i]-i \ne Q[j]-j$ для всех$i\ne j$
• $Q[i]+i \ne Q[j]+j$ для всех$i\ne j$

Каждое целое число представляет положение ферзя в й строке шахматной доски; ограничения кодируют требование, чтобы ни одна королева не атаковала любую другую королеву. Нетрудно доказать, что при или решений не существует, а решения в замкнутой форме известны для всех других значений . Таким образом, проблема решения королев является тривиальной.$Q[i]$$i$$n\times n$$n=2$$n=3$$n$$n$

Стандартный алгоритм обратного отслеживания для построения решения с королевами умозрительно помещает ферзей в префикс строк, а затем рекурсивно определяет, существует ли законное размещение ферзей в оставшихся строках. Рекурсивная подзадача может быть формализована следующим образом:$n$

• Если задано целое число и массив целых чисел, является ли префиксом массива который описывает решение проблемы kens?$n$$P[1..k]$$P$$Q[1..n]$$n$

Это более общее решение проблемы NP-трудно?

Известно, что несколько близких вопросов являются NP-сложными, включая завершение латинского квадрата [ Colbourn 1984 ], завершение Sudoku [ Yato and Seta 2002 ] и другое обобщение королев [ Martin 2007 ], но этот конкретный вопрос, похоже, ушел любое серьезное внимание.$n$

Связанные вопросы cstheory.se:

• Является ли проблема N Queens NP-трудной?
• Является ли задача о наполовину заполненном магическом квадрате NP-полной?

Потребовались годы, но этот пост вдохновил нас написать статью, которая вышла сегодня.

Ответ в том, что n Queens Completion является NP-Complete. Однако для полного раскрытия следует упомянуть, что мы решаем небольшой вариант проблемы. В нашем случае набор ферзей не должен быть префиксом полного набора. Так что технически мы не решили точную проблему, заданную здесь. Однако было бы крайне удивительно, если бы версия n Queens Completion из этого запроса также не была NP-Complete.

Я хочу еще раз поблагодарить Джеффа за то, что мы поставили этот вопрос здесь.

Сложность журнала n Queens Completion журнала AI Research Gent, Jefferson, Nightingale doi: 10.1613 / jair.5512 http://www.jair.org/papers/paper5512.html

(Это указывает на некоторые связанные результаты. Сначала я думал, что связанные результаты очень связаны, но я не могу быстро заполнить пробелы, так что, возможно, они не так уж и связаны. Возможно, все еще полезно.)

Упражнение 118 в разделе (черновик) 7.2.2.2 «Искусства компьютерного программирования» рассматривает очень похожую проблему. В решении Кнут зачисляет статью, которая в свою очередь зачитывает

• Гарднера, Грицманб, Прангенберг, О вычислительной сложности восстановления решеточных множеств по их рентгеновским лучам , 1999

Упражнение 118 доказывает, что БИНАРНАЯ ЦИФРОВАЯ ТОМОГРАФИЯ является NP-полной. Вход этой задачи состоит из линейных и диагональных сумм, все из .$[2]=\{0,1\}$

ВХОД: и$r,c\in[2]^m$$a,b\in[2]^{2m-1}$

ВЫХОД: существует ли такой что и и and $x\in[2]^{m\times m}$$\sum_j x_{ij}=r_i$$\sum_i x_{ij}=c_j$$\sum_i x_{i,s-i}=a_s$$\sum_i x_{i,d+i}=b_{d+m-1}$

Мне не понятно, как свести это к вашей проблеме. Одно из наблюдений, которое может помочь, заключается в том, что результат вашей задачи также зависит только от сумм, а не от точного расположения королев. (См. Теорему 2.4 в [Ривин, Динамическое программирующее решение проблемы n-Квинса, 1992], хотя, возможно, это легко увидеть.)

Кнут доказывает, что БИНАРНАЯ ЦИФРОВАЯ ТОМОГРАФИЯ является NP-полной благодаря сокращению из БИНАРНОЙ ПРОБЛЕМЫ НЕПРЕРЫВНОСТИ. Это очень похожая проблема, за исключением трех измерений и без диагоналей.

ВХОД:${xi},{xj},{xk}\in[2]^{n\times n}$

ВЫХОД: существует ли , что и и $x\in[2]^{n\times n\times n}$$\sum_i x_{ijk}={xi}_{jk}$$\sum_j x_{ijk}={xj}_{ik}$$\sum_k x_{ijk}={xk}_{ij}$

Статья Гарднера и соавт. кажется, уменьшает от более стандартных NP-полных проблем. Я не достаточно хорошо понимаю сокращение, чтобы объяснить это здесь, поэтому я просто оставлю указатели сверху, чтобы вы могли их изучить, если хотите.

Все это может быть бесполезно, если кто-то не поймет, как свести двоичную цифровую томографию к задаваемому вопросу.