Das deutsche QBasic- und FreeBASIC-Forum

[Revilo]

Hallo grindstone,
wenn du deine Single-Suche permanent durchlaufen läßt, musst du im schlimmsten Fall also alle 81 Zellen abklappern, um nach Singles zu suchen.
Würde es nicht reichen, ab der zuletzt eingetragenen Stelle nach Singles zu suchen? Danach geht es doch eh wieder in der Zelle (1,1) los.
Was sich dann als Single herausstellt, wird eben dann als solcher erkannt, nur halt einen Durchlauf später. Ist das nicht effektiver, als bei jedem Eintrag sofort alle 81 Zellen nach möglichen, sich jetzt ergebenen Singles "abzuklappern"?
Oder sehe ich das falsch?
Gruß Revilo

[SpionAtom]

Die 6 ist zu Beginn nicht ausgeschlossen in der Ecke (1,1), das hast du richtig erkannt. Später durch das finden diverser Singles wird sie aber schließlich doch ausgeschlossen.
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht.

[grindstone]

Wenn beim Ausschließen von Zahlen (zeilen- spalten- und quadratweise) in einem Feld nur noch eine mögliche Zahl übrigbleibt, wird sie automatisch gesetzt, so, als ob ich sie eingegeben hätte. Und dann wird erneut überprüft, ob dadurch weitere Zahlen ausgeschlossen werden können. Das gibt in den meisten Fällen eine Kettenreaktion.

Manchmal bekomme ich damit sogar schon eine Lösung, bevor ich alle Zahlen eingegeben habe.

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

[SpionAtom]

Erneute QBasic Enüchterung:

Habe einen Backtracking Algorithmus von https://www.geeksforgeeks.org/sudoku-backtracking-7/ übersetzt. Und erhalte beim Ausführen die Fehlermeldung:

[Revilo]

Hallo SpionAtom,

[SpionAtom]

Das erste Video erklärt den Algorithmus ziemlich gut, ist allerdings englisch:

https://www.youtube.com/watch?v=cbUd4VVyKto

Das zweite Video gibt sogar den Pseudocode vor, also die Bauanleitung ohne eine konkrete Programmiersprache zu verwenden:

https://www.youtube.com/watch?v=J0N1G33wNlQ

Das sieht ziemlich easy aus.
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht.

[SpionAtom]

Es war einigermaßen leicht zu implementieren (ich habe ja auch die Erfahrung ).

Ein iterativer Solver, der mit Live-Anzeige des Lösens ca. 3-10 Sekunden braucht.
Der Algorithmus ist tatsächlich sehr schön zu verstehen und man muss nicht mit Rekursionsparametern und Rückgabewerten hantieren.

https://github.com/SpionAtom/QBasic/blob/main/SUDOSOL2.BAS

Einzig bin ich mir nicht sicher, ob bei einem ungültigen Sudoku das ganze nicht in eine Endlosschleife läuft, der Test hat zumindest gut funktioniert.


EDIT: Für ein etwas schwierigeres Sudoku brauchte der Solver von 15:15 - 18:23 Uhr, in der Dosbox, unkompiliert, mit Zwischendurchausgabe. Dennoch sind über drei Stunden etwas zu viel des Guten.
Als nächstes muss ich also an der Mischung zwischen Lösungsstrategien und Backtracking arbeiten, sodass die Gesamtzeit kleiner wird.
(QB64 braucht 7 Sekunden!)
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht.

[Revilo]

Hallo SpionAtom,
wir kommen der Sache näher.
Deine empfohlenen Videos waren mir leider zu "englisch-belastet" also entsprechend wenig verständlich. Dennoch danke ich dafür.
Dein Code war wesentlich einleuchtender, weil in QBasic geschrieben, was ich verstehe.
Ich hätte noch eine Nachfrage zu deinem Code:
Code-Zeile 33 - 42 liefert praktisch das Original-Sudoku, was zu lösen ist.
Code-Zeile 55 - 64 liefert genau dieses Sudoku, falls es nicht lösbar ist.
Welchen Zweck haben die Code-Zeilen 44 - 53 ?

[SpionAtom]

Die drei Data-Blöcke sind enfach verschiedene Sudokus, die ich in meinem Programm laden kann. In Zeile 9 gebe ich an, welchen Data-Block ich lade.
Du kannst dort beliebig viele weitere Sudokus eintragen. Also 9 Datazeilen, die dein Sudo repräsentieren. Vorangestellt muss nur eine Zeilenbezeichnung sein wie S1: oder S2:
Und in Zeile 9 wählst du mit RESTORE Zeilenbezeichnung ein beliebiges vorhandenes Sudoku aus.

Mein Backtracking-Algorithmus funktioniert doch ganz gut. Wenn es eine valide Lösung gibt, dann wird sie auch gefunden. Wenn es keine valide Lösung gibt, dann bekomme ich das auch mit. Nur im schlimmsten Fall sucht er leider noch stundenlang.
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht.

[Revilo]

Hallo SpionAtom,
wenn du möchtest, dass ich dich verstehe, verzichte bitte auf "fach-chinesisch".
Was bedeutet "valide Lösung"?

Wie findest du meine Vorgehensweise bei der Single- bzw. Zwillingssuche?
Was hältst du von meiner Anregung zum 3 - maligen Durchlauf?

Gruß Revilo

[SpionAtom]

Valide Lösung = Gültige Lösung = Einfach ein korrekt gelöstes Sudoku.
(Hingegen eine invalide Lösung wäre ein falsch gelöstes Sudoku - also fehlerhaft, oder ein Sudoku ohne Lösung, oder ein Sudoku mit mehreren Lösungen)

Dreimaliger Durchlauf ist eigentlich unnötig.
Man hat seine Liste von Strategien: Full House, Singles, Hidden Singles, X-Wing....

Man klappert diese Liste ab, bis man was gefunden hat. Und dann klappert man diese Liste erneut ab, bis man was gefunden hat, usw.
Wurde die komplette Liste abgeklappert, ohne dass man was gefunden hat, dann bringt es auch keine neuen Ergebnisse, wenn man das ganze noch zwei- dreimal laufen lässt.
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht.

[Revilo]

Hallo SpionAtom,
im Grunde hast du natürlich recht.
Das ist eben ein Zeichen meiner fachlichen Unsicherheit.
Wenn die gesamte Liste der Strategien einmal erfolglos durchgelaufen ist,
wird das erneute Abklappern der Liste genauso erfolglos sein.

Ich lasse das ganze zwei- oder dreimal durchlaufen, nur um praktisch Gewissheit über eine bereits bestehende Gewissheit zu bekommen.
(Doppelt genäht hält besser ). Hinsichtlich der Bearbeitungszeit macht das keinen großen Unterschied.

Aber wenn sich doch ein Fehler eingeschlichen hat, kann dessen Suche Wochen dauern. Da sich dieser Fehler oft sehr gut versteckt, (manchmal ist es nur ein Komma, wo eigentlich ein Semikolon hingehört) stellt man praktisch alles, selbst das sauber funktionierende, unter "Generalverdacht".

Statt den einen Fehler zu finden, baut man eventuell einen zusätzlichen ein.
Genau deshalb ist mein Programm gespickt, mit "Zwischen-Infos":
print: "Bis hier ok.":sleep

Wenn man nicht genau weiß, was man tut, sollte man zumindest wissen, bis wohin man etwas richtig gemacht hat. Wenn es einen Fehler gibt, kann er nur danach aufgetreten sein. Das grenzt die Suche schon mal etwas ein.

Gruß Revilo

[SpionAtom]

Ja, die Fehlersuche (oder Debugging im Allgemeinen) mache ich in QBasic genau so mit den Zwischen-PRINTs, geht ja nicht anders.

Ich habe meinen Solver nun soweit, dass erst einige Lösungsstrategien probiert werden, ehe per Backtracking das ganze gelöst wird:

https://github.com/SpionAtom/QBasic/blob/main/SUDOSOLV.BAS

Im Repo liegt ebenfalls ein Testsudoku, welches ca. 40 Sekunden Lösungszeit braucht.

https://github.com/SpionAtom/QBasic/blob/main/m1.sud


Nun kann ich nach Lust und Laune weitere Strategien einbauen (Zwillingspaare zb, oder x-wing,...), jedoch ist das Lösungsprogramm erstmal funktionsfähig und somit fertig!
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht.

[Revilo]

Hallo SpionAtom.
Glückwunsch. Wenn ich bedenke, wie lange ich daran schon umherbastele.
Du machst das in wenigen Tagen, während ich Monate brauche.
Kompliment.
Das ist aber nun mal der Unterschied zwischen einem Profi und einem Laien.
Jetzt weiß ich zumindest schon mal, wie "der Hase überhaupt laufen muss".

Wofür steht eigentlich die 1. Zeile: DEFINT A-Z?
Vermutung: Alle Variablen, die mit einem Buchstaben beginnen, werden als integer definiert. So erspart man sich die Formatbezeichner. Richtig?

Was ist eine "initiale Ziffer"?

Nur, um mich nochmal zu vergewissern: CHR$(27) steht für ESCAPE, richtig?

Gruß und schönes WE Revilo

[SpionAtom]

Danke, danke! Macht ja auch Spaß etwas zu knobeln und an Programmen zu basteln.

[Revilo]

Hallo SpionAtom.
sicherlich kann man alles irgendwo nachlesen.
Sorry, aber zwischen lesen und tatsächlich verstehen können dennoch Welten liegen.
Meine Vermutung bezüglich DEFINT A-Z war offenbar richtig.

Aber was mache ich, wenn ich z.B. eine Variable Namens "Sudokuwort" habe?
Nach dieser Definition würde sie als "Integer" definiert werden.

Ich brauche sie aber nicht als integer sondern als String mit einer Länge von 81 Zeichen. Wie muss ich diese "Ausnahme" definieren?
Aber so ist nun mal das Leben.
Ein Laie muss sich quälen, ein Profi kann darüber lächeln, weil er weiß, wie es geht. Aber dennoch hat jeder Profi mal als Laie angefangen.

Gruß Revilo

[grindstone]

[SpionAtom]

Das mit der QBasic Hilfe ist kein Hinweis zum Ärgern. Es ist überall hilfreich, wenn man sich mit so Hilfen auseinandersetzt.

Außerdem bekommst du damit direkt Hilfe und musst nicht auf deine Forumskollegen auf Antwort warten. Wenn nach dem Lesen der Hilfe dann immer noch Fragen bestehen, frag hier gerne nach.

Aber sonst. Wenn du DEFINT nicht kennst, gehe zu dieser Stelle in deinem Programm und drücke F1, schneller geht's eigentlich nicht
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht.

[nemored]

Da ich vor QBasic mit einem anderen BASIC-Dialekt zu tun hatte, der zwar ein paar Jahre älter, aber bereits deutlich moderner umgesetzt war, war QBasic für mich eigentlich ein Rückschritt. Die integrierte Hilfe war eine der wenigen echten Glanzlichter.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1.

[Revilo]

Hallo SpionAtom, hallo grindstone,
nach dem, was ich bisher hier lesen durfte gibt es offenbar drei Möglichkeiten (respektive Befehle) eine Variable a als integer zu definieren.
'1) DEFINT A-Z
'2) DIM a%
'3) DIM a as INTEGER.

Wenn es drei Möglichkeiten gibt, wird jede wohl auch ihren eigenen speziellen Sinn und Zweck haben. Sonst bräuchte man ja nur eine dieser drei.

Frage:
Was ist der Unterschied zwischen diesen drei Möglichkeiten, eine Variable a als Integer zu definieren?

Gruß Revilo