Passend zum heutigen Datum habe ich mich mit dem „Haus des Nikolaus“ auseinandergesetzt. Zum Selbststudium lohnt ein Blick auf die Internetseite „Mathematische Basteleien“ von Jürgen Köller, der dort eine umfassende Beschreibung des Problems liefert. Der ebenda gegebene Hinweis, dass man die möglichen Lösungen der Strichführung mittels eines Computerprogramms auch auf einem C64 ermitteln kann, war Anreiz genug, genau dieses zu versuchen. Das Ergebnis wäre vielleicht auch ein passender Beitrag zum aktuell in der Schlußredaktion befindlichen C64-Weihnachtsheft gewesen, wenn das Progrämmchen denn eher verfügbar gewesen wäre.
Die Eingangs erwähnte Internetseite liefert verschiedene Hintergrund-Links und so gibt es auch einen auf ein bereits bestehendes Programm von Matthias Jauernig zur Ermittlung aller existierenden Lösungen. Leider in C und leider – aber nicht verwunderlich – mit rekursiven Funktionsaufrufen. Weil sich das Commodore BASIC dafür nicht wirklich gut eignet, habe ich mich für die Umsetzung am C64 (bzw. C128) lieber an dem an „brute Force“ erinnernden Hinweis aus der zuerst genannten Quelle gehalten.
Um das Haus und die Strichreihenfolge zu beschreiben, werden alle Ecken durchnummeriert. Beginnend unten links mit der Eins geht es gegen den Uhrzeigersinn im Rechteck herum. Die Dachspitze erhält die Fünf. Über eine Verknüpfungsmatrix (wer mit wem) kann man dann definieren, welche Punkte miteinander verbunden sind und welche nicht. Da jede Verbindung nur einmal zulässig ist (also nicht übermalt werden darf) ist die Anzahl der gültigen Lösungen begrenzt.
Das Programm wird dadurch vereinfacht, dass es berücksichtigt – was sich mathematisch ableiten läßt -, dass die Konstruktion des Hauses stets unten links beginnt (Punkt 1) und unten rechts endet (Punkt 2); man kann das umdrehen, erhält dann aber nur ein Spiegelbild. Durch die definierte Start- und Endposition ergibt sich auch für die benachbarten Punkte eine eingeschränkte Variabilität. Über verschachtelte Schleifen und Tabellen hätte man das in einem BASIC-Programm sauber abbilden können, ich habe mich aber für „quick and dirty“ entschieden und alles in eine Schleife gepackt, aus der ich nur die sofort erkennbar ungültigen Werte per IF-Abfrage rausschmeiße. Nicht elegant, nicht schnell, aber es funktioniert (sehr, sehr langsam).
100 rem *** das haus vom nikolaus ***
110 rem
120 dim n(5,5),a(5,5):rem verknuepfungsmatrix
130 data 0,1,1,1,0
140 data 1,0,1,1,0
150 data 1,1,0,1,1
160 data 1,1,1,0,1
170 data 0,0,1,1,0
180 for i=1to5: forj=1to5
190 read a: n(i,j)=a
200 next: next
210 rem start bei 1 ende bei 2
220 rem 9 knoten (0/8), davon 7 variabel
230 dim k(8)
240 k(0)=1:k(8)=2
250 c=0: rem counter
260 rem * hauptschleife *
270 for k=2311111 to 5535554
280 k$=mid$(str$(k),2)
290 f=0: rem fehlerflag
300 fori=1to7
310 k(i)=val(mid$(k$,i,1)):ifk(i)=0 or k(i)>5 then f=1 :i=7
320 next: if f then 450
330 rem * init testmatrix *
340 for i=1to5: forj=1to5
350 a(i,j)=n(i,j)
360 next: next
370 rem * pruefung auf wegstrecken *
380 f=0: rem fehlerflag
390 fori=1to8
400 if a(k(i-1),k(i))=0 then f=1:i=8
410 a(k(i-1),k(i))=0: rem benutzter weg
420 a(k(i),k(i-1))=0: rem zugehoeriger rueckweg
430 next
440 if f=0 then gosub 480
450 next
460 print"*** ende ***"
470 end
480 rem * ausgabe *
490 c=c+1
500 print "loesung"c"{left}:";
510 forj=0to8: print str$(k(j));: next
520 print: return
Es gibt 44 Lösungen (nur so als Hinweis, falls man das Ende der Berechnungen nicht abwarten will). Etwas schneller als in reinem BASIC geht es mit einem Compiler und SuperCPU oder in VICE im Warp-Mode. Der mit BASIC 128 (Data Becker) für einen C128 compilierte Code ist hier verfügbar.
Errata (14.12.2020): Die Zeile 270 sollte wie folgt lauten:
270 for k=2311111 to 4555554
Ich muss zugeben, dass ich mich um diesen Blogbeitrag seit zwei Tagen herumdrücke. Eigentlich tue ich das schon, seit ich mir dieses C64-Spiel gekauft habe. Zu viele Erinnerungen.
