... nennt sich dieses Puzzle von
Uli Stein
wahrlich zu Recht. Ein böswilliger Freund hatte es mir zum
Geburtstag geschenkt, um meine knappe Freizeit noch knapper zu
machen und mir schlaflose Nächte zu bereiten. Neun Karten
müssen erstens in der richtigen Reihenfolge gelegt und
zweitens so gedreht werden, dass von den Schweinen, Mäusen,
Katzen und Pinguinen die passenden Partner nebeneinander auf den
Bänken sitzen.
Stundenlange Versuche ergaben immer das gleiche Ergebnis:
alles passt - außer der letzen Karte, die passt nicht!
Schließlich kam mir der Gedanke, dass es intellektueller
viel anspruchsvoller wäre, ein Computerprogramm zu schreiben,
das die Lösung durch brutales Ausprobieren austestet,
als selbst die Lösung manuell herauszufinden. Also frisch
ans Werk! Als Sprache kam für mich nur QuickBASIC in Frage,
weil ich darin nun mal am fittesten bin.
Ich legte die Karten beliebig zusammen, numerierte sie von
1 bis 9 durch und markierte jeweils die Seite, die jetzt
"oben" war. In einem zweidimensionalen Array werden die
vier Bilder jeder Karte gespeichert.
Die Karten liegen zuerst in der Reigenfolge 1-2-3-4-5-6-7-8-9.
Zuerst wird eine neue Reihenfolge errechnet (das heißt,
die Karten werden vertauscht). Dann wird überprüft, ob
die Bilder zusammenpassen. Wenn sie nicht passen, werden die
Karten verdreht. Wenn alle Drehungen ohne Erfolg ausprobiert
wurden, werden die Karten wieder vertauscht usw.
Soweit die Theorie. Die Praxis sah allerdings etwas
komplizierter aus. Ich stellte sehr bald fest, dass mein
Computer (damals ein Pentium 133) viele Tage lang arbeiten
würde, bis alle Kombinationen "durch" sein
würden. Es galt also, das Programm intelligenter zu machen,
um unnötige Kombinationen und Tests zu überspringen.
1.) Vergleichen: wenn die Karten 7 und 8 nicht passen, braucht
man die Karten 1 und 2 nicht mehr zu vergleichen. Simpele Sache,
aber ich hatte dies zu berücksichtigen anfangs nicht
für nötig gehalten.
2.) Anzeige: die Darstellung der Karten und der Drehungen
auf dem Bildschirm (ursprünglich dazu gedacht, um optisch
darzustellen, dass das Programm überhaupt richtig arbeitet)
kann per Tastendruck ein- und ausgeschaltet werden. So wird viel
Rechenzeit gespart. Wenn das richtige Ergebnis gefunden wurde,
wird die Anzeige automatisch wieder eingeschaltet.
3.) Vertauschen: das Schwierigste überhaupt! Zuerst liegen
die Karten in der Reihenfolge 1-2-3-4-5-6-7-8-9, dann müssen
sie in der Reihenfolge 1-2-3-4-5-6-7-9-8 liegen. Aber wie kommt
man dorthin? Zuerst erhöhte ich die Zahl 123456789 einfach
jeweils um 1 und überprüfte, ob eine Ziffer doppelt
vorkam. Wenn ja, wurde weiter erhöht; wenn nein, wurden die
Karten getestet und gedreht. Leider musste ich feststellen, dass
der Computer einen relativ großen Teil der Rechenzeit damit
verbrachte, diesem Algorithmus zu folgen und eine neue gültige
Reihenfolge zu errechnen. Also investierte ich noch einmal eine
Menge Hirnschmalz, um einen Algorithmus zu entwickeln, der ohne
Umwege eine neue Kartenanordnung errechnet.
Mit diesem Programm kam dann mein Computer nach wenigen
Stunden auf das richtige Ergebnis, das man hier im Bild
bewundern kann. Durch Klicken auf das Bild bekommt man
eine Vergrößerung.
DEFINT A-Z DECLARE SUB display (k$()) DECLARE SUB direc (z$, a$) ' ---------- die 9 Karten: ------------------------------------------ ' K = Katze R = rechts Großbuchstaben: oben (zu Beginn) ' S = Schwein L = links Kleinbuchstaben: rechts, unten, links ' M = Maus ' P = Pinguin DATA KR,sl,ml,pr DATA MR,kl,pl,sr DATA PR,sl,ml,kr DATA SR,kl,mr,pl DATA SR,ml,pr,kl DATA MR,sl,kr,pl DATA ML,kr,pl,sr DATA KL,sl,mr,pr DATA MR,pl,kr,sl DIM d$(9, 5), k$(9, 5) CLS RESTORE ' die 9 Karten werden in Variablen gespeichert: FOR x = 1 TO 9 ' Bilder: 1=oben, 2=rechts, 3=unten, 4=links FOR b = 1 TO 4: READ d$(x, b): NEXT ' Nummer der Karte d$(x, 5) = MID$(STR$(x), 2) NEXT ' In dieser Datei wird die Reihenfolge der 9 Karten gespeichert. ' Dadurch kann man das Programm jederzeit abbrechen und später ' fortsetzen lassen. Der Inhalt dieser Datei ist zu Beginn: ' 123456789 ' 0 OPEN "I", #1, "puzzle.dat" INPUT #1, reihe$ ' bisherige Reihenfolge der 9 Karten INPUT #1, anzahl$ ' bisherige Anzahl der Vertauschungen CLOSE anzahl& = VAL(anzahl$) disp = 1 DO IF disp = 1 THEN LOCATE 1, 1 PRINT anzahl$; ": alte Zahl: "; reihe$ PRINT "Suche neue Zahl. Tasten: D=Display on/off, S=Speichern+Ende" END IF ' Die Reihenfolge der Karten wird vertauscht: ' aus 123456789 wird letztendlich 987654321. FOR x = 9 TO 2 STEP -1 IF MID$(reihe$, x, 1) > MID$(reihe$, x - 1, 1) THEN n = x - 1: x = 0 END IF NEXT n$ = MID$(reihe$, n, 1) z = 0 DO z = z + 1: IF z > 9 THEN STOP s$ = MID$(STR$(VAL(n$) + z), 2) s = INSTR(n + 1, reihe$, s$) LOOP WHILE s = 0 FOR x = 1 TO 9: r$(x) = MID$(reihe$, x, 1): NEXT SWAP r$(n), r$(s) reihe$ = LEFT$(reihe$, n - 1) + s$ FOR x = 1 TO 9 FOR y = n + 1 TO 9 IF r$(y) = MID$(STR$(x), 2) THEN reihe$ = reihe$ + r$(y) NEXT NEXT ' Vertauschungen zählen und Daten anzeigen anzahl& = anzahl& + 1 LOCATE 22, 1: PRINT reihe$; " ("; anzahl&; ")"; ' die Karten den neuen Lagepl„tzen zuweisen: RESTORE FOR x = 1 TO 9 r = VAL(MID$(reihe$, x, 1)) FOR b = 1 TO 5: k$(x, b) = d$(r, b): NEXT NEXT ' neue Lage anzeigen: IF disp = 1 THEN display k$() GOSUB dreh ky$ = UCASE$(INKEY$) IF ky$ = "D" THEN disp = 1 - disp IF ky$ = "S" THEN OPEN "O", #1, "puzzle.dat" PRINT #1, reihe$ PRINT #1, MID$(STR$(anzahl&), 2) CLOSE END END IF LOOP UNTIL VAL(reihe$) => 987654321 END dreh: ' Anfangsdrehung überall = 0 d1 = 0: d2 = 0: d3 = 0: d4 = 0: d5 = 0: d6 = 0: d7 = 0: d8 = 0 ' nach und nach werden alle Karten gedreht: FOR d9 = 0 TO 3 FOR d8 = 0 TO 3 ok = 1 z$ = "82" ' rechtes Bild der 8. Karte wird mit dem linken Bild der 9. Karte vergleichen: v1$ = k$(8, 2): v2$ = k$(9, 4): GOSUB test IF ok = 1 THEN FOR d7 = 0 TO 3 ok = 1 z$ = "72" v1$ = k$(7, 2): v2$ = k$(8, 4): GOSUB test IF ok = 1 THEN FOR d6 = 0 TO 3 ok = 1 z$ = "63" v1$ = k$(6, 3): v2$ = k$(9, 1): GOSUB test IF ok = 1 THEN FOR d5 = 0 TO 3 ok = 1 z$ = "52" v1$ = k$(5, 2): v2$ = k$(6, 4): GOSUB test z$ = "53" v1$ = k$(5, 3): v2$ = k$(8, 1): GOSUB test IF ok = 1 THEN FOR d4 = 0 TO 3 ok = 1 z$ = "42" v1$ = k$(4, 2): v2$ = k$(5, 4): GOSUB test z$ = "43" v1$ = k$(4, 3): v2$ = k$(7, 1): GOSUB test IF ok = 1 THEN FOR d3 = 0 TO 3 ok = 1 z$ = "33" v1$ = k$(3, 3): v2$ = k$(6, 1): GOSUB test IF ok = 1 THEN FOR d2 = 0 TO 3 ok = 1 z$ = "22" v1$ = k$(2, 2): v2$ = k$(3, 4): GOSUB test z$ = "23" v1$ = k$(2, 3): v2$ = k$(5, 1): GOSUB test IF ok = 1 THEN FOR d1 = 0 TO 3 ok = 1 z$ = "12" v1$ = k$(1, 2): v2$ = k$(2, 4): GOSUB test z$ = "13" v1$ = k$(1, 3): v2$ = k$(4, 1): GOSUB test IF ok = 1 THEN ' alles passt!!! OPEN "O", #1, "puzzle.dat" PRINT #1, reihe$ PRINT #1, MID$(STR$(anzahl&), 2) CLOSE BEEP: display k$(): END END IF ' die Karte wird einmal linksherum verdreht: FOR x = 0 TO 3: k$(1, x) = k$(1, x + 1): NEXT: k$(1, 4) = k$(1, 0) NEXT END IF FOR x = 0 TO 3: k$(2, x) = k$(2, x + 1): NEXT: k$(2, 4) = k$(2, 0) NEXT END IF FOR x = 0 TO 3: k$(3, x) = k$(3, x + 1): NEXT: k$(3, 4) = k$(3, 0) NEXT END IF FOR x = 0 TO 3: k$(4, x) = k$(4, x + 1): NEXT: k$(4, 4) = k$(4, 0) NEXT END IF FOR x = 0 TO 3: k$(5, x) = k$(5, x + 1): NEXT: k$(5, 4) = k$(5, 0) NEXT END IF FOR x = 0 TO 3: k$(6, x) = k$(6, x + 1): NEXT: k$(6, 4) = k$(6, 0) NEXT END IF FOR x = 0 TO 3: k$(7, x) = k$(7, x + 1): NEXT: k$(7, 4) = k$(7, 0) NEXT END IF FOR x = 0 TO 3: k$(8, x) = k$(8, x + 1): NEXT: k$(8, 4) = k$(8, 0) NEXT FOR x = 0 TO 3: k$(9, x) = k$(9, x + 1): NEXT: k$(9, 4) = k$(9, 0) NEXT RETURN test: IF ok = 0 THEN RETURN IF disp = 1 THEN ' Stelle anzeigen, wo gerade der Vergleich stattfindet direc z$, "*" ' Karten darstellen display k$() ' SLEEP 1 ' Anzeigeverzögerung END IF IF disp = 1 THEN direc z$, " " ok = 1 v1$ = LCASE$(v1$): v2$ = LCASE$(v2$) ' zum linken Pinguin gehört der rechte Pinguin usw.: IF v1$ = "pl" AND v2$ <> "pr" THEN ok = 0: RETURN IF v1$ = "sl" AND v2$ <> "sr" THEN ok = 0: RETURN IF v1$ = "kl" AND v2$ <> "kr" THEN ok = 0: RETURN IF v1$ = "ml" AND v2$ <> "mr" THEN ok = 0: RETURN IF v1$ = "pr" AND v2$ <> "pl" THEN ok = 0: RETURN IF v1$ = "sr" AND v2$ <> "sl" THEN ok = 0: RETURN IF v1$ = "kr" AND v2$ <> "kl" THEN ok = 0: RETURN IF v1$ = "mr" AND v2$ <> "ml" THEN ok = 0: RETURN RETURN SUB direc (z$, a$) ' je nach Kennzahl z$ wird die Position für das Sternchen errechnet: s = VAL(LEFT$(z$, 1)) IF s = 1 THEN r = 6: c = 20 IF s = 2 THEN r = 6: c = 40 IF s = 3 THEN r = 6: c = 60 IF s = 4 THEN r = 12: c = 20 IF s = 5 THEN r = 12: c = 40 IF s = 6 THEN r = 12: c = 60 IF s = 7 THEN r = 18: c = 20 IF s = 8 THEN r = 18: c = 40 IF s = 9 THEN r = 18: c = 60 s = VAL(RIGHT$(z$, 1)) IF s = 1 THEN r = r - 3 IF s = 2 THEN c = c + 10 IF s = 3 THEN r = r + 3 IF s = 4 THEN c = c - 10 LOCATE r, c: PRINT a$; END SUB SUB display (k$()) ' Lage und Drehung der Karten darstellen: FOR x = 1 TO 3: FOR y = 1 TO 3 GOSUB disp NEXT: NEXT EXIT SUB disp: r = y * 6: c = x * 20 LOCATE r, c: PRINT k$(x + (y - 1) * 3, 5) LOCATE r - 1, c: PRINT k$(x + (y - 1) * 3, 1) LOCATE r, c + 2: PRINT k$(x + (y - 1) * 3, 2) LOCATE r + 1, c: PRINT k$(x + (y - 1) * 3, 3) LOCATE r, c - 3: PRINT k$(x + (y - 1) * 3, 4) RETURN END SUB