Complexité de l'achèvement des n-reines?

Le problème des $n$ -queens classiques demande, étant donné un entier positif $n$ , s'il existe un tableau d'entiers satisfaisant aux conditions suivantes:$Q[1..n]$

• $1\le Q[i] \le n$ pour tout$i$
• i ≠ $Q[i] \ne Q[j]$ pour tout$i\ne j$
• $Q[i]-i \ne Q[j]-j$ pour tout$i\ne j$
• $Q[i]+i \ne Q[j]+j$ pour tout$i\ne j$

Chaque entier représente la position d'une reine sur la ème rangée d'un échiquier ; les contraintes codent l'exigence qu'aucune reine n'attaque une autre reine. Il est facile de prouver qu'il n'y a pas de solutions lorsque ou , et les solutions sous forme fermée sont connues pour toutes les autres valeurs de . Ainsi, en tant que problème de décision , le problème des -queens est complètement trivial.i n × n n = 2 n = 3 $Q[i]$$i$$n\times n$$n=2$$n=3$$n$$n$

L'algorithme de retour arrière standard pour construire une solution à reine place de manière spéculative des reines sur un préfixe des lignes, puis détermine récursivement s'il existe un placement légal de reines sur les lignes restantes. Le sous-problème récursif peut être formalisé comme suit:$n$

• Étant donné un entier et un tableau d'entiers, est-il un préfixe d'un tableau qui décrit une solution au problème des -queens?$n$$P[1..k]$$P$$Q[1..n]$$n$

Ce problème de décision plus général est-il difficile à NP?

Plusieurs questions proches sont connues pour être NP-difficiles, y compris l'achèvement du carré latin [ Colbourn 1984 ], l'achèvement Sudoku [ Yato et Seta 2002 ], et une généralisation différente des -queens [ Martin 2007 ], mais cette question spécifique semble avoir échappé toute attention sérieuse.$n$

Questions cstheory.se connexes:

• Le problème des N Queens est-il difficile à NP?
• Le problème du carré magique à moitié rempli est-il complet?

Cela a pris des années mais cet article nous a inspiré pour écrire un article qui est sorti aujourd'hui.

La réponse est que n Queens Completion est NP-Complete. Cependant, pour une divulgation complète, il convient de mentionner que nous résolvons une légère variante du problème. Dans notre cas, l'ensemble des reines ne doit pas nécessairement être un préfixe de l'ensemble complet. Donc, techniquement, nous n'avons pas résolu le problème exact posé ici. Cependant, il serait extrêmement surprenant que la version de n Queens Completion de cette requête ne soit pas également NP-Complete.

Je tiens à répéter les remerciements que nous adressons à Jeffε pour avoir soulevé cette question ici.

La complexité de n Queens Completion Journal of AI Research Gent, Jefferson, Nightingale doi: 10.1613 / jair.5512 http://www.jair.org/papers/paper5512.html

(Cela indique certains résultats liés. Au début, je pensais que les résultats liés sont très liés, mais je ne peux pas combler rapidement les lacunes, alors peut-être qu'ils ne sont pas si liés après tout. Peut-être toujours utiles.)

L'exercice 118 de la (version provisoire) de la section 7.2.2.2 de L'art de la programmation informatique examine un problème très similaire. Dans la solution, Knuth crédite un article qui à son tour crédite

• Gardnera, Gritzmannb, Prangenbergc, Sur la complexité informatique de la reconstruction d'ensembles de réseaux à partir de leurs rayons X , 1999

L'exercice 118 prouve que la TOMOGRAPHIE NUMÉRIQUE BINAIRE est NP-complète. L'entrée de ce problème se compose de sommes linéaires et diagonales, toutes de .$[2]=\{0,1\}$

$r,c\in[2]^m$$a,b\in[2]^{2m-1}$

$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}$

Je ne sais pas comment réduire cela à votre problème. Une observation qui pourrait aider est que la sortie de votre problème dépend également uniquement des sommes, et non du positionnement exact des reines. (Voir le théorème 2.4 dans [Rivin, une solution de programmation dynamique au problème des n-reines, 1992], bien que cela soit peut-être facile à voir.)

Knuth prouve que la TOMOGRAPHIE NUMÉRIQUE BINAIRE est NP-complète par une réduction du PROBLÈME D'INTERVENTION BINAIRE. C'est un problème très similaire, sauf en 3 dimensions, et sans diagonales.

${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}$

L'article de Gardnera et al. semble réduire des problèmes NP-complets plus standard. Je ne comprends pas assez bien non plus la réduction pour l'expliquer ici, donc je vais juste laisser les pointeurs d'en haut pour que vous exploriez si vous le souhaitez.

Tout cela pourrait être inutile, à moins que quelqu'un ne trouve comment réduire la TOMOGRAPHIE NUMÉRIQUE BINAIRE à la question posée.