Algún algoritmo para el juego "Voltear todo" (Light Out)?

Question

en este juego: http://www.mathsisfun.com/games/allout.html La función resolver puede resolver cualquier caso, sin importar cómo "abuse" de la placa original. Por favor, dime el algoritmo para resolver este juego. Intenté pensar durante días pero todavía no encontré ninguna pista para resolver todos los casos.

bien, después de leer algunas respuestas y comentarios (y tienen un rápido vistazo a la luz fuera de juego), amplío mi pregunta:

¿El juego diferente si ampliar el tamaño de la red (como a 25x25)? Todavía cualquier algoritmo posible para resolver cualquier caso, en aceptable tiempo (< 2s)?

Answer 1

Este juego es más comúnmente conocido como Lights Out, y tiene una serie de soluciones elegantes, todas basadas en algunas matemáticas estándar pero algo avanzadas. No los describiré todos aquí, pero si buscas un poco de Google puedes encontrar todo tipo de explicaciones que van desde procedimientos sencillos hasta transformaciones en álgebra lineal o teoría de grupos. Un par de enlaces:

http://www.hamusutaa.com/pilot/solution.html

http://www.ripon.edu/academics/macs/summation/2010/articles/M.%20Madsen%20-%20Lights%20Out.pdf

http://people.math.sfu.ca/~jtmulhol/math302/notes/24-Lights-Out.pdf

Editar: Re: su segunda pregunta. El algoritmo presentado en el segundo enlace que publiqué puede resolver un tablero n x n en O (n^6) tiempo, lo que significa que debería ser capaz de resolver rápidamente un tablero de 25 x 25.

Answer 2

Como la mayoría de los problemas de IA "juego", hay un enfoque general:

Implementar una estructura de árbol donde cada nodo es el estado del juego y los niños de los estados representan transiciones entre dichos estados.

Haga esto como una búsqueda de amplitud (primero en profundidad, bien si mantiene un registro de los estados pasados ​​que ha visto y se niega a volver a visitarlos, y no le importa encontrar la solución óptima) o venga con una heurística optimista que le permite usar A *. Una heurística bastante horrible en la que puedo pensar es "La cantidad de círculos que deben voltearse para ganar el rompecabezas, dividido por 5". No estoy seguro de si hay uno mejor; Yo estaría interesado en escuchar la entrada de la gente en esta (Tenga en cuenta que tiene que ser optimistas, es decir, la heurística puede, no exceso de calcular el número de movimientos necesarios.)

entrar en más detalles es un poco tonto ya este es un tema tan importante, y además de eso, es bastante simple si sabes cómo hacer una búsqueda de amplitud o A *.

Answer 3

Hay un método bien conocido para resolver este problema. Deje x_1, ..., x_n ser variables que correspondan a si presiona el botón n'th como parte de la solución y deja que a_1, ..., a_n sea el estado inicial.

Digamos que se está resolviendo un problema de 3x3, y las variables se establecen así:

x_1 x_2 x_3 
x_4 x_5 x_6 
x_7 x_8 x_9 

y este estado inicial es:

a_1 a_2 a_3 
a_4 a_5 a_6 
a_7 a_8 a_9 

Ahora, se puede anotar algunas ecuaciones (en el módulo aritmético 2) que la solución debe satisfacer.Básicamente se trata de codificar la regla sobre qué interruptores hacen que una luz determinada se encienda.

a_1 = x_1 + x_2 + x_4 
a_2 = x_1 + x_2 + x_3 + x_5 
... 
a_5 = x_2 + x_4 + x_5 + x_6 + x_8 
... 
a_9 = x_6 + x_8 + x_9 

Ahora puede usar la eliminación gaussiana para resolver este conjunto de ecuaciones simultáneas. Debido a que está trabajando en el módulo aritmético 2, en realidad es un poco más fácil que las ecuaciones simultáneas sobre los números reales. Por ejemplo, para deshacerse de x_1 en la segunda ecuación, simplemente agrega la primera ecuación.

a_1 + a_2 = (x_1 + x_2 + x_4) + (x_1 + x_2 + x_3 + x_5) = x_3 + x_4 + x_5 

Específicamente, aquí está el algoritmo de eliminación de Gauss en la aritmética de módulo 2:

• elegir una ecuación con una x_1 en ella. Nombralo E_1.
• Agregue E_1 a cualquier otra ecuación sin nombre con una x_1 en ella.
• Repita para x_2, x_3, ...., x_n.

Ahora, E_n es una ecuación que solo contiene x_n. Puede sustituir el valor de x_n que obtiene de esto en las ecuaciones anteriores. Repita para E_ {n-1}, ..., E_1.

En general, esto resuelve el problema en O (n^3) operaciones.

Aquí hay algunos códigos.

class Unsolvable(Exception): 
    pass 

def switches(vs): 
    n, m = len(vs), len(vs[0]) 
    eqs = [] 
    for i in xrange(n): 
     for j in xrange(m): 
      eq = set() 
      for d in xrange(-1, 2): 
       if 0 <= i+d < n: eq.add((i+d)*m+j) 
       if d != 0 and 0 <= j+d < m: eq.add(i*m+j+d) 
      eqs.append([vs[i][j], eq]) 

    N = len(eqs) 
    for i in xrange(N): 
     for j in xrange(i, N): 
      if i in eqs[j][1]: 
       eqs[i], eqs[j] = eqs[j], eqs[i] 
       break 
     else: 
      raise Unsolvable() 
     for j in xrange(i+1, N): 
      if i in eqs[j][1]: 
       eqs[j][0] ^= eqs[i][0] 
       eqs[j][1] ^= eqs[i][1] 

    for i in xrange(N-1, -1, -1): 
     for j in xrange(i): 
      if i in eqs[j][1]: 
       eqs[j][0] ^= eqs[i][0] 
       eqs[j][1] ^= eqs[i][1] 
    return [(i//m,i%m) for i, eq in enumerate(eqs) if eq[0]] 

print switches(([1, 0, 0], [0, 1, 0], [0, 0, 1], [0, 0, 0])) 

Le da el estado inicial una fila a la vez. Devuelve los interruptores que necesita presionar para apagar todas las luces.

Esto resuelve un problema de 50x50 en menos de medio segundo en mi computadora portátil.