Qualche algoritmo per il gioco "Flip all" (Light Out)?

Question

in questo gioco: http://www.mathsisfun.com/games/allout.html La funzione di risoluzione può risolvere qualsiasi caso, indipendentemente da come "abusare" della scheda originale. Per favore dimmi l'algoritmo per risolvere questo gioco. Ho provato a pensare per giorni, ma non ho ancora trovato alcun indizio per risolvere tutti i casi.

OK, dopo aver letto alcune risposte e commenti (e hanno un rapido sguardo a luce fuori gioco), espando la mia domanda:

Il gioco diverso se espandere le dimensioni della griglia (come ad 25x25)? Ancora qualche possibile algoritmo per risolvere un qualsiasi caso, in tempo accettabile (< 2s)?

Answer 1

Questo gioco è più comunemente noto come Lights Out e ha un numero di soluzioni eleganti, tutte basate su una matematica standard ma un po 'avanzata. Non li descriverò tutti qui, ma se tu Google un po 'puoi trovare tutti i tipi di spiegazioni che variano da procedure semplici a trasformazioni in algebra lineare o teoria di gruppo. Un po 'di link:

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

Edit: Re: la tua seconda domanda. L'algoritmo presentato nel secondo link che ho postato può risolvere una scheda n x n in tempo O (n^6), il che significa che dovresti essere in grado di risolvere rapidamente una scheda 25 x 25.

Answer 2

Come la maggior parte ai "gioco" problemi, c'è un approccio generale:

implementare una struttura ad albero dove ogni nodo è lo stato del gioco e dei bambini di stati rappresentano transizioni tra questi stati.

O fare questo come una ricerca di ampiezza (profondità-prima OK se si tiene un registro degli stati passati che hai visto e si rifiuta di rivisitarli, e non ti interessa trovare la soluzione ottimale) o vieni con un'euristica ottimistica che consente di utilizzare A *. Una euristica piuttosto orribile che posso pensare è "Il numero di cerchi che devono essere capovolti per vincere il puzzle, diviso per 5." Non sono sicuro che ce ne sia uno migliore; Sarei interessato ad ascoltare le opinioni della gente su questo (Si noti che deve essere ottimistico, cioè, l'euristico non può mai calcolare il numero di mosse necessarie.)

Entrare in maggiori dettagli è un po 'sciocco dal questo è un argomento così grande, e oltre a questo, è piuttosto semplice se sai come fare una ricerca di ampiezza o A *.

Answer 3

C'è un metodo ben noto per risolvere questo problema. Sia x_1, ..., x_n siano le variabili corrispondenti a se si preme il n'th pulsante come parte della soluzione e si lascia a_1, ..., a_n essere lo stato iniziale.

Diciamo che si sta risolvendo un problema 3x3, e le variabili sono impostate in questo modo:

x_1 x_2 x_3 
x_4 x_5 x_6 
x_7 x_8 x_9 

e questo stato iniziale è:

a_1 a_2 a_3 
a_4 a_5 a_6 
a_7 a_8 a_9 

Ora, è possibile scrivere un po ' equazioni (in modulo aritmetico 2) che la soluzione deve soddisfare.Fondamentalmente codifica la regola su quali interruttori fanno accendere una particolare luce.

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 

Ora è possibile utilizzare l'eliminazione gaussiana per risolvere questo insieme di equazioni simultanee. Poiché stai lavorando in aritmetico modulo 2, in realtà è un po 'più semplice delle equazioni simultanee rispetto ai numeri reali. Ad esempio, per eliminare x_1 nella seconda equazione, aggiungi semplicemente la prima equazione ad essa.

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

particolare, qui è l'algoritmo di eliminazione di Gauss in aritmetica modulo 2:

• Prelievo un'equazione con un x_1 in esso. Chiamalo E_1.
• Aggiungere E_1 ad ogni altra equazione senza nome con un x_1 in esso.
• Ripetere per x_2, x_3, ...., x_n.

Ora, E_n è un'equazione che contiene solo x_n. È possibile sostituire il valore per x_n ottenuto da questo nelle equazioni precedenti. Ripeti per E_ {n-1}, ..., E_1.

Nel complesso, questo risolve il problema nelle operazioni O (n^3).

Ecco un po 'di codice.

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])) 

Gli dai lo stato iniziale una riga alla volta. Restituisce gli interruttori che è necessario premere per spegnere tutte le luci.

Questo risolve un problema 50x50 in meno di mezzo secondo sul mio laptop.