El rompecabezas se juega en una cuadrícula de celdas típicamente rectangular, algunas de las cuales contienen números. Inicialmente, las células son de color desconocido, pero solo pueden ser blancas o negras. Dos celdas del mismo color se consideran "conectadas" si son adyacentes vertical u horizontalmente, pero no diagonalmente. Las células blancas conectadas forman "islas", mientras que las células negras conectadas forman el "mar".
El desafío consiste en pintar cada celda de blanco o negro, sujeto a las siguientes reglas:
Cada celda numerada es una celda de isla, el número que contiene es el número de celdas en esa isla.
Cada isla debe contener exactamente una celda numerada.
Debe haber un solo mar, que no puede contener "piscinas", es decir, áreas de 2×2 de celdas negras.
Los solucionadores humanos suelen puntear las celdas no numeradas que han determinado que pertenecen con seguridad a una isla.
Como la mayoría de los otros acertijos de lógica pura , se espera una solución única, y es muy poco probable que una cuadrícula que contenga números aleatorios proporcione un acertijo Nurikabe con solución única .
Historia
Nurikabe fue desarrollado por primera vez por "renin (れーにん)", cuyo seudónimo es la pronunciación japonesa de "Lenin" y cuyo autónimo puede leerse como tal, en el número 33 de (Puzzle Communication) Nikoli en marzo de 1991. Pronto causó sensación y ha aparecido en todos los números de esa publicación desde el 38 hasta el presente.
En 2005, Nikoli ha publicado siete libros compuestos íntegramente de rompecabezas de Nurikabe .
(Este párrafo depende principalmente de "Nikoli obras completas de acertijos interesantes (ニコリ オモロパズル大全集)". https://web.archive.org/web/20060707011243/http://www.nikoli.co.jp/storage /adición/omopadaizen/)
Métodos de solución
Solución al rompecabezas de ejemplo anterior
No debería ser necesario adivinar a ciegas para resolver un rompecabezas de Nurikabe . Más bien, se puede desarrollar y seguir una serie de procedimientos y reglas simples, asumiendo que el solucionador sea lo suficientemente observador para encontrar dónde aplicarlos.
El mayor error que cometen los solucionadores principiantes es concentrarse únicamente en determinar el blanco o el negro y no el otro; la mayoría de los rompecabezas de Nurikabe requieren ir y venir. Marcar celdas blancas puede obligar a otras celdas a ser negras para que una sección negra no quede aislada, y viceversa. (Quienes estén familiarizados con Go pueden pensar en las células indeterminadas próximas a varias regiones como "libertades" y aplicar la lógica " atari " para determinar cómo deben crecer).
Estrategia básica
Un rompecabezas de Nurikabe resuelto por un humano. Los puntos representan las celdas que se sabe que son blancas.
Dado que dos islas solo pueden tocarse en las esquinas, las celdas entre dos islas parciales (los números y las celdas blancas adyacentes que aún no suman sus números) deben ser negras. Esta suele ser una forma de comenzar un rompecabezas de Nurikabe , marcando en negro las celdas adyacentes a dos o más números.
Una vez que una isla está "completa", es decir, tiene todas las celdas blancas que requiere su número, todas las celdas que comparten un lado con ella deben ser negras. Obviamente, cualquier celda marcada con '1' al principio es una isla completa en sí misma y puede aislarse con negro al principio.
Siempre que tres celdas negras formen un "codo", una L, la celda en la curva (en diagonal desde la esquina de la L) debe ser blanca. (La alternativa es un "grupo", a falta de un término mejor).
Todas las celdas negras eventualmente deben estar conectadas. Si hay una región negra con una sola forma posible de conectarse al resto del tablero, la única vía de conexión debe ser negra.
Corolario: no puede haber un camino continuo, usando pasos verticales, horizontales o diagonales, de celdas blancas desde una celda que se encuentra en el borde del tablero hasta una celda diferente como esa, que encierra algunas celdas negras en su interior, porque de lo contrario, las negras Las celdas no estarán conectadas.
Al final, todos los glóbulos blancos deben formar parte exactamente de una isla. Si hay una región blanca que no contiene un número y solo hay una forma posible de conectarse a una región blanca numerada, la única vía de conexión debe ser blanca.
Algunos acertijos requerirán la ubicación de "inalcanzables": celdas que no se pueden conectar a ningún número, que están demasiado lejos de todas ellas o bloqueadas por otros números. Estas celdas deben ser negras. A menudo, estas celdas tendrán solo una ruta de conexión con otras celdas negras o formarán un codo cuya celda blanca requerida (ver punto anterior) solo puede alcanzar un número, lo que permitirá un mayor progreso.
Estrategia avanzada
Un ejemplo de la tercera estrategia avanzada. La celda diagonal entre las dos islas tiene que ser negra.
Si hay un cuadrado que consta de dos celdas negras y dos celdas desconocidas, al menos una de las dos celdas desconocidas debe permanecer blanca según las reglas. Así, si una de esas dos celdas desconocidas (llámela 'A') sólo puede conectarse a un cuadrado numerado a través de la otra (llámela 'B'), entonces B necesariamente debe ser blanca (y A puede o puede no ser blanco).
Si una isla de tamaño N ya tiene N-1 celdas blancas identificadas, y solo quedan dos celdas para elegir, y esas dos celdas se tocan en sus esquinas, entonces la celda entre esas dos que está en el otro lado de la isla debe ser negro.
Si un cuadrado debe ser blanco y solo dos islas pueden conectarse a él y no quedan celdas no identificadas después de conectarse, entonces si las islas se conectan en un ángulo de 90 grados (por ejemplo: una isla se puede conectar al lado superior y la otra al lado derecho). lado) la celda dentro del ángulo (la que toca la esquina superior izquierda del cuadrado blanco en el ejemplo anterior) debe ser negra para evitar conectar las 2 islas.
Las celdas indeterminadas adyacentes a una fila recta (o una columna recta) de celdas negras se pueden probar para determinar si son negras, porque si son negras formarán dos codos y habrá dos celdas blancas adyacentes a las que se debe poder acceder desde las islas. . Si no se pueden cumplir dentro de las restricciones, significa que la celda en la que se analizó la oscuridad debe ser blanca.
Complejidad computacional
Es NP-completo resolver Nurikabe, incluso cuando los números involucrados son solo 1 y 2.
Además, considere estas dos reglas de Nurikabe:
Las celdas negras forman un área conectada.
Las celdas negras no pueden formar cuadrados de 2 × 2,
Cualquiera de las dos puede ignorarse, dando un total de tres variantes. Resulta que todos son NP completos. [1]
Rompecabezas relacionados
Un ejemplo de rompecabezas Mochikoro de 8x8.Solución al rompecabezas anterior.
Los acertijos de determinación binaria LITS y Mochikoro, también publicados por Nikoli , son similares a Nurikabe y emplean métodos de solución similares. El rompecabezas de determinación binaria Atsumari es similar a Nurikabe pero se basa en un mosaico hexagonal en lugar de un mosaico cuadrado.
Mochikoro es una variante del rompecabezas Nurikabe:
Cada celda numerada pertenece a un área blanca, el número indica cuántas celdas pertenecen al área blanca. Es posible que algunas áreas blancas no incluyan una celda numerada.
Todas las áreas blancas deben estar conectadas en diagonal.
La celda negra no debe cubrir un área de 2x2 celdas o más.
^ Holzer, Markus; Klein, Andreas; Kutrib, Martín (2004). "Sobre la integridad NP del rompecabezas de lápiz NURIKABE y sus variantes" (PDF) . Actas de la 3ª Conferencia Internacional sobre Diversión con Algoritmos . S2CID 16082806. Archivado desde el original (PDF) el 11 de febrero de 2020.
Brandon McPhail, James D. Fix. Nurikabe es la Conferencia NP-Complete NW del CSCC, 2004. También presentada en el Reed Mathematics Colloquium, 2004.
Markus Holzer, Andreas Klein y Martin Kutrib. Sobre la integridad NP del rompecabezas de lápiz NURIKABE y sus variantes. Actas de la Tercera Conferencia Internacional sobre Diversión con Algoritmos, 2004.
