Metoda, którą mam zamiar wyjaśnić technicznie, działa dla siatki o dowolnym rozmiarze, ale wymaga pewnej wiedzy, której nie wiem, jak określić od zera. Jeśli chcesz poszukać w Internecie związanych z tym informacji, metoda ta jest ogólnie określana jako „pogoń za światłami” lub „pogoń za światłami”.

Zacznij od naciśnięcia przycisków w drugim rzędzie odpowiadającym komórki w górnym rzędzie, następnie przyciski w trzecim rzędzie odpowiadające podświetlonym komórkom w drugim rzędzie itd. To jest dokładnie to, co już robiłeś, ścigając światła do dolnego rzędu, skąd pochodzi nazwa .

Teraz, jak wiesz, najtrudniejsza część pojawia się, gdy masz pustą siatkę z wyjątkiem dolnego rzędu. W tym momencie sposobem na zakończenie jest naciśnięcie określonych przycisków w pierwszym rzędzie odpowiadającym podświetlonym komórkom w dolnym rzędzie, a następnie ponowne ściganie świateł z góry. Jeśli wcisnąłeś prawe przyciski w pierwszym rzędzie, po zakończeniu drugiego pościgu zagadka zostanie rozwiązana.

O ile wiem, musisz tylko wiedzieć , które przyciski nacisnąć górny rząd, aby odpowiadał konkretnemu wzorowi, który pozostał w dolnym rzędzie po początkowej fazie. Jeśli potrafisz wymyślić metodę określania tych właściwych do pchania na górze, prawdopodobnie możesz użyć bardzo podobnej metody, aby uogólnić to na siatkę dowolnej wielkości. Nie znam na to metody, więc zostawię to jako ćwiczenie czytelnikowi.

W klasycznej wersji układanki 5x5 okazuje się, że są tylko 7 możliwych wzorów w dolnym rzędzie po początkowym ściganiu, więc wymienię tylko 7 możliwych wzorów i odpowiadające im przyciski w pierwszym rzędzie do naciśnięcia dla każdego. Przyciski są ponumerowane od lewej do prawej.

  | -------------------- + ---------- ------- || Po lewej w dolnym rzędzie | Wciśnij górny rząd || -------------------- + ----------------- || 1, 2, 3 | 2 || 1, 2, 4, 5 | 3 || 1, 3, 4 | 5 |
| 1, 5 | 1, 2 || 2, 3, 5 | 1 || 2, 4 | 1, 4 || 3, 4, 5 | 4 || -------------------- + ----------------- |  

Podobne tabele przeglądowe można prawdopodobnie znaleźć w Internecie dla innych rozmiarów.

Nie mam strategii, ale oto kilka faktów na temat planszy 5 × 5:

• Zamówienie się nie liczy. Kliknięcie w kafelek A, a następnie kliknięcie płytki B jest dokładnie tym samym, co kliknięcie płytki B, a następnie kliknięcie płytki A - lub kliknięcie na płytkę A, potem na płytkę B, potem znowu na płytkę A, potem znowu na płytkę A, a potem na odwrócenie innej kafelek, a następnie kafelek B.
  Krótko mówiąc, kafelek jest lub nie jest częścią rozwiązania (nieuporządkowany zestaw kafelków, które musisz zamienić). Kręcenie się w kółko i powtarzanie tych samych ruchów nigdzie Cię nie prowadzi.
  
  
  Tak blisko, a jednak tak daleko…
  
  
• Mniej nie znaczy więcej. Próby zminimalizowania ilości zapalonych / nieoświetlonych komórek mogą przynieść efekt przeciwny do zamierzonego (patrz rysunek powyżej). Zamiast tego powinieneś spróbować doprowadzić grę do konfiguracji, którą możesz rozpoznać i rozwiązać za pomocą pamięci.
• Gry symetryczne mają rozwiązania symetryczne. Pamiętaj: odzwierciedlaj swoje ruchy i grę złożoność znacznie się zmniejszy.
• Rozwiązania nie są wyjątkowe, a środkowy kafelek nigdy nie jest wymagany. Chociaż może to ułatwić rozwiązanie łamigłówki, pojawia się że wszystkie gry do rozwiązania można rozwiązać bez środkowego kafelka.

Poniższe rozwiązanie działa dla każdej siatki m × n:

Pomyśl o danej siatce jako wektorze w wymiarowej przestrzeni wektorowej m × n. Każda wartość to 1 (jeśli światło jest włączone) lub 0 (jeśli światło jest wyłączone). Teraz możesz myśleć o każdym wypchnięciu komórki jako wektorze w tej przestrzeni wektorowej. Ponieważ możesz wypchnąć m x n różnych komórek, masz m x n różnych wektorów. Jeśli coś zmienią w komórce, wartość wynosi 1, w przeciwnym razie 0.

Jak wspomniał badp, jest interesujące tylko wtedy, gdy musisz nacisnąć jeden przycisk, czy nie. Nie ma potrzeby patrzenia na kolejność, nie ma potrzeby wciskania przycisku więcej niż jeden raz, więc masz równanie

wektor dla swojej siatki = a_1 x cellvector1 + a_2 x cellvector_2 + ... a_mn x cellvector_mna_1, a_2, ..., a_mn wynosi 0 lub 1.

Ponieważ masz zmienne mxn (a_1 ... a_mn) i równania mxn (wiersze wektorów), możesz rozwiązać to za pomocą Eliminacja Gaussa.

Jeśli jesteś Niemcem, możesz przeczytać „ Aufgabe 2, 30. Bundeswettberwerb Informatik”

Rozwiązanie problemu zgaśnięcia świateł 6x6:
Dolny rząd układanki 6x6 może zawierać dowolną możliwą kombinację świateł. Dlatego tabela, podobna do tej z Chad Birch dostarczonej powyżej dla układanki 5x5, zawierałaby 63 wiersze. Możesz jednak rozwiązać dowolną łamigłówkę 6x6 Lights Out za pomocą tego małego stolika:

  | -------------------- + ----------------- |
| Po lewej w dolnym rzędzie | Naciśnij górny rząd |
| -------------------- + ----------------- |
| 1 | 1, 3 |
| 2 | 4 |
| 3 | 1, 5 |
| 4 | 2, 6 |
| 5 | 3 |
| 6 | 4, 6 |
| -------------------- + ----------------- |
 

W przypadku dowolnej kombinacji świateł pozostawionych w dolnym rzędzie, po prostu połącz linie z powyższej tabeli, pamiętając, że dwukrotne naciśnięcie przycisku jest równoznaczne z całkowitym nie naciśnięciem przycisku. Na przykład, jeśli dolny wiersz zawiera
4, 5, 6
naciskałbyś
2, 6, 3, 4, 6
lub po prostu
2, 3, 4,
ponieważ dwie szóstki się anulowały.

Bawiąc się różnymi rozmiarami gry, znalazłem kilka rzeczy, które wzbudziły moją ciekawość.

Po pierwsze, przypadek 4 x 4 jest trywialny - ścigaj oświetlone kwadraty w dół i rozwiązuje się przy pierwszym podaniu. Przypadki 2 x 2 i 3 x 3 są (co ciekawe) mniej trywialne, ale nie do końca trudne.

Po drugie, przypadek 9 x 9 jest prawie trywialny. Jeśli ponumerujemy kolumny od 1 do 9 (od lewej do prawej w mojej głowie, ale każdy z nich jest w porządku), to po pierwszym pościgu są tylko dwa wyniki - albo rozwiązuje się go przy pierwszym przejściu (jak w przypadku 4 x 4) lub alternatywnie podświetlone kwadraty w dolnym rzędzie to 1, 3, 5, 7, 9, a jeśli teraz klikniesz te kwadraty w górnym rzędzie i ścigasz je, rozwiązuje.

Przypadek 7 x 7 wydaje się poddaj się bardzo prostej strategii, która zajęła mi kilkanaście gier, aby dostrzec. Pierwszy pościg kończy się najróżniejszymi konfiguracjami w dolnej linii - zbyt dużą, aby rozsądnie skatalogować. Jednak po tym pierwszym pościgu mogę niezawodnie wybrać górną linię w następujący sposób: dla każdego podświetlonego kwadratu i w dolnym rzędzie należy kliknąć kwadraty górnego rzędu i-1, i, i + 1. Możesz po prostu kliknąć je zgodnie z tą zasadą lub wypisać je dla całego wiersza, a następnie kliknąć te pola, które pojawiają się nieparzystą liczbę razy - to samo, ale na papierze. Potem ścigaj kwadraty i zadanie jest skończone. Oczywiście, jeśli świeci się kwadrat 1 lub kwadrat 7, wyniki wynoszą 1, 2 lub 6, 7, ponieważ nie ma 0 ani 8. To nadal działa.

W tym momencie wypróbowałem tę strategię na innych wymiarach , 6, 8, 11, 12, 16 - i nie działa na nich, więc jest charakterystyczny dla przypadku 7 x 7 lub być może strategia 7 x 7 jest szczególnym przypadkiem bardziej ogólnej metody.

Teraz potrzebujemy tylko rozwiązań dla 4x4 z owijaniem. Przykład: {0000} {0000} {0000} {0000} Naciskając lewy górny róg, otrzymujesz: {1101} {1000} {0000} {1000} Tak, wiem, że zacząłem przy wyłączonych wszystkich światłach, ale tak było przykład. Ale aby postępować zgodnie ze wskazówkami, sprawdziłem kilka rozwiązań 7x7 inną podaną tutaj metodą, niektóre są nierozwiązywalne. Obecnie jestem w trakcie tworzenia tabeli dla macierzy 4x4, ponieważ otrzymałem taki, w którym musiałem dwukrotnie lub więcej „ścigać światła”.

  Oto przykład w postaci macierzy .0000000000000000 PRESS TOP LEFT1101100000001000  

Widzicie, co mam na myśli przez zawijanie? Po prostu zapytaj, a ja odpowiem na prasę z opakowaniem.

Ta łamigłówka jest pokazana w misji DDO jako całun i jest bardzo łatwa do rozwiązania dla 3x3 - 4x4 i 5x5

4x4 jest proste, ponieważ rozwiązuje się za jednym przejściem, 3x3 i 5x5 wymagają drugiego przejścia z kilkoma instrukcje

Najpierw dla każdego przejazdu, po prostu kliknij przełącznik bezpośrednio pod dowolnymi świecącymi punktami w górnym wierszu powtarzaj to, aż dojdziesz do dołu

W przypadku 4x4 twój problem zostanie rozwiązany

W przypadku 3x3 pozostawi to zapalone światła w dolnym rzędzie i bez względu na to, czy jest to 3x3 czy 5x5, skupiasz się tylko na dolnych punktach po lewej stronie (ignorując 2 punkty po prawej stronie 5x5)

Teraz najfajniejsza część

Wracasz do górnego wiersza w tej samej kolumnie, co podświetlone punkty w dolnych 3

W przypadku tych w kolumnie 1, naciskasz przełącz na 1 i 2

Dla jednego w kolumnie 3 to 2 i 3

Dla jednego w kolumnie 2 to 1, 2 & 3

Powtarzasz to dla każdego oświetlonego miejsca, nawet jeśli oznacza to powtórzenie w celu przełączenia tego samego

Więc XX 0 będzie 1, 2, następnie 1, 2, 3X 0 X będzie równe 1, 2, potem 2, 3

E. tc

A kiedy już to zrobisz, rozwiąż w dół, aby uzyskać ostatnie przejście i zadanie wykonane

W pełni ręczny sposób rozwiązywania zagadek 3x3 4x4 i 5x5

Z satysfakcją udowodniłem, że żadne z podanych tutaj rozwiązań nie jest ważne. W rzeczywistości istnieje 5x5 spraw, które są całkowicie nierozwiązywalne. Oto, jak możesz to sobie udowodnić: weź talię kart i rozdaj matrycę, używając czerwonych kartek, aby wskazać zapalone światło, i czarnych kart, aby wskazać, że światła są wyłączone. Zajmij się dowolną wielkością matrycy, a następnie wypróbuj podaną tutaj technikę. Wypróbowałem matrycę 5x5 i wymyśliłem dolny wiersz, który NIE pasuje do zamieszczonego tutaj. Oznacza to, że macierz 5x5 jest nierozwiązywalna przy użyciu algorytmu „follow the lights”. Inna witryna twierdzi, że macierz 6x6 zawsze można rozwiązać. Ponownie, używając metody opisanej powyżej - rozdawania kart w celu utworzenia matrycy i używając algorytmu „follow the lights”, znalazłem kilka macierzy 6x6, których nie można było rozwiązać tą techniką. Możesz umieścić całą matematykę, jaką chcesz, ale w praktyce PODANE TUTAJ ROZWIĄZANIA NIE DZIAŁAJĄ DLA WSZYSTKICH MATRYK.

Dzieje się tak, ponieważ tylko 25 procent wszystkich gier można rozwiązać. Te, które można rozwiązać, będą możliwe do rozwiązania tą metodą.