Das deutsche QBasic- und FreeBASIC-Forum

[dreael]

In der Presse greift bekanntlich zur Zeit das Sudoku-Fieber um sich. Spätestens, als sich mein Vater auch an einem solchen Rätsel die Zähne ausgebissen hatte, wurde es für mich Zeit, einmal ein paar Zeilen QBasic zu tippen (typisches Mini-Projekt); als Ergebnis ist

http://beilagen.dreael.ch/QB/SUDOKU.ZIP

entstanden. Um ein Rätsel zu lösen, muss man es wie in den Beispiel-.TXT-Dateien ersichtlich mit einem Texteditor erfassen (9 Zeilen mit 9 Zeichen, 0 = leeres Feld) und dann meinem Programm verfüttern, welches mit Hilfe von Rekursion sämtliche Lösungen dazu sucht.

Hinweis: Programm läuft bereits mit QBasic 1.1 und braucht keine speziellen Compileroptionen.
_________________
Teste die PC-Sicherheit mit www.sec-check.net

[MisterD]

hehe ich hab als Informatikprojekt son ding in Prolog geschrieben..
http://phpfi.com/99788
Macht deiner auch nur Bruteforce oder arbeitest du per ausschluss?
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra

[Mecki]

Ebenfalls eine interessante Lösung gibts auf www.freebasic.de in der (noch) aktuellen Downloaddatenbank: http://freebasic.de/?zeig=downloads&detail=userupload/Mathematisches/Freebasic-Trial.ZIP
_________________
» Yodl.de: So sucht man gestern.
» Geld verdienen im Netz + ICQ.
» Firefox!
» 100€ zu gewinnen
» FreeBASIC.de

[Mao]

Hi Mecki,
dein Link führt zu einem "403" bzw. "404"

[ytwinky]

[Manuel]

Sehr schön gemacht. Ich hatte auch bereits angefangen, ein solches Spiel in QBasic zu proggen, damit ich endlich mal eine Verwendung für Rekursion bekomme^^. Wäre vielleicht eine sehr gute Idee gewesen, wenn man sowas mal im QB-Wettbewerb aufgenommen hätte .
_________________
DL Walk (Denkspiel) | DL Malek (Denkspiel) | DL Warrior (ASCII-Adventure) | DL Sokodos (Sokoban-Klon)
---
www.astorek.de.vu

[MisterD]

ach und mecki, werd dir mal einig ob du nun stripslashes oder addslashes benutzt.. "die\\\'s"
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra

[ytwinky]

slash('/') und backslash('\') kenne ich ja nun schon und verwechsele sie auch (fast) nicht mehr..
..was sind denn nun stripslashes bzw. addslashes ?????????????
Gruß
ytwinky
_________________

[MisterD]

das sind phpfunktionen xD addslahes("die's") => "die\'s" und stripslashes("die\'s") => "die's"..
wenn mans nun verwechselt wird addslashes("die\'s") zu "die\\\'s" weil der backslash und das hochkomma escaped werden.
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra

[ytwinky]

php? Tut das weh?
..nee, im Ernst:
Habe ich bis jetzt nicht gebraucht, wird sich wohl auch noch hinziehen, bis..
Trotzdem schönen Dank für die Erklärung.
Gruß
ytwinky
_________________

[MisterD]

hehe man siehts, deine website sieht nich soo nach großem stellenwert des designs aus
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra

[dreael]

Inzwischen habe ich es geschafft, das Sudoku-Projekt etwas fortzusetzen:

http://beilagen.dreael.ch/QB/SUDOKUGN.BAS

Damit können Rätsel nun selber generiert werden. Für die Interessierten das Grundprinzip: Zuerst wie ein "Sudoku" mit "81 Lücken" "gelöst", d.h. das gelöste Sudoku zuerst generiert. Hierbei kommt wie beim Sudoku-Lösprogramm auch Rekursion zum Einsatz, wobei die Startposition überall per Zufallsgenerator initialisiert wird, damit immer wieder eine andere fertige Lösung entsteht.

In einem zweiten Schritt wird Feld um Feld ausgelost und zur Lücke umgewandelt. Dabei wird jedesmal geprüft, ob das Rätsel noch eindeutig ist. Die Eindeutigkeit kann durch normales Lösen (Rekursion wie beim bisherigen Programm) mit dem Unterschied, dass nach 2 Lösungen abgebrochen werden kann, weil ja dann bereits die Uneindeutigkeit nachgewiesen worden ist. Sobald dies der Fall ist, wird die zuletzt herausgenommene Zahl wieder zurückgelegt, d.h. wird wieder vorgegebene Zahl. Nach max. 20 solcher "fehlgeschlagenen" Lückenerzeugversuchen wird der Herausnehmeprozess als "gesättigt" betrachtet und das Rätsel ist fertig erstellt => Speicherung als Textdatei im Format vom ersten Programm.

Verfeinerungen für die Weiterentwicklung könnten beispielsweise sein, spezielle Anfängerrätsel zu generieren, wo es z.B. immer eindeutige Lücken gibt, ebenso natürlich ein Rahmenzeichen-Textfile für den Ausdruck zum von Hand lösen. Last but noch least: Gelöstes Sudoku links nicht mehr anzeigen, damit es zum Selberlösen spannend bleibt.
_________________
Teste die PC-Sicherheit mit www.sec-check.net

[Dark_King]

hmm des kann mein programm schon ne weile nur kann des immernoch net Sudokus lösen

man ich muss da echt mal weiter machen und nicht immer die feinarbeit, bin ja immernoch an der fehlermedung dran (hab zuviel anderes zeugs gemacht anstat richtig mich um mein programm zu kümmern)

sieht aber echt cool aus, auch wenn des ganze net so sicher is, falscher dateiname --> absturz

mfg

Dark_King

PS: Ich könnte noch mehr schreiben aber da würde ich nur mein Programm, dass noch in der entwicklung ist anpriesen
_________________

[dreael]

Inzwischen gibt es eine kleine Neuigkeit: visueller Sudokulöser. Wer sich bereits die verschiedenen Sudoku-Tutorials in den Büchern sowie Internet etwas schlauer gemacht hat, kennt die verschiedene Muster, nach denen man suchen muss wie Ausschluss, Zeilen- und Spaltenoperationen usw.

Beim hier vorgestellten Programm steht also absichtlich nicht das Lösen jedes beliebigen Sudokus (dies beherrst nämlich das ganz zu Beginn vorgestellte Programm bereits) im Zentrum, sondern die Analyse bezüglich Schwierigkeitsgrad. Anfänger können diese Variante auch gut als Lehrprogramm gebrauchen, in dem man die durch farbige Rechtecke gegebenen Hinweise auf platzierfähige Zahlen noch zuerst selber finden versucht, bevor man sie mit Tastendruck aufdeckt.

Download-Link: http://beilagen.dreael.ch/QB/VSUDOKU.ZIP

Unterschied der beiden Versionen: Die zweite Version sucht auch nach indirekten Tripeloperationen, während die erste Version nur Ausschluss- und Zeilen-/Spaltenoperationen macht. Das Eingabedateiformat ist übrigens immer noch dasselbe, also ASCII, 9 Zeilen à 9 Zeichen.
_________________
Teste die PC-Sicherheit mit www.sec-check.net

[dreael]

Auch bei mir hat es während der Offline-Zeit im kleinen Rahmen Neuerungen gegeben: Bin unter

http://www.squobble.com/puzzle/

eine noch recht interessante Sudoku-Variante fündig geworden, die gleich etwas "Forschung & Entwicklung"-Stoff geliefert hat. Zuerst zur Variante im genannten Link: Neben den Zahlen stellen auch die Farben ein eigenes Sudoku-System dar, es müssen also die Steine so gelegt werden, dass sowohl die Zahlen als auch Farben ein gültiges Sudoku bilden.

Da ich schon eine Weile mich auch mit dem Thema Rätsel generieren auseinandergesetzt habe, hat sich folgende Herausforderung ergeben: In der genannten Version werden zwei "normale" Sudokus im Prinzip unabhängig voneinander generiert und anschliessend überlagert, das eine davon in Farben transformiert. Zwangsweise ergeben sich einerseits mehrfach vorkommende Zahlen-/Farbkombinationen, umgekehrt kommen bestimmte Kombinationen überhaupt nicht vor.

Die grosse Herausforderung: Ein solches Farb-/Zahlsudoku generieren, welches zusätzlich die Eigenschaft hat, dass jede Farbe mit jeder Zahl kombiniert vorkommt und es somit keine zwei identischen Felder gibt. Von mir bereits einmal ein Ansatz, ein solches Rätsel zu generieren:

http://beilagen.dreael.ch/QB/FZSUDOKU.ZIP

Screenshot Suchprozess:

http://beilagen.dreael.ch/QB/Doppelsudoku1.gif

Trotz verschiedenen Optimierungen der rekursiven Suche hat sich herausgestellt, dass es möglichlicherweise ganz lange dauert, bis man ein komplettes "Dual-Layer"-Sudoku findet, welches auch das Steinkriterium erfüllt.

Dass aber diese Aufgabe mathematisch betrachtet lösbar ist, beweist FZSUDO_S.BAS (=die "Sonder"-Variante): Die dortige spezielle Anordnung würde sämtliche Kriterien erfüllen (links).

http://beilagen.dreael.ch/QB/Doppelsudoku3.gif

Durch Permutation der Zeilen, Spalten sowohl innerhalb der Quadrate als auch qadratgruppenweise und Farben und Zahlen auf beliebige Weise selber permutieren lässt sich im beschränkten Rahmen auch Zufall hineinbringen (rechts).

Wer also Lust hat, kann seinen 3,4 GHz-Pentium einmal selber ein Wochenende lang mit dieser Suchaufgabe beschäftigen oder findet vielleicht ein verbesserter Suchalgorithmus, bei dem nicht mehr dieser Tripel-Gruppierungseffekte wie bei FZSUKO_S.BAS auftreten.
_________________
Teste die PC-Sicherheit mit www.sec-check.net

[nixsager]

Hi

wenn du immer noch an dem prog arbeitest und du noch immer einen suchalgorithmus, schnapp paar leute die das spiel spielen und frag sie aus und mach dann daraus einen suchalgorithmus!

frage mich aber nich wie da ich für das spiel und den suchalgorithmus
zu blöd bin

[Jojo]

ein mensch arbeitet aber nicht nach einem algorithmus, sondern nach einem system - was in meinen augen einen riesen-unterschied macht, denn das system ist oft gar nicht so durch eine maschine "nachvollziehbar"...
_________________
» Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.

[nixsager]

probieren geht über studieren

ich häts auch ander ausdrücken können, er soll eine ki bauen

[dreael]

Inzwischen gibt es vom visuellen Sudokulöser eine neue Version:

http://beilagen.dreael.ch/QB/VSUDOKU3.BAS

Es beinhaltet folgende Neuerungen:
- Nach indirekten Tripeln wird erst gesucht, wenn es keine direkten Operationen (Zeile/Spalte und Ausschluss) gibt
- Gegenüber VSUDOKU2.BAS erkennt es neu auch indirekte Auschlüsse. Dazu kleine Situation:

[dreael]

Bereits das nächste Release ist draussen:

http://beilagen.dreael.ch/QB/VSUDOKU4.BAS

Als Neuheit findet diese Version nun auch Hidden und Naked Gruppen, womit inzwischen ein sehr grosser Teil aller Sudoku-Rätsel ohne "Trial and error" (Zahl annehmen müssen, welche entweder per Zufall stimmt oder zu einem Widerspruch führt) gelöst werden kann.

Ausserdem sucht das Programm den jeweils einfachsten Weg, d.h. bei indirekten Kombinationen wird immer der kürzeste Weg gesucht, wofür programmintern intensiver Gebrauch von Rekursion gemacht wird.

Darstellung ist ebenfalls etwas optimiert: Drittes Sudoku-Quadrat konnte ins zweite genommen werden, d.h. Lösungsreihenfolge und Anzahl Kandidaten erscheinen nun kombiniert.
_________________
Teste die PC-Sicherheit mit www.sec-check.net