Est-il difficile de lire correctement les brouillons internationaux?

Le problème suivant est-il NP-difficile?

Étant donné une configuration de carte pour brouillons internationaux , trouvez un mouvement juridique unique.$n\times n$

Le problème correspondant pour les vérificateurs américains (ou versions anglaises) est trivialement résoluble en temps polynomial. Il existe trois différences majeures entre ces deux jeux.$n\times n$

La première et la plus importante différence est la règle du «roi volant». Aux pions, un roi peut sauter par-dessus la pièce d' un adversaire adjacent dans une case vide à deux pas dans n'importe quelle direction diagonale. Dans les projets internationaux, un roi peut sauter par-dessus la pièce d'un adversaire à une distance arbitraire en se déplaçant sur une distance arbitraire le long d'une diagonale.

Comme dans les dames, la même pièce peut être utilisée pour capturer une série de pièces en un seul tour. Cependant, contrairement aux dames, les pièces capturées dans les brouillons internationaux ne sont pas supprimées tant que la séquence entière n'est pas terminée. La pièce capturée peut sauter par-dessus ou atterrir plusieurs fois sur la même case vide, mais elle ne peut pas sauter plus d'une fois par-dessus la pièce d'un adversaire.

Enfin, les pions et les projets internationaux ont une règle de capture forcée: si vous pouvez capturer la pièce d'un adversaire, vous devez. Cependant, les règles règles ne sont pas d'accord lorsqu'il existe plusieurs options pour plusieurs. Dans les dames, vous pouvez choisir n'importe quelle séquence maximale de captures; en d'autres termes, vous pouvez choisir n'importe quelle séquence de capture qui se termine lorsque la pièce de capture ne peut plus capturer. Dans les brouillons internationaux, vous devez choisir la séquence de captures la plus longue . Ainsi, mon problème est équivalent au suivant:

Étant donné une configuration de carte pour brouillons internationaux , trouvez un coup qui capture le nombre maximum de pièces opposées.$n\times n$

Il suffirait de prouver que le problème suivant est NP-complet. (C'est évidemment dans NP.)

Étant donné une configuration de plateau pour projets internationaux impliquant uniquement des rois , un joueur peut-il (et doit-il donc) capturer toutes les pièces de son adversaire en un seul tour?$n\times n$

Le problème de vérificateurs correspondant peut être répondu en temps polynomial; c'est un exercice de devoirs divertissant. Le problème ressemble plus à l'analyse de Demaine, Demaine et Eppstein des phases finales de Phutball ; une solution à l'exercice amusant de devoirs apparaît à la fin de leur article. Une solution apparaît également dans l'article FOCS 1978 de Frankel et al. cela prouve que jouer aux dames de manière optimale est difficile pour PSPACE; voir également la preuve de 1984 de Robson que les vérificateurs sont en fait EXPTIME-complet.

OK, voici la réduction. Il s'avère que vous n'avez pas besoin de planarité après tout. Aussi, pour "trouver un déménagement légal", je prends la question de décision comme "le déménagement X est-il légal?".

Tout d'abord, travaillons plutôt avec un jeu où les pièces se déplacent orthogonalement plutôt qu'en diagonale. Ce jeu est équivalent (il suffit de regarder le tableau des brouillons tourné à 45 degrés) à l'exception des propriétés des bords, que nous n'utiliserons pas. Nous utilisons deux gadgets: fusion / scission et crossover. Voir http://www.hearn.to/draughts.pdf . Nous supposons qu'il y a un seul roi blanc sur le plateau pour se déplacer. (Aucune autre pièce ne pourra capturer un nombre significatif de pièces.) Elle se déplacera dans les couloirs indiqués, capturant des pièces noires en cours de route.

Tout d'abord, fusionnez: si le roi entre sur l'un des N chemins A (en capturant une pièce noire, non représentée), il peut sortir en B. De même, si nous inversons le gadget et qu'il entre en B, capturant la pièce montrée, il peut sortir le long de n'importe quel chemin A (encore une fois, capturer une pièce noire externe). Il s'agit d'un gadget à usage unique (car la pièce noire de sortie ne peut être capturée qu'une seule fois).

Deuxièmement, le croisement. Si le roi entre par A (C), il peut sortir par B (D). Il ne peut pas s'arrêter au milieu et changer de route, car ce serait un segment de mouvement non capturant.

Maintenant, étant donné un graphique dirigé, construisez une configuration de jeu correspondante comme suit. Pour chaque sommet, créez une fusion qui alimente un fractionnement. Acheminez les sorties divisées vers les entrées de fusion des gadgets de sommet (fusion + division) correspondant aux sommets auxquels les bords sortants se connectent, en utilisant des croisements si nécessaire. Démarrez le roi sur une entrée supplémentaire à n'importe quel sommet (avec une pièce noire à capturer pour le laisser entrer dans le sommet).

Enfin, égalisez toutes les «longueurs de bord» en ajoutant des morceaux noirs supplémentaires le long des voies de sortie / d'entrée selon les besoins. S'il y a V sommets et k pièces noires le long de chaque arête, alors le roi peut capturer 2V + kV + 1 pièces si et seulement s'il existe un circuit hamiltonien du graphe correspondant. Si le roi a un mouvement alternatif disponible, capturer une simple chaîne de pièces 2V + kV, puis déterminer si ce mouvement alternatif est légal est NP-complet.

Voici une alternative possible à la réduction de Bob, cette fois du cycle hamiltonien (non dirigé). Je ne suis pas sûr à 100% que les détails sont corrects - j'ai déjà trouvé et corrigé plusieurs problèmes - mais je suis sûr que cela peut être massé en une preuve correcte. Comme le souligne Bob, cette réduction a un bug sérieux; le roi blanc peut facilement s'écarter de son chemin canonique à travers le plateau. Ce bug peut être corrigé en ajoutant le gadget cross-over de Bob aux endroits appropriés (je pense) , mais ce n'est pas très différent de sa réduction.

Soit un graphe non orienté avec n sommets et $G$$n$$m$$G$$-1$

$O(n^2)\times O(n^2)$$O(n^2+m)$$k$$k$$hn$$h$

$k$$k$$k$$(i,j)$$i$$j$$x$$y$

$hn^2+4n$$G$

Maintenant, pourquoi ne m'avez-vous pas posé ce problème lorsque je travaillais sur ma thèse?

OK, j'ai une réduction de Planar Directed Hamiltonian Cycle.