Automatisches Lösen von PM Logicals: Logik-Puzzle

[marcm200]

Ein Programm, das einige der Logik-Puzzles aus den PM Logicals automatisch lösen kann (siehe Bild; 3 aus den PM-Heften, und eins ("Fraktal"), das ich selbst erstellt habe). Die Zeiten zum Lösen bewegen sich im Bereich 1-4h (unter cpcemu 2.4, Echtzeitspeed). Das Programm ist un-optimiert.

Dies war seit Anfang der 90er das erste Programm, das ich wieder direkt in BASIC geschrieben habe.

Das Archiv enthält das Programm "logicals.bas", die 4 Raetsel (NAME.log, die über MERGE eingebaut werden) und eine kurze Anleitung sowie Beschreibung der aktuell verwendeten Schlussregeln (insgesamt 12 bis dato). Es werden tendenziell eher die kleineren Logikpuzzles gelöst, aber auch da nicht alle, es fehlen noch einige Regeln dafür.

[TFM]

Was genau wird denn hier gelöst? Die PM war vor langer Zeit mal gut, lese ich aber schon länger nicht mehr ;-)

[marcm200]

Bei diesen Logik-Puzzles muss man Blöcke von ausgefüllten Feldern positionieren, ähnlich wie "Schiffe versenken". Angehängt mal das Anfangsfeld für das FRAKTAL-Rätsel. Zwischen zwei "Schiffen" muss immer mindestens ein Leerfeld, ein Trennfeld (hier weiß), liegen.

Die Aufgabe ist nun, durch logisches Schließen die Schiffe so zu legen, dass alle Blocklängen, die ganz links vor den Zeilen oder über den Spalten angegeben sind, erfüllt werden, und sich Zeilen und Spalten nicht widersprechen. Mir ist allerdings nicht bekannt, ob es mathematisch bewiesen ist, dass es nur genau eine Endkonfiguration gibt.

Die achte Zeile bspw. sagt "25". D.h. wir haben ein Schiff der Länge 25. Insgesamt hat das Spielfeld 34 Spalten. Legen wir das Schiff ganz links in diese Zeile, geht es von Spalte 1-25, legen wir es ganz rechts hin, von 11-35. D.h. die Felder 11-25 in dieser Zeile sind immer Teil des Schiffes, und können damit bereits ausgefüllt werden.

Das ist immer die erste Regel, die ich anwende. Komplizierter wird es bspw. in Zeile 9 mit "11 11 1". Die Schiff-Felder, wenn alles ganz links anliegt, sind 1-11 (Schiff I),13-23 (II),25 (III). Und wenn alles ganz rechts liegt, 35 (III), 33-23 (II), 21-11 (I). D.h. die Felder 11,13-21,23,25 sind auf jeden Fall Teil eines Schiffes, aber man kann aber noch nicht sagen, für welches. Feld 14 bspw. kann zu Schiff II gehören (wenn alles links liegt) oder Schiff I (wenn alles rechts anliegt).

Wenn man dies auch für die Spalten macht, hilft einem das dann, die Schiffe genauer zu lokalisieren. Ich habe hier einige Rätsel nochmal per Hand gelöst, und alle Regeln, die mir so eingefallen sind, programmiert. Diese werden dann repetitiv angewendet, bis sich keine Veränderung mehr ergibt.

Es gibt in den PM Logicals Rätsel mit 50 oder mehr Soalten und Zeilen, die kann ich aktuell auch mit meiner C++-Version mit mehr Regeln (noch?) nicht lösen. Die "ultimate Regel" dort ist: Setze ein Feld auf Schiff oder Trenn, spiele weiter, und wenn es eine Inkonsistenz gibt im weiteren Verlauf, muss das initiale Feld ja genau das Gegenteil sein.

Aber da oft vor Inkonsistenz oder "gesamtes Rätsel gelöst" keine weitere Veränderung mehr stattfindet, d.h. Regeln fehlen, ist das oft nicht zielführend, und wenn, ist dies zeittechnisch, wenn man die Regel oft anwendet, auch auf den aktuellen 64bit-Rechnern sehr anspruchsvoll (und irgendwie eher Raten.)

Vielleicht hat ja jemand noch weitere mächtige Regeln für diese großen Rätsel gefunden?

Auf jeden Fall fand ich es interessant zu sehen, dass der Schneider durchaus auch in den 80ern (falls es die Logicals damals schon gegeben hätte) schnell genug gewesen wäre, um diese Rätsel in Angriff zu nehmen. Und das ist beim RetroComputing heutzutage meist meine Hauptfrage.

Ich habe diese Logicals früher gerne ausprobiert. Da ist so mancher Nachmittag draufgegangen.

[marcm200]

Was ich eben noch vergessen habe: Bei der Regel für "11 11 1" bin ich mir nicht sicher, ob sie so korrekt ist. Programmiert habe ich daher eine abgeschwächte Version: Da die Schiffe nach dem ersten 11er Block 12 Felder+2 Trennfelder = 14 benötigen, stehen für das rste Schiff nur die Spalten 1-20 zur Verfügung. Bei einer Blocklänge von 11 bedeutet das also, dass Spalte 11 auf jeden Fall ein Schiffteil ist und zu Schiff I gehört. Ähnlich kann man mit den anderen beiden verfahren und nachschauen, ob es dort auch definierte Felder gibt.

Ich habe im Programm zum Schluss eine Konsistenzprüfung eingebaut, ob auch genau nur die Blöcke der definierten Länge auftreten und es die Mindestanzahl an Trennfelder gibt. Unter der Annahme, dass ich diese Programmzeilen korrekt implementiert habe (ab 60000), ist ein vollständig gelöstes Rätsel damit wirklich gelöst - auch, wenn die Schlussregeln möglicherweise falsch oder inkorrekt implementiert sind.

[mv]

Ich kenne die PM Logicals zwar nicht, finde es aber spannend, sie zu lösen.
Habe mal alle Beispiel in das Programm gepackt und in die CPCBasicApps-Sammlung aufgenommen.
Damit wird die Lösung innerhalb von ein paar Sekunden berechnet...
https://benchmarko.github.io/CPCBasicTS/?database=apps&example=math/logicals