Das deutsche QBasic- und FreeBASIC-Forum

[grindstone]

[SpionAtom]

[dreael]

Und hier noch ein guter Wikipedia-Artikel als Einstieg

https://de.wikipedia.org/wiki/Wahrheitstabelle

@Revilo: Letztlich würde ich Dein Problem tatsächlich einmal als Wahrheitstabelle formulieren (Bleistift und Papier), d.h. alle Eingangswerte als Spalten, alle Kombinationen davon als Zeilen und in einer Spalte den gewünschten Ausgabewert (True bzw. False).

Anschliessend ist die Boolsche Algebra gefragt, um einen passenden Ausdruck formulieren zu können (und diesen nach Möglichkeit noch vereinfachen), welcher überall den gewünschten Ausgabewert liefert.
_________________
Teste die PC-Sicherheit mit www.sec-check.net

[grindstone]

[Revilo]

Hallo nemored,
bei der Suche nach einem Lösungsweg für Sudokus stieß ich auf ein Video zum Thema Backtracking. Am Ende wurde auch der Code angegeben, aber leider in Python. Das half mir aber nicht viel weiter, weil ich ja nur QBasic beherrsche.
Hier wurden die Begriffe "True" und "False" verwendet, weil man bei diesem Algorithmus wohl unterscheiden muss, ob es weiter geht oder ob man in einer "Sackgasse" gelandet ist.

Python ist dem QBasic augenscheinlich ähnlich, aber eben nicht dasselbe.
Wenn ich diesen Python - Ansatz nutzen möchte, müßte ich also Python in QBasic quasi "übersetzen". Hast du eine Idee, wie man das elegant hinbekommen kann, gibt es vielleicht ein Tutorial, das darlegt, wie eine Python-Zeile in QBasic aussehen müsste, z.B. bei Schleifen?

"True" und "False" gibt es in QBasic aber bekanntlich nicht.
Kann man sie irgend wie anders ausdrücken, um dieselbe Wirkung zu erzielen?

Meine Idee ist, statt "True" und "False" , die ja Begriffe der Boolschen Arithmetik sind, einfach eine stinknormale Variable "Sackgasse" einzuführen:
Sackgasse = 0 alles ok. es geht weiter, wie bei "True"
Sackgasse = 1 bei Backtracking also 1 Schritt zurück wie bei "False"

Diese Idee zu testen wäre aber erst der zweite Schritt.
Zuerst brauche ich ja eine Übersetzung des Python -Codes in QBasic.
Gruß

[Revilo]

Hallo nemored,
als Ergänzung meiner letzten Mail:

Ich habe mir mal die Mühe gemacht, alles relevante Zeichen für Zeichen abzutippen, damit ich es dir übermitteln kann.

Als notwendiger Parameter wird das zu lösende Sudoku (hier als Beispiel) als zweidimensionale Liste übergeben, in Python wird es so dargestellt:

sudoku = [ [0,0,7,0,0,9,0,4,5],
[9,3,0,7,0,8,0,6,0],
[6,0,0,0,5,0,0,0,7],
[0,0,0,0,8,0,0,7,0],
[0,0,0,0,0,0,0,3,0],
[7,4,2,0,6,3,9,1,0],
[0,0,0,2,0,0,0,0,6],
[0,6,0,9,1,0,0,0,3],
[1,0,3,0,0,0,0,0,0] ]

Wie würde diese Tabelle in QBasic aussehen, oder kann man sie in QBasic
vom Syntax her so 1 zu 1 übernehmen/definieren?
Wie kann ich sicherstellen, dass die gegebenen Zahlen auch an der richtigen Stelle in dieser Tabelle stehen?

Der Code für den Backtracking-Algorithmus sieht dafür in Python so aus:

def backtracking (sudoku):
if alle­_felder_ausgefüllt(sudoku):
return True = Sudoku gelöst

zeile, spalte = naechstes_freie_feld(sudoku)
for zahl in range(1,10): = Zahlen von 1 bis 9
if zahl_erlaubt(zeile, spalte, zahl):
sudoku[zeile][spalte] = zahl

geloest = backtracking(sudoku)

if geloest:
return True
sudoku[zeile][spalte] = 0
return False

Wie kann man das in Qbasic übersetzen?
Warum läuft for zahl in range(1,10): von 1 bis 10, wenn doch nur 9 Zahlen für eine Zelle möglich sind?

Welche Vorarbeiten, Definitionen z.B. für Zeile und Spalte wären noch nötig?
Das mag sich lesen, als ob ich eine Komplett-Lösung von dir erwarten würde. Da ich mich inzwischen schon seit 5 Jahren mit diesem Problem umherquäle, wäre ich bestimmt nicht böse, wenn du sie mir fertig liefern würdest. Aber wo bliebe dann der Reiz am eigenen Denken?
Lernen heißt in erster Linie, sich selbst zu bemühen.
Aber manchmal geht es einfach nicht mehr weiter, weil es immer irgend etwas gibt, das man noch nicht weiß. Und dann braucht man mal einen helfenden Hinweis/Tipp/Fingerzeig.
So bitte ich, meine Anfragen auch zu verstehen.
Gruß Revilo

[SpionAtom]

Ich kann dir nur empfehlen, eine Nummer kleiner zu beginnen.
Statt eines Solvers, der mit Rekursion arbeitet, schreib doch erstmal ein Programm, welches den Benutzer erlaubt, das Sudoku erstmal selbst zu lösen.

Die Algorithmen selbst sollte man auch unabhängig von der verwendeten Programmiersprache verstehen, bist du schon soweit?

Dann lege ich dir Konzepte nahe wie "Zweidimensionale Arrays", oder "Boolsche Algebra"

Mehr zu den Arrays findest du zb unter diesen Links: http://www.antonis.de/faq/QBMonFAQ-Dateien/324197220.html
http://www.antonis.de/faq/QBMonFAQ-Dateien/74973999.html

Mehr zu Boolsche Algebra findest du unter diesem Link, vielleicht kannst du das nochmal verinnerlichen :
https://forum.qbasic.at/viewtopic.php?p=111833



Zweidimensionale Arrays würde ich wie folgt in QBasic umsetzen

[nemored]

Ich arbeite seit etwa 20 Jahren nicht mehr mit QBasic, daher kann ich nicht garantieren, dass meine Lösungsvorschläge exakt so funktinieren. Im Moment fehlt mir auch die Zeit, ausführlich auf einen Sudoku-Löser einzugehen, daher nur eine grobe Umsetzung des Backtracking-Algorithmus.

In FreeBASIC gibt es eine Methode, Arrays zu befüllen, die der oben angegebenen Python-Methode sehr ähnelt; in QBasic gibt es diese Möglichkeit noch nicht. Ich würde da ebenfalls den Weg mit DATA und READ gehen, den SpionAtom vorgeschlagen hat.

Hier also eine "Übersetzung" des Backtracking-Algorithmus. Ob sich allerdings in QBasic bereits Arrays übergeben lassen, weiß ich ehrlich gesagt nicht.