"Lights Out" Lösung herleiten?

Aufrufe: 1392     Aktiv: 22.03.2021 um 02:38
1

Hallo,

es gibt ja in Spielen öfter mal so Puzzles die unter dem Namen "Lights out" kursieren:

https://en.wikipedia.org/wiki/Lights_Out_(game)

Da sind beispielsweise 9 Lampen in einem 3x3 Muster angeordnet.

Zu beginn sind bspw. alle 9 Lampen aus.

Und wenn man eine Lampe aktiviert, wird nicht nur diese getriggert (also geht respektive an oder aus) sondern auch die Lampe links recht oben und unten davon. so wie bei einem kreuzmuster.

Ziel ist es am Ende alle 3x3 Lampen anzuschalten.

Es gibt zwar im Internet fix und fertige Lösungen wie man ein solches rätsel löst, also welche der Lampen man wie oft triggern muss.

 

Aber ich würde gerne verstehen wie man sowas herleitet.

Ich kann mir so ein Lampenfeld bspw. als 3x3 Matrix P vorstellen,

welches nur die Werte 0 und 1 enthält.


Zu Beginn des Spiels sind ja alle Lampen aus,

als Matrix also P=(0 0 0,0 0 0,0 0 0) (ich schreibe es zeile für zeile, durch kommas getrennt , hin).


Eine Operation würde ich mir so vorstellen dass eine Matrix dranaddiert wird.

Also wenn man bspw. die matrix M11=(1 1 0,1 0 0,0 0 0) hat, wenn man nun die Lampe oben links triggern will,

würde man an unsere Lampenmatrix P die Matrix M11 dranaddieren.


oder wenn man vom Startzustand (wo alle Lampen aus sind) die lampen 11 23 33 anmacht,

müsste man mathematisch die Matrixrechnung P+M11+M23+M33 berechnen.

Die resultierende Matrix gibt dann an welche Lampen danach noch an sind oder nicht.

Schön und gut, ich kann also die Startsituation als Matrix angeben sowie auch die anwendbaren Operationen mathematisch angeben.

Aber wie kann ich nun mit alldem das Ursprungsproblem lösen?

also die Frage:

Wie oft muss welche der Matrizen M11 bis M33 an die Matrix P dranaddiert werden damit wir die Matrix (1 1 1,1 1 1,1 1 1) erhalten?

Ich durchschaue es derzeit noch nicht. HAt Jemand einen guten Plan oder Idee? :-)

Wobei mir noch klar ist dass für jede Matrix Mij gilt: 2*Mij=Mij+Mij =(0 0 0,0 0 0,0 0 0) =P.

also 2 mal die selbe Matrix zu addieren cancelt sich aus.-

 

Irgendwie denke ich bei alldem dass man da mit Operationen mod 2 agieren muss aber ich habe noch keinen richtigen Plan :-/

 

 

Diese Frage melden
gefragt

Student, Punkte: 304

 
Habe gerade nochmal nachgedacht, eigentlich ist es ja gar nicht mal die Frage wie oft eine Matrix Mij dran addiert wird, sondern ob überhaupt.

Will sagen:
wenn wir bspw. +3*Mij dazurechnen, ist das ja dasselbe als wenn wir nur +Mij addieren. Also 3 mal lampe triggern oder nur einmal, kommmt aufs selbe aus. weil ungerade anzahl ist die lampe am ende an.

heißt, die frage ist nur welche Matrizen wir überhaupt ran addieren müssen. und welche matrizen wir weglassen und eben nicht benutzen.

wenigstens ist diamit die frage nahc dem "wie oft" vom tisch. :-/   ─   densch 21.03.2021 um 18:33
Ich habe etwas überlegt:
nehmen wir mal zur Vereinfachung den Fall mit einer 3x3 Matrix.

wenn wir bspw. die zelle in der mitte betrachten, so kann deren status verändert werden durch das triggern von 5 verschiedenen zellen:
der zelle in der mitte, der zelle oben, der zelle unten, der zelle links und der zelle rechts.
also wird sie von maximal 5 zellen beeinflusst.

Wir wollen eine Matrix L, die wir die lösungsmatrix nennen, einführen.
ihre zellen enthalten entweder die zahl 1 oder 0.
und letztlich gibt sie an, wenn wir mit der nullmatrix starten, welche lampn getriggert werden müssen um am ende die einsenmatrix zu kriegen.
haben wir also bspw. die Matrix L=(1 0 1,0 1 0,1 0 1)
dann heißt das dass wir vom startzustand aus die lampen oben links oben rechts, mitte, unten links und unten recht, je einmal drücken müssen um alle lampen am ende an zu haben. die anderen lampen dürfen nicht getriggert werden.
Leider kenne wir zu Beginn L nicht, sodass wir einfach mal L=(a b c,d e f,g h i) ansetzen. wlechen der werte 0 und 1 a-i haben müssen, müssen wir noch herleiten.

nun überlegen wir uns wie sich das drücken der lampen auf welche lampen auswirkt:
bspw. die lampe in der mitte wird von allen lampen ausser denen in den ecken beeinflusst, ihr zustand
lässt sich mathematisch also berechnen als (b+d+e+f+h) mod 2 bestimmen.
damit da 1 rauskommt, muss eben die summe (b+d+e+f+h) eine ungerade zahl ergeben.

weil die ganze sache mit dem mod ziemlich scheiße ist, wollen wir einfach annehmen das wir nur nxn matrizen mit den Elementen 0 oder 1 akzeptieren. dann können wir das modulo problem mal vorerst ignorieren.

Wenn die EInsermatrix, die wir am Ende wollen, E=(1 1 1,1 1 1,1 1 1) ist und Eij die zelle in der iten zeile und der j ten spalte bezecihnet,
dann muss für unsere pläne wie erwähnt gelten dass E22=b+d+e+f+h.

am rand und in der ecke wird es schwierig weil da nur 4 oder 3 zellen wirkund entfalten.

um ein einheitkliches vorgehen hinzukriegen, machen wir einen meisterstrich:
wir machen um unsere Lösungsmatrix (a b c, d e f, g h i) einen Rahmen von Nullelementen drum herum.
Tun also so als wäre es eine 5x5 Matrix bei der die Elemente am Rand alle 0 sind.

Die Lampe oben links in der Ecke lässt sich dann imer noch bequem berechnen als 0+0+a+b+d (wobei die ersten 2 nullen die fiktiven 0 zellen oberhalb und links der lampe sind).

mathematisch sieht unsere "erweiterte" lösungsmatrix nun so aus:
Pe=( 0 0 0 0 0, 0 a b c 0, 0 d e f 0, 0 g h i 0, 0 0 0 0 0)
auf deren Zellen wollen wir wie gewohnt über
Pe_ij zugreifen. itezeile, jte spalte halt.

bezeichne wieder E unsere EInsermatrix von oben.
Dann gilt:
E_ab=Pe_(a-1)b+Pe_ab+Pe_(a+1)b+Pe_a(b-1)+Pe_a(b+1)

Weil wir ja P zu Pe passend erweitert machen, müssen wir uns um Rand oder Eckzellen keine Gedanken mehr machen :-)


   ─   densch 21.03.2021 um 20:55
Das meinte ich im Prinzip auch, yo.

Ich habe, mal wieder nahcgedacht, und schmeiße kurz meinen bisherigen Plan:
Statt einer Einsermatrix nutzen wir einen Einservektor E.
Gehen wir wieder von unserem beispiel mit 3x3=9 Lampen aus, so ist E ein Vektor bestehend aus 9 Einsen.
Dann haben wir noch einen Vektor v=(a,b,c,d,e,f,g,h,i).
Und wir haben noch eine 9x9 matrix A sodass gelten soll:
A*v=E

Wie wandeln wir unsere Matrizen in Vektoren?
Wir fügen sie zeilenweise aneinander.
so machen wir aus der Matrix (a b c, d e f, g h i)
den Vektor v=(a,b,c,d,e,f,g,h,i).


Die 9x9=81 Elemente der Matrix A sind fest gegeben durch unsere Ausgangskonfiguration mit dem Kreuzmuster.

betrachten wir , wie gewohnt, unsere Lampe in der Mitte.
Für diese galt ja dass M22=b+d+e+f+h gilt.
was man als M22=Zeilenvektor (0,1,0,1,1,1,0,1,0) mal dem spaltenvektor (a,b,c,d,e,f,g,h,i) lesen kann.

Betreffend unserer
A*v=E
Gleichung bedeutet dies Folgendes:
die 5. Zeile von A muss (0,1,0,1,1,1,0,1,0) lauten.
Warum gerade die 5.?
Weil wir bei der Umwandlung von einer Matrix in einen Vektor bei E aus der 1 in zeile 2 spalte 2, das 5. Element des vektors 1 wird.

Wie wir genau Elemente in der Matrix den späteren elementen in nem Vektor zuordnen, sit relativ gleich.
Wir dürfen nur nicht die zuordnungsvorschrift vergessen, denn später wenn wir lösungen für a-i haben, müssen wir wieder rückwärts zuordnen können welcher buchstabe welcher Zelle zugehörig war.

Im Endeffekt haben wir eiN Gleichungssystem mit 9 Gleichungen und 9 unbekannten zu lösen.
Was wir mit computerprogramm und gauss sicherlich einfach können.


Mich regts nur auf dass ich mir die ganze zeit drüber den Kopf zerbreche wie ich Matrizenmultiplikation mit Zellen aus verschiedenen Zeilen gleichzeitig mahcen kann.
Wenn ich doch einfach statt ner Matrix deren Elemente in einen vektor schreiben kann und sich damit das Problem direkt erledigt -.-   ─   densch 21.03.2021 um 21:41
Und um es abzurunden:
Gegeben eine nxn Matrix die wir in einen Vektor umwandeln wollen.
Das Element M_ab, also zeila a , spalte b,
wird im neuen Vektor an der Position a*n+b zu finden sein.

Haben wir hingegen wie oben bspw. einen vektor der länge 9, so muss die zeilen und spalten länge der to-be-matrix n=wurzel(9)=3 sein.
ist K die position im vektor, so ist in der matrix dann
a=K%n, b=K mod n
also a ist das ergebnis der ganzzahligen division von K und n, b der Rest der bei selbiger Division übrig bleiben würde. :-)   ─   densch 21.03.2021 um 21:52
Na, jetzt habe ichs selbst schon! :-D

Aber interessant zu lesen dass sich leute damit wissenschaftlich beschäftigen.

Diese "Chasing the Light" Strategie muss man auch erst mal verstehen wobei ja eigentlich logisch dass , wenn Alles ausser der letzten Reihe komplett hell oder komplett dunkel sein soll, es maximal nur 2^5 verschiedene Muster geben kann.
Und demnach nur 32 verschiedene Wege, wie man von dem Punkt an zur Lösung kommt.

   ─   densch 22.03.2021 um 02:38
Kommentar schreiben
1 Antwort
1
http://cau.ac.kr/~mhhgtx/courses/LinearAlgebra/references/MadsenLightsOut.pdf Es gibt sicherlich noch mehr Paper dazu. Evtl. auch mal in die Referenzen schauen. Es ist gar nicht mal so einfach, sowas herzuleiten. Da kann das Spiel noch so einfach sein. Aber es ist immer wieder interessant. :)
Diese Antwort melden
geantwortet

Selbstständig, Punkte: 30.55K

 

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Cauchy wurde bereits informiert.