Estrategia para resolver el puzzle "Luces apagadas"

No tengo una estrategia, pero aquí hay algunos datos sobre el tablero 5×5:

• El orden no cuenta. Hacer clic en una baldosa A, luego hacer clic en una baldosa B es exactamente lo mismo que hacer clic en la baldosa B, luego hacer clic en la baldosa A - o hacer clic en la baldosa A, luego en la baldosa B, luego en la baldosa A otra vez, luego tal vez voltear alguna otra baldosa, luego la baldosa B.
  En resumen, un azulejo es o no es parte de la solución (un conjunto desordenado de fichas que debes cambiar). Ir en círculos intentando los mismos movimientos una y otra vez no te lleva a ninguna parte.

  
  Tan cerca y tan lejos

• Menos no es más. Intentar minimizar la cantidad de celdas iluminadas/no iluminadas puede ser contraproducente (véase la imagen anterior). En su lugar, debes intentar llevar el juego a una configuración que puedas reconocer y resolver de memoria.

• Los juegos simétricos tienen soluciones simétricas. Tenlo en cuenta: refleja tus movimientos y la complejidad del juego bajará considerablemente.

• Las soluciones no son únicas, y el azulejo central nunca es necesario. Aunque puede facilitar la resolución de un rompecabezas, es aparece que todos los juegos resolubles pueden ser resueltos sin la ficha central.

La siguiente solución funciona para cada cuadrícula m × n:

Piensa en la cuadrícula dada como un vector en un espacio vectorial de m × n dimensiones. Cada valor es 1 (si la luz está encendida) o 0 (si la luz está apagada). Ahora puedes pensar en cada empuje de celda como un vector en este espacio vectorial. Como puedes empujar m x n celdas diferentes, tienes m x n vectores diferentes. Si cambian algo en una celda, el valor es 1, sino 0.

Como ha mencionado badp, sólo es interesante si hay que pulsar un botón o no. No hace falta mirar el orden, ni pulsar un botón más de una vez. Así que tienes una ecuación

vector para su cuadrícula = a_1 x vector de celda1 + a_2 x vector de celda_2 + ... a_mn x vector de celda_mn a_1, a_2, ..., a_mn es 0 o 1.

Como tienes m x n variables (a_1 ... a_mn) y m x n ecuaciones (las filas de los vectores) puedes resolverlo con Eliminación gaussiana .

Si es usted alemán, quizá le interese leer " Tarea 2, 30º Concurso Nacional de Informática "

Jugando con diferentes tamaños de juego encontré algunas cosas que despertaron mi curiosidad.

En primer lugar, el caso 4 x 4 es trivial: persigue los cuadrados iluminados y se resuelve en la primera pasada. Los casos de 2 x 2 y 3 x 3 son (curiosamente) menos triviales, pero no exactamente difíciles.

En segundo lugar, el caso de 9 x 9 es casi trivial. Si numeramos las columnas del 1 al 9 (de izquierda a derecha en mi cabeza, pero cualquiera de las dos está bien, por supuesto), entonces sólo hay dos resultados después de la primera persecución: o bien se resuelve a la primera (como el caso de 4 x 4) o, alternativamente, las casillas iluminadas en la fila inferior son 1, 3, 5, 7, 9 y si ahora haces clic en esas casillas en la fila superior y las persigues, se resuelve.

El caso de 7 x 7 parece ceder a una estrategia muy simple que me llevó una docena de juegos para detectar. La primera persecución acaba con todo tipo de configuraciones diferentes en la línea de fondo, demasiadas para catalogarlas de forma sensata. Sin embargo, después de esa primera persecución, puedo elegir de forma fiable la línea superior de la siguiente manera: para cada casilla i de la fila inferior que esté iluminada hay que hacer clic en las casillas de la fila superior i-1, i , i+1. Puedes hacer clic en ellas según esa regla o escribirla para toda la fila y luego sólo hacer clic en las casillas que aparecen un número impar de veces - lo mismo pero en papel. Después de eso persigue las casillas y el trabajo está hecho. Está claro que si la casilla 1 o la 7 están encendidas, los resultados son 1,2 o 6,7, ya que no hay 0 ni 8. Sigue funcionando.

En este punto he probado esta estrategia en algunas otras dimensiones, 6, 8, 11, 12, 16 - y no funciona en ellos por lo que es peculiar al caso de 7 x 7 o tal vez la estrategia de 7 x 7 es un caso especial de un método más general.

He comprobado satisfactoriamente que ninguna de las soluciones dadas aquí son válidas. De hecho, hay 5x5 casos que son totalmente irresolubles. A continuación te explico cómo puedes comprobarlo tú mismo: Coge una baraja de cartas y reparte una matriz usando cartas rojas para indicar una luz encendida y cartas negras para indicar luces apagadas. Reparte una matriz del tamaño que quieras y luego prueba la técnica que se indica aquí. He probado con una matriz de 5x5 y me ha salido una fila inferior que NO coincide con la que se ha publicado aquí. Eso significa que la matriz de 5x5 es irresoluble usando el algoritmo de "seguir las luces". Otro sitio afirma que la matriz de 6x6 es siempre resoluble. De nuevo, utilizando el método descrito anteriormente - repartiendo cartas para crear la matriz y utilizando el algoritmo "sigue las luces", encontré varias matrices de 6x6 que no eran resolubles utilizando esta técnica. Puedes poner todas las matemáticas que quieras pero en la práctica, LAS SOLUCIONES DADAS AQUÍ NO FUNCIONAN PARA TODAS LAS MATRICES.

Esto se debe a que sólo el 25% de los juegos son resolubles. Los que son resolubles lo serán con ese método.