Hidoku NP est-il complet?

Un Hidoku est une grille avec quelques entiers préremplis de 1 à . Le but est de trouver un chemin d'entiers successifs (de 1 à ) dans la grille. Plus concrètement, chaque cellule de la grille doit contenir un entier différent de 1 à et chaque cellule de valeur doit avoir une cellule voisine de valeur (peut également être en diagonale). $n \times n$ $n^2$ $n^2$ $n^2$ $z ≠ n^{2}$ $z + 1$

Est-il difficile pour NP de décider si un Hidoku donné est résoluble? Quelle réduction pourrait être utilisée?

Edit: selon les commentaires, je donne un petit éclaircissement. Étant donné une grille de cellules, certaines d'entre elles contiennent déjà des valeurs (entiers de 1 à n²). Nous devons remplir toutes les cellules restantes avec des nombres entiers de 1 à , de sorte que deux cellules n'ont pas la même valeur et que chaque cellule avec la valeur a un voisin avec la valeur . Autrement dit, après avoir rempli les cellules, nous devons trouver le chemin . Dans la grille, qui visite logiquement chaque cellule. $n^2$ $z ≠ n²$ $z + 1$ $1, 2, 3,\cdots, n^2$

Un exemple de Hidoku serait http://www.janko.at/Raetsel/Hidoku/018.c.gif . Un Hidoku déjà résolu est http://diepresse.com/images/uploads/3/f/7/586743/spectrumsommerraetsel_7august_hidoku_schwer_loesung20100810172340.gif , où vous pouvez voir le chemin auquel je faisais référence.

complexity-theory reductions np-hard ipsec
la source

Intuitivement, sans y penser beaucoup, cela semble résolu par le polytime à première vue. Quelque chose comme une programmation dynamique sur les valeurs autorisées (

1, \dots, n^{2}

$1, \dots, n^2$ ) et les sommets (

v_{1}, \dots v_{n}

$v_1, \dots v_n$ ). Sons résolubles dans le temps

O (n^{3})

$O(n^3)$ .

Pål GD

Ceci peut être modélisé de manière équivalente sous forme de graphe, connectant des nœuds avec des arêtes s'ils sont successeurs dans

N

$\mathbb{N}$ . Ensuite, vous cherchez un chemin à Hamilton. Selon les chemins de Hamilton dans les graphiques en grille d'Itai et al. (1982), ce problème est NP-complet dans les graphiques en grille. Cela ne correspond pas immédiatement à votre problème car vous autorisez les connexions diagonales, mais cela augure mal.

Raphael

@Raphael n'est pas le graphique construit un DAG?

Pål GD

Je ne vois pas comment c'est un DAG. Pour autant que je comprends, l'entrée est un graphique en grille (non orienté) (contenant également des bords diagonaux) et le but est de trouver un chemin hamiltonien, où la position de certains nœuds sur le chemin est donnée.

George

@George Okey, j'ai interprété la question comme trouvant le chemin maximum des valeurs croissantes dans une grille!

Pål GD

Réponses:

Je pense qu'il est -complet: comme l'a remarqué Raphaël, le cycle hamiltonien sur les graphes de grille avec problème de trous est NP-complet ( Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter: Hamilton Paths in Grid Graphs. SIAM J Comput. 11 (4): 676-686 (1982) ). $\sf{NP}$

Donc, étant donné un graphique de grille avec des trous, vous pouvez facilement créer un jeu Hidoku équivalent où les cellules fixes initiales remplissent toutes les diagonales paires; les diagonales impaires vides forment un graphique non orienté qui est équivalent au graphique de grille d'origine et le Hidoku a une solution si et seulement si le graphique de grille d'origine a un chemin hamiltonien. $G$ $G$

entrez la description de l'image ici

Figure 1: un graphique en grille avec des trous et le puzzle Hidoku équivalent (les cellules bleues représentent les cellules numérotées fixes initiales ( est la première, est la dernière), les cellules blanches sont les cellules que le joueur doit remplir, violet ligne indique la séquence des cellules numérotées fixes initiales). $12 \times 12$ $1$ $144$

Des lignes auxiliaires (remplies) peuvent être ajoutées en bas ou à droite pour en faire un carré.

Un autre exemple de réduction d'un graphique de grille à un puzzle Hidoku: le graphique de grille 6x4 est intégré dans une plus grande grille 13x13; les diagonales paires sont remplies de nombres fixes et les cellules libres restantes sont équivalentes au graphique de grille d'origine.

entrez la description de l'image ici

L'image complète avec transformation peut être téléchargée ici .

Quelques notes supplémentaires pour compléter la réponse:

le problème est également connu sous le nom de Hidato ; la carte peut avoir une forme arbitraire (mais comme généralisation du boîtier carré, elle reste NP-difficile);
comme l'a correctement démontré Steven Stadnicki dans sa réponse, il n'est pas évident que le problème se situe dans NP si la grille initiale partiellement remplie n'est pas donnée sous la forme d'un tableau d'entiers mais est donnée dans une représentation succincte ; cependant, il est clairement dans NP si la carte initiale est donnée en utilisant la liste raisonnable de représentation d'entiers; $n \times n$
Je pense que les règles originales du jeu disent que la solution doit être unique ; le problème est donc aux États - Unis (dur aux États-Unis) et il est peu probable qu'il soit en NP.

En résumé, si nous supprimons la contrainte de solution unique et spécifions la carte initiale avec une liste de entiers, le jeu est -complete. $n^2$ $\sf{NP}$

Vor
la source

N'est-ce pas un DAG? Ai-je complètement mal compris la question?

Pål GD

@ PålGD: non, je ne pense pas que ce soit un DAG, c'est un graphique en grille non orienté avec des bords diagonaux. Le jeu commence avec un tableau partiellement rempli et le joueur doit commencer à partir de la cellule 1 et atteindre le dernier en faisant des pas orthogonaux ou diagonaux (mais peut-être que je ne me souviens pas très bien des règles ... maintenant je le vérifie)

Vor

Mais il dit "trouver un chemin d'entiers successifs".

Pål GD

Peut-être que cela signifie simplement qu'il ne peut pas visiter la même cellule deux fois et que toutes les cellules doivent être visitées

Vor

"Le but est de trouver un chemin d'entiers successifs (de à ) dans la grille"?

1

$1$

n^{2}

$n^2$

Pål GD

$n\times n$ $\Omega(n)$ $n$ $\lg n$ $(x_i, y_i, w_i): x_i, y_i\leq n, w_i\leq n^2$ $(x_i, y_i)$ $w_i$ $\lg n + \lg n + \lg n^2 = 4\lg n\in O(\lg n)$ $\Omega(n)$ $o(n)$

$\Omega(n)$

(Pour une discussion sur des questions similaires, voir ma question il y a quelque temps sur la complexité de Nurikabe succinct sur le site cstheory.SE.)

Steven Stadnicki
la source

Ne pas spécifier la taille de la planche en unaire me semble une interprétation déraisonnable.

David Eisenstat

@DavidEisenstat Ce n'est pas nécessairement l' interprétation naturelle , mais elle me semble parfaitement valable.

Steven Stadnicki

@StevenStadnicki: Je suis d'accord avec vous, j'ai fait une note similaire dans la preuve d' exhaustivité de NP de Binary Puzzle que j'ai récemment publiée sur cstheory.stackexchange.com. Bien que la représentation non unaire ne soit en effet pas si raisonnable :-). Je vais ajouter une note sur ma réponse. Et je devrais également aborder le problème de l'unicité de la solution; parce que je pense que les règles d'origine disent que la solution doit être unique.

Vor