Light Up ( en japonés : 美術館bijutsukan , galería de arte), también llamado Akari (明かり, luz) es un rompecabezas de lógica de determinación binaria publicado por Nikoli . A partir de 2011, Nikoli ha publicado tres libros compuestos íntegramente de 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 manera que ninguna de ellas brille una sobre otra 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 sea 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 en cada lado, y una celda con un 0 no puede tener una bombilla junto a ninguno de sus lados. Una celda negra sin numerar puede tener cualquier cantidad de bombillas adyacentes a ella, o ninguna. Las bombillas colocadas en diagonal 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 iluminación 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, tenga solo una configuración de bombillas circundantes. Después de este paso, otras celdas numeradas pueden iluminarse en uno o más lados, lo que reduce las posibles configuraciones de bombillas a su alrededor y, en algunos casos, hace posible solo una configuración.
Otra técnica común es buscar una celda que aún no esté iluminada y determinar si sólo 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 que la rodean, lo que hace imposible tener tres bombillas a su 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" otra celda no iluminada, lo que haría imposible encenderla sin romper las reglas.
Las técnicas más avanzadas tienden a centrarse en diferentes combinaciones de pistas. Por ejemplo, dos 3 que están separados por un espacio, sin nada entre ellos o en los otros dos lados de la celda que hay en el medio, deben tener una bombilla en ese espacio y en los dos espacios que están junto a los dos treses, en la línea que los une. Si no, entonces habría dos bombillas iluminándose entre sí. Además, a partir de esta deducción, las cuatro celdas restantes que rodean a los treses deben contener dos bombillas. Tenga en cuenta que, como los cuatro espacios están dispuestos en dos filas sin nada entre ellos, debe haber una bombilla en cada fila, por lo que puede 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 junto al 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 bien, se sabe que hay exactamente una bombilla en esas celdas, por lo que las otras celdas junto al 1 deben estar vacías.
El hecho de que el rompecabezas tenga una solución única permite deducciones adicionales. Por ejemplo, puede haber una zona larga en un borde, con múltiples cuadrados negros a un espacio de distancia. Colocar la luz junto a cualquiera de ellos iluminará exactamente los mismos cuadrados. Como hay exactamente una solución, una bombilla en cualquiera de ellos sería una contradicción. Todos esos cuadrados pueden eliminarse de inmediato. Otra deducción común implica un rectángulo, sin ninguna de las cuatro esquinas junto a un cuadrado negro numerado. Si las bombillas se colocan en esquinas opuestas, el patrón de iluminación es el mismo en ambos sentidos. Si se garantiza que un lado del rectángulo tiene una luz, las esquinas del otro lado pueden eliminarse, aunque aún no se conozca la ubicación de la luz en el lado garantizado.
Determinar si un rompecabezas 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.
También se han investigado en términos de complejidad las variaciones del rompecabezas Light Up original, en el que hay paredes sin números más paredes con un número determinado, es decir, 0, 1, 2, 3 o 4 (llamamos a estas variaciones Akari- ). Se muestra, mediante una reducción de tiempo polinomial a partir de Circuit-SAT, que Akari-1, Akari-2 y Akari-3 son NP-completos; para Akari-4 y los rompecabezas sin números se muestra que están en P; Akari-0 hasta ahora no está categorizado. [2]
