hola

Heyawake ( en japonés : へやわけ, "habitaciones divididas") es un rompecabezas de lógica binaria publicado por Nikoli . Hasta 2013, Nikoli había publicado cinco libros compuestos íntegramente por rompecabezas de Heyawake . Apareció por primera vez en Puzzle Communication Nikoli #39 (septiembre de 1992).

Heyawake se juega en una cuadrícula rectangular de celdas sin tamaño estándar; la cuadrícula está dividida en "habitaciones" rectangulares de distintos tamaños mediante líneas gruesas que siguen los bordes de las celdas. Algunas habitaciones pueden contener un solo número, generalmente impreso en la celda superior izquierda; en su diseño original, todas las habitaciones estaban numeradas, pero esto rara vez es necesario para resolver el juego y ya no se sigue.

Algunas de las celdas del rompecabezas deben pintarse de negro; el objetivo es determinar, para cada celda, si debe pintarse o dejarse en blanco. En la práctica, suele ser más fácil marcar las celdas que se sabe que están en blanco de alguna manera , por ejemplo, colocando un punto en el centro de la celda.

Las siguientes reglas determinan qué células son cuáles:

• Regla 1: Las celdas pintadas nunca pueden estar conectadas ortogonalmente (no pueden compartir un lado, aunque sí pueden tocarse en diagonal).
• Regla 2: Todas las células blancas deben estar interconectadas (formar un único poliomino ).
• Regla 3: Un número indica la cantidad exacta de celdas pintadas que debe haber en esa habitación en particular.
• Regla 4: Una habitación que no tenga número puede contener cualquier número de celdas pintadas, o ninguna.
• Regla 5: Cuando se forme una línea recta (ortogonal) de glóbulos blancos conectados, esta no debe contener glóbulos de más de dos habitaciones ; en otras palabras, cualquier línea de glóbulos blancos que conecte tres o más habitaciones está prohibida.

Cabe señalar que las dos primeras reglas también se aplican a (por ejemplo) los rompecabezas Hitori , por lo que estos rompecabezas comparten algunos de sus métodos de resolución:

• Si se descubre que una celda está pintada de negro, se sabe inmediatamente que las cuatro celdas adyacentes (ortogonalmente) deben ser blancas (según la Regla 1).
• Una sección de celdas blancas contiguas (ortogonalmente) no puede separarse del resto de la cuadrícula (según la Regla 2). Las celdas negras no pueden formar una división diagonal a través de la cuadrícula ni un bucle cerrado; cualquier celda que complete tal "cortocircuito" debe ser blanca.

Los rompecabezas más complejos requieren combinar la Regla 1 y la Regla 2 para avanzar sin adivinar; la clave está en reconocer dónde las celdas deben adoptar uno de dos patrones de tablero de ajedrez y cuál de ellos conduce a un cortocircuito.

Las reglas restantes diferencian a Heyawake de otros rompecabezas de "dinastía":

• La regla 5 es la regla fundamental del rompecabezas; las celdas negras deben colocarse de manera que se eviten líneas (ortogonales) de celdas blancas que crucen dos límites de la habitación ("llaves inglesas").
• Las habitaciones numeradas suelen proporcionar a quienes resuelven el problema un punto de partida, entre otras deducciones. Los siguientes son los ejemplos más sencillos de habitaciones definidas al inicio:
  • Una habitación de 2×2 en la esquina de la cuadrícula que contiene un '2' debe tener una celda pintada en la esquina de la cuadrícula y el segundo cuadrado pintado en diagonal hacia afuera desde la esquina. Como los cuadrados pintados no pueden compartir un lado (Regla 1), la única alternativa desconectaría la celda blanca forzada en la esquina, violando la Regla 2.
  • Una habitación de 2×3 con el lado de 3 celdas a lo largo de un borde de cuadrícula que contiene un '3' debe tener una celda pintada en el centro del lado de 3 celdas a lo largo del borde y las otras dos en las esquinas opuestas de la habitación, por razones similares a las anteriores.
  • Una habitación de 1×3 que contiene un '2' debe tener pintadas las dos celdas de los extremos, ya que una celda central pintada obligaría a infringir la regla 1. En términos más generales, una habitación de 1×(2 n −1) que contiene un n debe tener pintadas todas las demás celdas que contiene.
  • Una habitación de 3×3 que contenga un '5' debe tener un patrón de cuadros, con celdas pintadas en todas las esquinas y en el centro.

• Heyawacky se juega de forma similar a Heyawake, pero las habitaciones no son necesariamente rectangulares. Las líneas ortogonales de células blancas no pueden salir y volver a entrar en una habitación; es decir, dichas líneas no pueden abarcar más de un límite de región.
• Symmetry Heyawake (también conocido como ekawayeH y Ayeheya ) se juega como Heyawake, pero la colocación de las celdas sombreadas en cada habitación es simétrica rotacionalmente alrededor de su centro.

Se ha analizado la complejidad computacional de Heyawake: ^{[ 1 ]} decidir para una instancia dada de Heyawake si existe una solución al rompecabezas es NP-completo . Una interpretación de este resultado teórico en términos sencillos es que este rompecabezas es tan difícil de resolver como el problema de satisfacibilidad booleana , que es un problema difícil bien estudiado en ciencias de la computación .

Lista de tipos de rompecabezas Nikoli

• Holzer, Markus; Ruepp, Oliver (2007). «Los problemas del diseño de interiores: un análisis de complejidad del juego Heyawake» (PDF) . Actas de la 4.ª Conferencia Internacional sobre Diversión con Algoritmos, LNCS 4475. Springer, Berlín/Heidelberg. pp. 198–212 . doi : 10.1007/978-3-540-72914-3_18 . ISBN  978-3-540-72913-6.

• Página de Nikoli en Heyawake archivada el 9 de noviembre de 2013 en Wayback Machine.