Colegio Particular Andino
Educacion Para El Trabajo
Heyawake
Reglas
Heyawake se juega en una cuadrícula rectangular de celdas
sin tamaño estándar; La cuadrícula se divide en "habitaciones"
rectangulares de diversos 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, todas las habitaciones estaban numeradas, 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 se debe pintar o si
se debe dejar en blanco (el blanco restante). En la práctica, a menudo es más
fácil marcar las celdas "en blanco" conocidas de alguna manera, por
ejemplo, colocando un punto en el centro de la celda.
Las siguientes reglas determinan que celdas son cuales:
Regla 1: Las células pintadas nunca pueden estar conectadas
ortogonalmente (pueden no compartir un lado, aunque pueden tocarse en
diagonal).
Regla 2: todas las células blancas deben estar
interconectadas (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 tenga número puede contener
cualquier número de celdas pintadas, o ninguna.
Regla 5: cuando se forma una línea recta (ortogonal) de
glóbulos blancos conectados, no debe contener celdas de más de dos
habitaciones; en otras palabras, cualquier línea de células 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 a (por ejemplo) los rompecabezas Hitori , y por lo tanto estos
rompecabezas comparten algunos de sus métodos de resolución:
Si se descubre que una celda está pintada, se sabe de
inmediato que todas las cuatro celdas adyacentes (ortogonalmente) deben ser
blancas (de la Regla 1).
Una sección de las celdas blancas contiguas (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
bucle cerrado; cualquier celda que complete tal "cortocircuito" debe
ser blanca en su lugar.
Los rompecabezas más complejos requieren combinar la Regla 1
y la Regla 2 para avanzar sin adivinar; la clave es reconocer dónde las celdas
deben asumir uno de dos patrones a cuadros y uno conduce a un cortocircuito.
Las reglas restantes diferencian a Heyawake de otros
rompecabezas de la "dinastía":
La regla 5 es la regla que define el rompecabezas; las
celdas negras deben colocarse para evitar cualquier línea (ortogonal) de
glóbulos blancos que crucen los bordes de dos habitaciones
("llaves").
Las habitaciones numeradas suelen proporcionar a los
solucionadores un punto de partida, entre otras deducciones. Los siguientes son
los ejemplos más simples de salas 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
la segunda casilla pintada en diagonal hacia afuera desde la esquina. Como los
cuadrados pintados pueden no 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 la 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, para Razones similares a las anteriores.
Una sala de 1 × 3 que contenga un '2' debe tener las dos
celdas finales pintadas, ya que una celda central pintada forzaría una
infracción de la regla 1. Más generalmente, una sala 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, tales líneas no
pueden extenderse más de un límite de región.
Simetría 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
La complejidad computacional de Heyawake ha sido analizada:
[1] decidir para una instancia dada de Heyawake si existe una solución para el
rompecabezas es NP-completo . Una interpretación de este resultado teórico en
términos sencillos es que este enigma es tan difícil de resolver como el
problema de satisfacción booleana , que es un problema difícil bien estudiado
en informática .
Ver tambien
Lista de tipos de rompecabezas Nikoli
