Liebe inforz-Radaktion,
zuallererst: Glückwunsch zu eurer immer wieder hochinteressanten inforz und weiter so!
Ich hatte schon am 25.Juni fast aufgegen die Lösung für das Rätsel-Labyrinth zu finden, jetzt schicke ich euch mit schöner Erinnerung an einige schlaflose, rätselfrohe Nächte meine Lösung. (Einen Graphen und einen Stapel Gekritzel vom Anfänger, ein C-Programm, dass einem alle Lösungen ausspuckt und jede Menge Gekritzeltes.)
Liebe Grüße
Thomas Niedling
---
Mein Lösungsvorschlag:
Vorneweg: Die 25 Felder wie folgt durchnummerieren um ihnen Namen zu verpassen und Lösungen ausgeben lassen zu können:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ^ |
Der Anfänger ------------ ...erstellt - mit der Methode zeichne für jedes Feld einen Knoten und gehe alle Felder durch und zeichne zu den Knoten der erreichbaren (anderen) Felder jeweils eine Kante - einen vollständigen Graphen für das Problem. (anlage 1)
Mit der Suchtechnik der Rückwärtstraversierung von Knoten 12 aus (die Null in der Mitte) erhält man dann - abgesehen von Schlingen - die 28 Wege aus anlage2. (Die Skizzierung der Rückwärtstraversierung unter Gekritzeltes unten.)
Der Fortgeschrittene -------------------- ...bediend sich dem Code des Anfängers, der zu faul war seine ganzen Papiere abzutippen (labyr1.c und labyr1.exe), dafür aber alle Schlingen, die möglich sind bei der Traversierung, mit ausgibt und modifiziert den Code. Der boolean besucht muss nun abgeschafft werden, weil Schlingen zugelassen sein müssen. Gibt es keine positiven Schlingen mehr um negative noch 0 bringen zu können oder umgekehrt, so kann auch hier abgebrochen werden. Boolean: neg_zyklus. (labyr2.c)
---
Gekritzeltes:
Suchtechnik: Rückwärtstraversierung
12
6-9-7-12
(6-9-7)#-12
18-16-(6-9-7)#-12
(18-16)#-(6-9-7)#-12
15-(18-16)#-(6-9-7)#-12
(0-10-15)#-(18-16)#-(6-9-7)#-12 oder 19-15-(0-10-15)*-(18-16)#-(6-9-7)#-12
Verfolgen wir zuerst nur die 1.Alternative:
1.) 20-(0-10-15)#-(18-16)#-(6-9-7)#-12
23-20-(0-10-15)#-(18-16)#-(6-9-7)#-12 oder 5-20-(0-10-15)#-(18-16)#-(6-9-7)#-12
Davon wiederum die 1. liefert die Wege:
1.1) a) 22-(17-2-22)*-(21)*-23-20-(0-10-15)#-(18-16)#-(6-9-7)#-12 b) ...
(nach etwa 4 Stunden ist man bei Unterfall 45b)
(x)* : x ist die Wiederholung, die man auch weglassen darf (x)# : muss mindestens 1mal traversiert werden, darf aber beliebig oft wiederholt werden
P.S.: Noch zwei nette Foto im Anhang...
