Heyawake ( japonés : へ や わ け, "habitaciones divididas") es un acertijo lógico de determinación binaria publicado por Nikoli . A partir de 2013, Nikoli ha publicado cinco libros que consisten en su totalidad en rompecabezas de Heyawake . Apareció por primera vez en Puzzle Communication Nikoli # 39 (septiembre de 1992).
Reglas
Heyawake se juega en una cuadrícula rectangular de celdas sin tamaño estándar; la cuadrícula está dividida en "habitaciones" rectangulares de varios tamaños mediante líneas en negrita que siguen los bordes de las celdas. Algunas habitaciones pueden contener un solo número, normalmente impreso en su celda superior izquierda; como se diseñó originalmente, cada habitación estaba numerada, pero esto rara vez es necesario para resolver y ya no se sigue.
Algunas de las celdas del rompecabezas se pintarán de negro; el objeto del rompecabezas es determinar para cada celda si debe pintarse o dejarse en blanco (quedando en blanco). En la práctica, a menudo es más fácil marcar celdas conocidas como "en blanco" de alguna manera, por ejemplo, colocando un punto en el centro de la celda.
Las siguientes reglas determinan qué celdas son cuáles:
- Regla 1: Las celdas pintadas nunca pueden estar conectadas ortogonalmente (no pueden compartir un lado, aunque pueden tocarse en diagonal).
- Regla 2: Todos los glóbulos blancos deben estar interconectados (formar un solo poliomino ).
- Regla 3: Un número indica exactamente cuántas celdas pintadas debe haber en esa habitación en particular.
- Regla 4: Una habitación que no tiene número puede contener cualquier número de celdas pintadas, o ninguna.
- Regla 5: Cuando se forme una línea recta (ortogonal) de celdas blancas conectadas, no debe contener celdas de más de dos habitaciones; en otras palabras, cualquier línea de celdas blancas que conecte tres o más habitaciones está prohibida.
Métodos de solución
Tenga en cuenta que las dos primeras reglas también se aplican (por ejemplo) a los acertijos de Hitori y, por lo tanto, estos acertijos comparten algunos de sus métodos de resolución:
- Si se descubre que una celda está pintada, se sabe inmediatamente que las cuatro celdas adyacentes (ortogonalmente) deben ser blancas (de la Regla 1).
- Una sección de glóbulos blancos contiguos (ortogonalmente) no se puede cortar del resto de la cuadrícula (de la Regla 2). Las celdas negras no pueden formar una división diagonal a través de la cuadrícula ni un circuito cerrado; cualquier celda que complete un "cortocircuito" de este tipo debe ser blanca.
Los acertijos más complejos requieren combinar la Regla 1 y la Regla 2 para progresar sin adivinar; la clave es reconocer dónde las celdas deben asumir uno de los dos patrones a cuadros y uno conduce a un cortocircuito.
Las reglas restantes diferencian a Heyawake de otros acertijos de "dinastía":
- La regla 5 es la regla definitoria del rompecabezas; Se deben colocar celdas negras para evitar cualquier línea (ortogonal) de celdas blancas que crucen los bordes de dos habitaciones ("llaves").
- Las salas numeradas suelen proporcionar a los solucionadores un lugar de partida, entre otras deducciones. Los siguientes son los ejemplos más simples 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 sería desconectar 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 contenga un '2' debe tener pintadas las dos celdas de los extremos, ya que una celda central pintada forzaría una infracción de la regla 1. De manera más general, una habitación de 1 × (2 n −1) que contenga una n debe tener cada otra celda dentro de ella pintada.
- Una habitación de 3 × 3 que contenga un '5' debe tener un patrón a cuadros, con celdas pintadas en todas las esquinas y en el centro.
Variantes
- Heyawacky se juega como Heyawake, pero las habitaciones no son necesariamente rectangulares. Las líneas ortogonales de glóbulos blancos 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 se juega como Heyawake, pero las pistas indican si el patrón de celdas negras en una habitación es rotacionalmente simétrico alrededor de su centro o no.
Complejidad computacional
Se ha analizado la complejidad computacional de Heyawake: [1] decidir para una instancia determinada 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 acertijo es tan difícil de resolver como el problema de satisfacibilidad booleano , que es un problema difícil bien estudiado en informática .
Ver también
Notas
- ↑ M. Holzer, O. Ruepp (2007)
Referencias
- Holzer, Markus; Ruepp, Oliver (2007). "Los problemas del diseño de interiores: un análisis de la complejidad del juego Heyawake" (PDF) . Actas, 4ta Conferencia Internacional sobre Diversión con Algoritmos, LNCS 4475 . Springer, Berlín / Heidelberg. págs. 198–212. doi : 10.1007 / 978-3-540-72914-3_18 . ISBN 978-3-540-72913-6.