Algorytm dla gry "Przerzuć wszystkie" (Light Out)?

Question

w tej grze: http://www.mathsisfun.com/games/allout.html Funkcja rozwiązania może rozwiązać każdy przypadek, bez względu na to, jak "wykorzystujesz" oryginalną planszę. Proszę, powiedz mi algorytm do rozwiązania tej gry. Próbowałem myśleć przez kilka dni, ale wciąż nie znalazłem żadnej wskazówki, aby rozwiązać wszystkie przypadki.

OK, po przeczytaniu niektórych odpowiedzi i komentarzy (i rzucić okiem na światło z gry), ja poszerzyć moje pytanie:

Czy gra inaczej, gdybym powiększyć rozmiar siatki (jak na 25x25)? Wciąż każdy możliwy algorytm do rozwiązania dowolnego przypadku o numerze, w akceptowalnym czasie (< 2s)?

Answer 1

Ta gra jest bardziej znana jako Lights Out i ma wiele eleganckich rozwiązań opartych na pewnej standardowej, ale nieco zaawansowanej matematyce. Nie będę ich tutaj opisywał, ale jeśli ty Google trochę, możesz znaleźć wszystkie rodzaje wyjaśnień, od prostej procedury do transformacji do algebry liniowej lub teorii grup. Kilka linków:

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: drugie pytanie. Algorytm przedstawiony w opublikowanym drugim łączu może rozwiązać tablicę n x n w czasie O (n^6), co oznacza, że ​​powinieneś być w stanie szybko rozwiązać tablicę 25 x 25.

Answer 2

Podobnie jak większość AI problemów „gra”, istnieje ogólne podejście:

Wdrożenie struktury drzewa, gdzie każdy węzeł jest stan gry i dzieci państw reprezentują przejścia między tymi państwami.

Wykonaj to jako pierwsze wyszukiwanie (głębokość - najpierw OK, jeśli przechowujesz rejestr wcześniejszych stanów, które widziałeś i odmawiasz ponownego ich przeglądania, a nie zależy Ci na znalezieniu optymalnego rozwiązania) lub przyjdziesz z optymistyczną heurystyką, która pozwala używać A *. Zupełnie okropną heurystyką, jaką mogę wymyślić, jest "Liczba kół, które trzeba odwrócić, aby wygrać układankę podzieloną przez 5". Nie jestem pewien, czy jest lepszy; Byłbym zainteresowany wysłuchaniem opinii ludzi na ten temat (pamiętaj, że musi to być optymistyczne, to znaczy, że heurystyka nigdy nie może przeliczyć na liczbę wymaganych ruchów).

Przejście w szczegóły jest trochę głupie, ponieważ jest to bardzo duży temat, a poza tym jest całkiem proste, jeśli wiesz, jak wykonać szerokie pierwsze wyszukiwanie lub A *.

Answer 3

Istnieje dobrze znana metoda rozwiązania tego problemu. Niech x_1, ..., x_n będą zmiennymi odpowiadającymi temu, czy naciśniesz n-ty przycisk jako część rozwiązania, i niech a_1, ..., a_n będzie stanem początkowym.

Powiedzmy jesteś rozwiązywania problemu 3x3, a zmienne są ustawione tak:

x_1 x_2 x_3 
x_4 x_5 x_6 
x_7 x_8 x_9 

i stan początkowy jest:

a_1 a_2 a_3 
a_4 a_5 a_6 
a_7 a_8 a_9 

Teraz można napisać niektóre równania (w arytmetycznym modulo 2), które rozwiązanie musi spełniać.Zasadniczo koduje regułę dotyczącą przełączników powodujących przełączanie określonego światła.

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 

Teraz możesz użyć eliminacji gaussowskiej do rozwiązania tego zestawu równoczesnych równań. Ponieważ pracujesz w arytmetycznym module modulo 2, jest to trochę łatwiejsze niż równoczesne równania na liczbach rzeczywistych. Na przykład, aby pozbyć się x_1 w drugim równaniu, po prostu dodaj do niego pierwsze równanie.

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

szczególności tutaj Gaussa algorytm eliminacja arytmetyczna modulo 2:

• Pick równania z X_1 w nim. Nazwij go E_1.
• Dodaj E_1 do każdego innego równania bez nazwy z elementem x_1.
• Powtórz dla x_2, x_3, ...., x_n.

Teraz E_n jest równaniem, które zawiera tylko x_n. Możesz zastąpić wartość x_n otrzymaną od tego we wcześniejszych równaniach. Powtórz dla E_ {n-1}, ..., E_1.

Ogólnie rzecz biorąc, rozwiązuje to problem w operacjach O (n^3).

Oto kod.

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

Podajesz stan początkowy w rzędzie na raz. Zwraca przełączniki, które należy nacisnąć, aby wyłączyć wszystkie światła.

Rozwiązuje to problem 50x50 w mniej niż pół sekundy na moim laptopie.