"Noch verzwickter"

... 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.


Und hier das Programm. Zugegeben: es ist nicht besonders übersichtlich aufgebaut. Besonders das Drehen der Karten hätte durch eine einzige, dafür aber rekursiv aufgerufene Funktion eleganter gestaltet werden können. Allerdings müssen bei jedem Aufruf lokale Variable gerettet werden, was die Sache zeitaufwändig macht. Deshalb habe ich die hier dargestellte Verschachtelung bevorzugt.
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