¿Está completo el NP de Hidoku?

Un Hidoku es una cuadrícula con algunos enteros precompletados de 1 a . El objetivo es encontrar un camino de enteros sucesivos (de 1 a $n \times n$ $n^2$ ) en la cuadrícula. Más concretamente, cada celda de la cuadrícula debe contener un número entero diferente de 1 a y cada celda con valor debe tener una celda vecina con valor (también puede ser en diagonal). $n^2$ $n^2$ $z ≠ n^{2}$ $z + 1$

¿Es NP difícil decidir si un Hidoku dado tiene solución? ¿Qué reducción podría usarse?

Editar: de acuerdo con los comentarios, doy una pequeña aclaración. Dado es una cuadrícula de celdas, algunas de ellas ya contienen valores (enteros de 1 a n²). Debemos llenar todas las celdas restantes con números enteros de 1 a , de modo que no haya dos celdas que tengan el mismo valor y que cada celda con valor tenga un vecino con valor . Es decir, después de completar las celdas, debemos encontrar la ruta . En la cuadrícula, que visita lógicamente cada celda. $n^2$ $z ≠ n²$ $z + 1$ $1, 2, 3,\cdots, n^2$

Un ejemplo de un Hidoku sería http://www.janko.at/Raetsel/Hidoku/018.c.gif . Un Hidoku ya resuelto es http://diepresse.com/images/uploads/3/f/7/586743/spectrumsommerraetsel_7august_hidoku_schwer_loesung20100810172340.gif , donde puede ver el camino al que me refería.

complexity-theory reductions np-hard ipsec
fuente

Intuitivamente, sin pensarlo mucho, suena polivalente solucionable a primera vista. Algo así como la programación dinámica en los valores permitidos (

) y los vértices (

). Suena solucionable en el tiempo

1, \dots, n^{2}

$1, \dots, n^2$

v_{1}, \dots v_{n}

$v_1, \dots v_n$

O (n^{3})

$O(n^3)$

Pål GD

Esto puede ser modelado equivalente como gráfica, la conexión de los nodos con los bordes si son sucesores en

. Entonces, estás buscando un camino de Hamilton. De acuerdo con las rutas de Hamilton en los gráficos de cuadrícula de Itai et al. (1982) este problema es NP-completo en gráficos de cuadrícula. Esto no se ajusta de inmediato a su problema, ya que permite conexiones diagonales, pero es un mal augurio.

N

$\mathbb{N}$

Raphael

@ Raphael no es el gráfico construido un DAG?

Pål GD

No veo cómo se trata de un DAG. Según tengo entendido, la entrada es un gráfico de cuadrícula (no dirigido) (que también contiene bordes diagonales) y el objetivo es encontrar un camino hamiltoniano, donde se proporciona la posición de algunos nodos en el camino.

George

@George Okey, ¡interpreté la pregunta como encontrar la ruta máxima de valores crecientes en una cuadrícula!

Pål GD

Respuestas:

creo que es -completo: como notó Raphael, el ciclo hamiltoniano en los gráficos de cuadrículaconproblemas deagujeroses NP completo (Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter: Hamilton Paths in Grid Graphs. SIAM J. Comput. 11 (4): 676-686 (1982)). $\sf{NP}$

Entonces, dado un gráfico de cuadrícula con agujeros, puedes construir fácilmente un juego de Hidoku equivalente donde las celdas fijas iniciales llenan todas las diagonales pares; las diagonales impares vacías forman un gráfico no dirigido que es equivalente al gráfico de cuadrícula original y el Hidoku tiene una solución si y solo si el gráfico de cuadrícula original tiene un camino hamiltoniano. $G$ $G$

ingrese la descripción de la imagen aquí

Figura 1: un gráfico de cuadrícula con agujeros y el equivalente $12 \times 12$ rompecabezas Hidoku equivalente (las celdas azules representan las celdas numeradas fijas iniciales ( es la primera, es la última), las celdas blancas son las celdas que el jugador debe llenar, línea púrpura indica la secuencia de las celdas numeradas fijas iniciales). $1$ $144$

Se pueden agregar líneas auxiliares (rellenas) en el lado inferior o derecho para que sea un cuadrado.

Otro ejemplo de reducción de un gráfico de cuadrícula a un rompecabezas Hidoku: el gráfico de cuadrícula de 6x4 está incrustado en una cuadrícula más grande de 13x13; las diagonales pares se rellenan con números fijos, y las celdas libres restantes son equivalentes al gráfico de cuadrícula original.

ingrese la descripción de la imagen aquí

La imagen completa con transformación se puede descargar aquí .

Algunas notas adicionales para completar la respuesta:

el problema también se conoce como Hidato ; el tablero puede tener una forma arbitraria (pero como una generalización de la caja cuadrada, sigue siendo NP-hard);
como lo demostró correctamente Steven Stadnicki en su respuesta, no es obvio que el problema esté en NP si la cuadrícula inicial parcialmente llena no se da como una matriz de enteros, sino que se da en algunos $n \times n$ representación sucinta ; sin embargo, está claramente en NP si la tabla inicial se proporciona utilizando la lista razonable de representación de enteros;
Creo que las reglas originales del juego dicen que el solución debería ser única ; por lo que el problema está en los Estados Unidos (US-duro), y poco probable que sea en NP.

En resumen, si eliminamos la restricción de solución única y especificamos el tablero inicial con una lista de enteros, el juego es -completo. $n^2$ $\sf{NP}$

Vor
fuente

¿No es esto un DAG? ¿He entendido completamente la pregunta?

Pål GD

@ PålGD: no, no creo que sea un DAG, es un gráfico de cuadrícula no dirigido con bordes diagonales. El juego comienza con un tablero parcialmente lleno y el jugador debe comenzar desde la celda 1 y llegar al último haciendo pasos ortogonales o diagonales (pero tal vez no recuerdo muy bien las reglas ... ahora lo reviso)

Vor

Pero dice "encontrar un camino de enteros sucesivos".

Pål GD

Tal vez simplemente significa que no se puede visitar la misma celda dos veces, y que todas las células deben ser visitados

Vor

1

$1$

n^{2}

$n^2$

$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)$ celdas dadas para tener una solución única, por lo que cualquier especificación con menos de esa cantidad de datos puede ser rechazada de inmediato, pero (a) eso supone que está preguntando sobre el ' La variante de solución única del problema en lugar de la variante de "existe una solución", y (b) no es inmediatamente obvio que incluso esa restricción sea verdadera; No estoy seguro de cómo trataría de demostrarlo.

(Para una discusión de problemas similares, vea mi pregunta de hace un tiempo sobre la complejidad de la sucinta Nurikabe en el sitio cstheory.SE).

Steven Stadnicki
fuente

No especificar el tamaño del tablero en unario me parece una interpretación irrazonable.

David Eisenstat

@DavidEisenstat No es necesariamente la interpretación natural , pero me parece perfectamente válida.

Steven Stadnicki

@StevenStadnicki: Estoy de acuerdo con usted, hice una nota similar en la prueba de integridad de NP de Binary Puzzle que publiqué recientemente en cstheory.stackexchange.com. Aunque la representación no unaria no es tan razonable :-). Agregaré una nota en mi respuesta. Y también debería abordar el problema de la singularidad de la solución; porque creo que las reglas originales dicen que la solución debería ser única.

Vor