Light Up ( japonés : 美術館bijutsukan , galería de arte), también llamado Akari (明かり, luz) es un acertijo de lógica de determinación binaria publicado por Nikoli . A partir de 2011, Nikoli ha publicado tres libros que consisten íntegramente en rompecabezas Light Up .
Light Up se juega en una cuadrícula rectangular de celdas blancas y negras. El jugador coloca bombillas en celdas blancas de modo que no haya dos bombillas que se iluminen entre sí, hasta que toda la cuadrícula esté iluminada. 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 del 0 al 4, que indica cuántas bombillas se deben colocar adyacentes a sus cuatro lados; por ejemplo, una celda con un 4 debe tener cuatro bombillas a su alrededor, una a cada lado, y una celda con un 0 no puede tener una bombilla al lado de ninguno de sus lados. Una celda negra sin numerar puede tener cualquier número de bombillas adyacentes o ninguna. Las bombillas colocadas diagonalmente adyacentes a una celda numerada no contribuyen al recuento de bombillas.
Un punto de partida típico en la solución de un rompecabezas de Light Up es encontrar una celda negra con un 4, o una celda con un número menor 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 tiene sólo 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 bombillas 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 iluminarla.
Cuando no está claro dónde colocar una bombilla, también se pueden colocar puntos en 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 diagonalmente adyacente a un 3 bloqueará dos de las celdas circundantes, haciendo imposible tener tres bombillas a su alrededor; por lo tanto, las celdas diagonales alrededor de un 3 nunca pueden tener luces y siempre pueden tener puntos. De manera similar, se pueden colocar puntos en lugares donde una bombilla "atraparí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 a 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. . De lo contrario, tendríamos 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 ellos, se debe tener una bombilla en cada fila, para poder marcar todos los demás espacios en esas filas como vacíos.
Otro patrón bastante común es un 1 diagonalmente adyacente a un 2, con uno de los espacios al lado del 2 pero no adyacente al 1 vacío o tapiado. 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 del 2. Ahora, se sabe que hay exactamente una bombilla en esas celdas, por lo que las otras celdas al lado del 1 ambos deben estar vacíos.
Determinar si un determinado rompecabezas de Light Up tiene solución es NP-completo . [1] Esto se demuestra mediante una reducción de tiempo polinomial desde Circuit-SAT , que se sabe que es NP-completo, hasta los rompecabezas Light Up.
También se han investigado en complejidad variaciones 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- ). 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 acertijos sin números se muestra que están en P; Akari-0 hasta el momento no está categorizado. [2]
