Das deutsche QBasic- und FreeBASIC-Forum

[SpionAtom]

Mein Sudoku-Solver nimmt langsam Form an.

Bewundern könnt ihr den Fortschritt an dieser Stelle: https://forum.qbasic.at/viewtopic.php?t=9270

Hier möchte ich allgemein über Algorithmen sprechen. Bei Bedarf gehe ich auch gerne über die Implementation meiner bisherigen Algorithmen ein.

Das Finden von 'Naked Singles', also ob sich in einer Zelle nur noch ein Kandidat befindet, ist in etwa so umgesetzt, wie man es im Kopf löst.
Das Finden von 'Hidden Singles' ist eine kleine Nummer umfangreicher. Hier gilt es zu schauen, ob eine Ziffer in einer Einheit (Zeile, Spalte oder Haus) nur noch einmal als Kandidat vorkommt.

Die weiteren Aufgaben, die mir bevorstehen, ist das Auffinden von Kandidaten Paaren, Drillingen(, Vierlingen).
Sowie das Finden von 'Hidden Drillingen', 'Hidden Vierlingen',.... (ich glaube Hidden Zwillinge gibt es gar nicht.)

Ein Zwilling (oder Kandidatenpaar) ist die Konstellation, dass in einer Einheit zwei Zellen sind, die jeweils genau dieselben zwei Kandidaten haben.

Wie kann man das möglichst lösen, dass es Zwillinge, Drillinge und Vierlinge gleichermaßen findet?

Um alles einheitlicher zu gestalten, versuche ich in Zukunft die Begriffe von dieser Seite zu übernehmen (und eventuell einzudeutschen): https://hodoku.sourceforge.net/en/tech_intro.php
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht.

[grindstone]

Hallo SpionAtom!

Wie ich an anderer Stelle schon erwähnt habe, bastele ich auch an einem Sudokulöser, allerdings in freeBASIC.

Die bereits existierenden Sudokulöser habe ich mir ganz bewusst nicht angesehen, um mich in meinem Gedankengang nicht beeinflussen zu lassen und dadurch vielleicht einen vielversprechenden Lösungsansatz vorzeitig zu verwerfen.

Mein Programm erstellt zunächst einmal eine Eingabemaske ähnlich dem "Kandidatengitter", mit allen 9 Zahlen in jedem Feld. Sobald die Maske erstellt ist, beginnt das Programm in einer Endlosschleife nach Naked Singles und Hidden Singles zu suchen und unerlaubte Zahlen aus den Kandidaten der anderen Felder zu entfernen.

Durch Anklicken eines Kandidaten (= eine der kleinen Zahlen in einem Feld) mit der Maus kann ich diesen als Vorgabe setzen, alle anderen Kandidaten, die dann nicht mehr zulässig sind, werden sofort entfernt.

Bei den allermeisten Sudokus reicht das aus, um sie zu lösen, bei vielen erscheint die Lösung schon, bevor ich alle Zahlen eingegeben habe. Wenn nicht, wie bei deinem Test-Sudoku, bleibt eine überschaubare Anzahl von Kandidaten übrig.

Entschuldige die lange Herleitung, aber sie war notwendig, um deutlich zu machen, worauf ich hinauswill.

Von hier an geht bei mir das Lösen erst einmal "zu Fuß" weiter, das zu automatisieren wäre der nächste Schritt. Ich speichere also den Spielstand ab und beginne, die Kandidaten der Reihe nach durchzuprobieren. War die gesetzte Zahl ein Fehlversuch, gibt es nach (weiterhin kontinuierlichem automatischem) Entfernen aller Naked- und Hidden Singles einige leere Felder, d.h. Felder, für die es keine Kandidaten mehr gibt. Das heißt: Lösung unmöglich, gespeicherten Spielstand zurückladen und die nächste Zahl ausprobieren. Bis jetzt ist mir noch kein Sudoku untergekommen, bei dem es mehr als 8 solcher Versuche gebraucht hätte, um es zu lösen und schon gar keines, bei dem es erforderlich gewesen wäre, in die zweite Ebene zu wechseln, also Zahlenpaare auszuprobieren.

Was ich damit sagen will: Aus meiner Sicht ist es unsinnig, in einem Computerprogramm 40 oder mehr verschiedene, teilweise recht komplizierte Lösungsansätze zu implementieren, die eigentlich "nur" für Menschen gemacht sind. Es dürfte zielführender sein, sich die Tatsache zunutze zu machen, daß der Computer (im Gegensatz zum Menschen) in kurzer Zeit eine große Zahl von Berechnungen durchführen kann. Die Kunst der Programmierers ist es, dabei die richtige Balance zwischen Algorithmus und Rechenleistung zu finden.

Das nur mal als kleine philosophische Betrachtung. Weiterhin viel Spaß!

Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen!

[SpionAtom]

Ich beginne ziemlich ähnlich mit meinem Solver.
Das Sudoku wird durch ein zweidimensionales Array repräsentiert, und die Kandidaten durch ein dreidimensionales Array. Letztendendes habe ich somit auch Zugriff auf alle Felder und dessen Kandidaten.

Schritt 1 ist das Sudoku laden, Schritt 2 ist alle Kandidaten einzutragen und anschließend alle ungültigen Kandidaten zu löschen.

Im Anschluss beginnt die Schleife mit den Lösungsstrategien bei mir, diese Liste besteht bisher aus den Strategien 'Naked Singles' und 'Hidden Singles'.
Die Liste wird immer von oben nach unten abgearbeitet. Ist eine Strategie erfolgreich (eine Zahl kann eingetragen werden oder Kandidaten können gelöscht werden), beginnt die Liste von oben. Zwischendurch wird auch geschaut, ob das Sudoku gelöst ist.
Sollte keine Strategie mehr zum Erfolg führen, so tritt der simple Backtracking Algorithmus in Kraft. In der Dosbox in QBasic kann das schonmal eine Minute und mehr dauern.

Das wäre ein Grund weitere Lösungsstrategien zu implementieren.
Ein weiterer Grund wäre es dem Benutzer einen Lösungsweg aufzuzeigen.
Und der wichtigste Grund: Aus Spaß an der Freude! Es macht Spaß an Programmen und Algorithmen zu tüfteln!

Sudokus, die mit Naked Singles und Hidden Singles allein zu lösen sind, kommen meiner Erfahrung nach nicht über den Schwierigkeitsgrad einfach oder mittel hinaus.
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht.