Apaga el algoritmo del juego

Es una tarea. Tengo que diseñar y apagar el juego usando la descripción de retroceso a continuación.

El juego consiste en una cuadrícula de luces de 5 por 5; cuando se inicia el juego, se enciende un conjunto de estas luces (al azar, o uno de un conjunto de patrones de rompecabezas almacenados). Al presionar una de las luces, se activará y desactivará las cuatro luces adyacentes a ella. (Los vecinos diagonales no se ven afectados.) El juego proporciona un acertijo: dada alguna configuración inicial donde algunas luces están encendidas y otras apagadas, el objective es apagar todas las luces, preferiblemente en el menor número de presiones de botón posible.

Mi enfoque es ir del 1 al 25 y verificar si todas las luces están apagadas o no. De lo contrario, verificaré de 1 a 24 y así sucesivamente hasta que llegue a 1 o encuentre la solución. No, si no hay solución, comenzaré de 2 a 24 y seguiré el proceso anterior hasta llegar a 2 o encontrar la solución.

Pero a través de esto, no estoy obteniendo el resultado? por ejemplo, la luz a (0,0) (1,1) (2,2) (3,3) (4,4) está ENCENDIDA?

Si alguien necesita código, puedo publicarlo.

¿Alguien puede decirme cuál es el enfoque correcto al usar el retroceso para resolver este juego?

Gracias.

Hay un algoritmo estándar para resolver este problema que se basa en la eliminación de Gauss sobre GF (2). La idea es establecer una matriz que represente el botón presiona un vector de columna que representa las luces y luego usar técnicas de simplificación de matriz estándar para determinar qué botones presionar. Se ejecuta en tiempo polinomial y no requiere ningún retroceso.

Tengo una implementación de este algoritmo que incluye una descripción matemática de cómo funciona disponible en mi sitio personal. ¡Espero que le sea útil!

Editar : si se ve obligado a utilizar el rastreo hacia atrás, puede usar los siguientes hechos para hacerlo:

  • Cualquier solución nunca presionará el mismo botón dos veces, ya que hacerlo cancelaría un movimiento anterior.
  • Cualquier solución presiona el primer botón o no lo hace.

Teniendo en cuenta este enfoque, puede resolver esto utilizando el rastreo retroactivo utilizando un algoritmo recursivo simple que realiza un seguimiento del estado actual de la placa y de los botones sobre los que ya ha tomado decisiones:

  • Si ha decidido sobre cada botón, luego regrese si el tablero está resuelto o no.
  • De otra manera:
    • Intenta presionar el siguiente botón y ver si el tablero se puede resolver de forma recursiva desde allí.
    • Si es así, devuelve el éxito.
    • De lo contrario, trate de no presionar el siguiente botón y ver si el tablero se puede resolver de forma recursiva desde allí.
    • Si es así, devuelve el éxito. De lo contrario, devuelve una falla.

Esto explorará un espacio de búsqueda de tamaño 2 25 , que es de aproximadamente 32 millones. Eso es grande, pero no insuperablemente grande.

¡Espero que esto ayude!

Retroceder significa:

Incrementally build a solution, throwing away impossible solutions. 

Aquí hay un enfoque que utiliza el hecho de que hay una localidad de entradas y salidas (presionar un botón afecta el cuadrado a su alrededor).

 problem = GIVEN solutions = [[0],[1]] // array of binary matrix answers (two entries, a zero and a one) for (problemSize = 1; problemSize <= 5; problemSize++) { newSolutions = []; foreach (solutions as oldSolution) { candidateSolutions = arrayOfNByNMatriciesWithMatrixAtTopLeft(min(5,problemSize+1), oldSolution); // size of candidateSolutions is 2^((problemSize+1)^2 - problemSize^2) // except last round candidateSolutions == solutions foreach (candidateSolutions as candidateSolution) { candidateProblem = boardFromPressingButtonsInSolution(candidateSolution); if (compareMatrix(problem, candidateProblem, 0, 0, problemSize, problemSize)==0) newSolutions[] = candidateSolution; } } solutions = newSolutions; } return solutions; 

Como ya se sugirió, primero debe formar un conjunto de ecuaciones simultáneas.

Lo primero que debe tenerse en cuenta es que un botón de luz en particular debe presionarse como máximo una vez porque no tiene sentido activar el conjunto de luces dos veces.

 Let Aij = Light ij Toggled { Aij = 0 or 1 } 

Habrá 25 de esas variables.

Ahora, para cada una de las luces, puedes formar una ecuación parecida a

 summation (Amn) = 0. { Amn = 5 light buttons that toggle the light mn } 

Entonces tendrá 25 variables y 25 incógnitas. Puedes resolver estas ecuaciones simultáneamente.

Si necesita resolverlo utilizando retroceso o recursión, puede resolver las ecuaciones de esa manera. Simplemente asum un valor inicial de variables, vea si satisfacen todas las ecuaciones. Si no, entonces retrocede.

La solución ingenua

En primer lugar, necesitará una forma de representar el estado de la placa y una stack para almacenar todos los estados. En cada paso, haga una copia de la placa, cambiada al nuevo estado. Compare ese estado con todos los estados del tablero que ha encontrado hasta ahora. Si no lo ha visto, presione ese estado en la parte superior de la stack y continúe con el próximo movimiento. Si lo has visto, intenta el próximo movimiento. Cada nivel deberá probar todos los 64 movimientos posibles antes de mostrar el estado de la stack (retroceso). Querrá utilizar recursividad para administrar el estado del siguiente movimiento para verificar.

Hay a lo sumo 2 64 configuraciones posibles de la placa, lo que significa que usted podría tener una larga cadena de estados únicos y aún quedarse sin memoria. (Como referencia, 1 GB tiene 2 30 bytes y necesita un mínimo de 8 bytes para almacenar la configuración de la placa). No es probable que este algoritmo finalice durante la vida útil del universo conocido.

Debe hacer algo inteligente para reducir su espacio de búsqueda …

Primera búsqueda codiciosa

Puede hacerlo mejor buscando primero en los estados que están más cerca de la configuración resuelta. En cada paso, clasifique los movimientos posibles en orden desde la mayoría de las luces apagadas hasta las menos luces apagadas. Itera en ese orden. Esto debería funcionar razonablemente bien, pero no se garantiza que obtenga la solución óptima.

No todos los rompecabezas de Lights-Out son solucionables

Independientemente del algoritmo que utilice, es posible que no haya una solución, lo que significa que puede buscar por siempre (o varios billones de años, al menos) sin encontrar una solución.

Deberá verificar la solvanibilidad de la placa (que es un algoritmo mucho más rápido) antes de perder el tiempo tratando de encontrar una solución.