Light Up (en japonés : 美術館bijutsukan , galería de arte), también llamado Akari , es un acertijo lógico de determinación binaria publicado por Nikoli . A partir de 2011, Nikoli ha publicado tres libros que consisten en su totalidad en rompecabezas Light Up .
Reglas
Light Up se juega en una cuadrícula rectangular de celdas blancas y negras. El jugador coloca bombillas en las celdas blancas de modo que no se enciendan dos bombillas entre sí, hasta que se ilumine toda la cuadrícula. Una bombilla envía rayos de luz horizontal y verticalmente, iluminando toda su fila y columna a menos que su luz esté bloqueada por una celda negra. Una celda negra puede tener un número de 0 a 4, lo que indica cuántas bombillas deben colocarse adyacentes a sus cuatro lados; por ejemplo, una celda con un 4 debe tener cuatro bulbos alrededor, uno a cada lado, y una celda con un 0 no puede tener un bulbo al lado de ninguno de sus lados. Una celda negra sin numerar puede tener cualquier cantidad de bombillas adyacentes o ninguna. Los bulbos colocados diagonalmente adyacentes a una celda numerada no contribuyen al recuento de bulbos.
Métodos de solución
Un punto de partida típico en la solución de un rompecabezas Light Up es encontrar una celda negra con un 4, o una celda con un número más pequeño que esté bloqueada en uno o más lados (por ejemplo, un 3 contra una pared o un 2 en una esquina) y, por lo tanto, solo tiene una configuración de bombillas circundantes. Después de este paso, se pueden iluminar otras celdas numeradas en uno o más lados, reduciendo las posibles configuraciones de bombilla a su alrededor y, en algunos casos, haciendo posible solo una configuración.
Otra técnica común es buscar una celda que aún no esté encendida y determinar si solo hay una celda posible en la que se pueda colocar una bombilla para encenderla.
Cuando no está claro dónde colocar una bombilla, también se pueden colocar puntos en las celdas blancas que no pueden tener bombillas, como alrededor de un 0 o en lugares donde una bombilla crearía una contradicción. Por ejemplo, una bombilla colocada en diagonal adyacente a un 3 bloqueará dos de sus celdas circundantes, haciendo imposible tener tres bombillas alrededor; por lo tanto, las celdas diagonales alrededor de un 3 nunca pueden tener luces y siempre pueden estar punteadas. De manera similar, se pueden colocar puntos en lugares donde una bombilla "atraparía" a otra celda apagada, haciendo imposible encenderla sin romper las reglas.
Las técnicas más avanzadas tienden a centrarse en diferentes combinaciones de pistas. Dos 3 que están separados por un espacio, por ejemplo, sin nada entre ellos o con los otros dos lados de la celda en el medio, deben tener una bombilla en ese espacio, y los dos espacios al lado de los dos tres, en la línea que los une. . Si no, entonces uno tendría dos bombillas iluminándose entre sí. Además, de esta deducción, las cuatro celdas restantes que rodean a los tres deben contener dos bombillas. Tenga en cuenta que como los cuatro espacios están dispuestos en dos filas sin nada entre ellas, se debe tener una bombilla en cada fila, de modo que se puedan marcar todos los demás espacios en esas filas como vacíos.
Otro patrón bastante común es un 1 adyacente en diagonal a un 2, con uno de los espacios al lado del 2 pero no adyacente al 1, ya sea vacío o con paredes. Como máximo, se puede colocar una bombilla en las dos celdas comunes a las dos pistas, por lo que la última bombilla debe ir en el último espacio alrededor de las 2. Ahora, se sabe que hay exactamente una bombilla en esas celdas, por lo que las otras celdas junto al 1 deben estar vacíos.
Complejidad computacional
Determinar si un rompecabezas de Light Up dado se puede resolver es NP-completo . [1] Esto se demuestra mediante una reducción de tiempo polinomial de Circuit-SAT , que se sabe que es NP-completo, a los rompecabezas Light Up.
Una variación del rompecabezas Light Up original en el que hay paredes sin números más paredes con un número determinado, por lo que 0, 1, 2, 3 o 4 (llamamos a estas variaciones Akari-), también se han investigado en complejidad. Se muestra, mediante una reducción de tiempo polinomial de Circuit-SAT, que Akari-1, Akari-2 y Akari-3 son NP-completos; para Akari-4 y rompecabezas sin números, se muestra que estos están en P; Hasta ahora, Akari-0 no está categorizado. [2]
Ver también
- Lista de tipos de rompecabezas Nikoli
- Categoría: Rompecabezas de lógica
Referencias
- ^ McPhail, Brandon (28 de febrero de 2005). "Light Up es NP-completo" (PDF) .
- ^ Pulles, Bram (9 de enero de 2021). "Análisis de Akari" (PDF) . Consultado el 27 de mayo de 2021 .