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