 |
Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
|
| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
grindstone
Anmeldungsdatum: 03.10.2010
Beiträge: 1245
Wohnort: Ruhrpott
|
 Verfasst am: 27.11.2024, 11:32 Titel: |
 |
|
| nemored hat Folgendes geschrieben: | Warum nur schwirren meine Gedanken jetzt um funktionale Programmiersprachen, head und tail?  |
Nun bring ihn doch nicht noch mehr durcheinander! Ihm kommt doch jetzt schon Qualm aus den Ohren.
Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
| Nach oben |
|
 |
Berkeley
Anmeldungsdatum: 13.05.2024
Beiträge: 74
|
| Verfasst am: 27.11.2024, 18:39 Titel: |
|
|
Ich wiederhole mich nur ungern: Rekursion ist hierfür nicht nötig. Und als "Rekursion" bezeichnet man, wenn ein Unterprogramm sich selbst aufruft - und sich natürlich Daten übergibt. Streng genommen ist es eigentlich nur eine Schleife, die anders formuliert wird. Bei dem Begriff geht's auch letztlich nur darum, welche Fähigkeiten eine Programmiersprache/Compiler besitzt, und nicht um eine Programmiertechnik.
Das kann man auch einfach auf Wikipedia nachlesen unter "Rekursion" und "Iteration", falls man sich für Informatik-Theorie interessiert. https://de.wikipedia.org/wiki/Rekursion#Rekursion_in_der_Programmierung
Elementar bei diesem Problem ist der Umgang mit Arrays - "Feldvariablen":
| Code: |
DIM kaestchen&(9, 9)
|
- so in etwa. Je nach BASIC-Dialekt "kaestchen%", nur "kaestchen" und stattdessen "AS INTEGER", "AS BYTE" was auch immer. Steht zum Beispiel in der dritten Spalte sechste Zeile vom Sudoku die Zahl "9" machen wir
- Normalerweise haben die ersten Felder immer den "Index" 0. Die Zählung geht also von 0 bis 8 statt von 1 bis 9. Manche BASICs sind menschenfreundlicher, und übersetzen diese Angaben zwischen mathematischem und Computer-Index, dann geht's im Quelltext von 1 bis 9, obwohl's im Maschinencode von 0 bis 8 geht - was leider eher zu Verwirrung und Fehlern führt. Vorallem FreeBASIC ist da "zu free", man kann hier sowohl 0 als auch 9 benutzen, ohne dass es eine Fehlermeldung gibt.
Und jetzt überlegen wir uns einen Algorithmus, welcher das Sudoku löst. Wobei wir zuallererst eine Lösung brauchen, wie man ein Sudoku eingibt. Die allerprimitivste Lösung wär' erst mal über den Quelltext:
| Zitat: |
kaestchen(0,0)=0
kaestchen(1,0)=0
kaestchen(2,0)=0
kaestchen(3,0)=0
kaestchen(4,0)=0
kaestchen(5,0)=0
kaestchen(6,0)=0
kaestchen(7,0)=0
kaestchen(8,0)=0
kaestchen(0,1)=0
kaestchen(1,1)=0
kaestchen(2,1)=0
kaestchen(3,1)=0
' ... und so weiter bis zum:
kaestchen(8,8)=0
|
Verdammt langer Text, aber deutlich einfacher getippt als ein Interface mit Mausklickeingabe... (wenn auch nicht kürzer ;-))
Das vorgegebene Sudoku füllt man dann also einfach in die Felder aus und lässt den Algorithmus drüberlaufen. Leere Kästchen sind 0, "gelöste" Kästchen enthalten die Ziffer 1 bis 9.
Eleganter ist natürlich, wenn man nur die Vorbelegungen eingibt:
| Code: |
FOR y%=0 to 8
FOR x%=0 to 8
kaestchen(x%,y%)=0
NEXT x%
NEXT y%
kaestchen(3,2)=7
kaestchen(5,6)=2
...
|
- Die FOR-NEXT-Schleifen sind eigentlich überflüssig, weil die BASICs Variablen normal immer auf 0 setzen. Aber es zeigt, wie man in einer Schleife auf jedes einzelne Feld zugreifen kann, und das braucht man dann beim Lösungsalgorithmus. Aber auch für die Ausgabe des "Ergebnisses":
| Code: |
FOR y%=0 to 8
PRINT "+-+-+-+-+-+-+-+-+-+"
FOR x%=0 to 8
PRINT "+";STR$(kaestchen(x%,y%));
NEXT x%
PRINT "+"
NEXT y%
PRINT "+-+-+-+-+-+-+-+-+-+"
|
Ohne das würde man gar nicht sehen, was der Algorithmus fabriziert.
Und zum Lösungsalgorithmus muss man sich einfach nur überlegen, dass es sehr einfache Regeln für ein Sudoku gibt: In einer Zeile, in einer Spalte und einem Kasten darf jede Ziffer nur einmal vorkommen. Dabei spalten sich die Lösungsmöglichkeiten auf. Meine Lösung war eine dritte Dimension im Feld:
| Code: |
DIM kaestchen&(9, 9, 10)
|
Die dritte Dimension speichert, welche Ziffern in dem Kästchen noch möglich sind, ungültige Lösungen werden eliminiert. JETZT macht die Initialisierung Sinn:
| Code: |
FOR y%=0 TO 8
FOR x%=0 TO 8
kaestchen&(x%,y%,0)=0
FOR z%=1 TO 9
kaestchen&(x%,y%,z%)=1
NEXT z%
NEXT x%
NEXT y%
|
In der dritten Dimension speichern wir, welche Ziffern in dem Kästchen noch möglich sind. Sobald für ein Kästchen nur noch ein Z -Eintrag mit dem Wert 1 übrig bleibt, ist der Fall klar, den Wert von Z tragen wir dann im Feld mit Z=0 ein, also kaestchen(x%,y%,0)=z% - ist nicht in dem obigen Code gemeint, sondern analog im Lösungsalgorithmus !
Zwecks Codeoptimierung schauen wir immer im Kästchen(x,y,0) zuerst rein: ist der Wert 0, ist das Kästchen noch nicht gelöst, die Werte 1-9 verraten den Inhalt. Das ist effizienter, statt alle 9 (x,y,z) mit z=1-9 durchzugehen und zu schauen, ob nur ein einziges Feld noch 1 (bzw. besser: ungleich 0) ist.
Ne Zeile im Sudoku sind alle x mit einem bestimmten y-Wert. Ne Spalte alle y mit einem bestimmten x-Wert, und die Kasten sind x und y von 0-2, 3-5 oder 6-8. "Der Modulo-Operator" liefert uns den Teilungsrest: x% MOD 3 liefert den Rest einer Teilung durch 3. Ist der Wert 0, ist x% genau durch 3 teilbar (und kann auch 0 sein).
Bei Integeroperationen fällt der Nachkommaanteil eh weg: INT(x%/3)*3 liefert dir automatisch den x-Startwert aller Kästen: 0, 3 oder 6.
Krieg' erst mal den "Sudoku Viewer/Editor" zum Laufen, dann schauen wir weiter. Wie angedroht, kann der Lösungsalgorithmus in eine Endlosschleife rennen, denn manche Sudokus haben entweder zwei Lösungen, oder eine Lösung die sich mehr oder weniger durch Ausprobieren zwei völlig gültiger Zahlen erst später ergibt. In der Regel löst man Sudokus aber einfach nur durch Schlussfolgerung. |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4664
Wohnort: ~/
|
| Verfasst am: 27.11.2024, 18:50 Titel: |
|
|
Ich habe head und tail in eine PN verbannt. :D
| Zitat: | | Der Lehrer hasst mich. Warum sollte er sonst ausgerechnet meine Ergebnisse immer wieder als falsch bewerten? Passt ihm meine Nase nicht oder meine Herkunft oder meine Religion oder, oder, oder....? |
Zu deiner Beruhigung: Ich beurteile keinen Schüler nach Herkunft oder Religion. Es ist ausschließlich die Nase.
Jetzt aber wieder ernsthaft:
| Revilo hat Folgendes geschrieben: | Hallo nemored,
1) Das zu bearbeitende Sudoku ist geladen, die Ersteinträge sind erfolgt.
2) Je nach dem, wie viele freie Zellen es danach noch gibt, gibt es gleich viele Backtracking - Ebenen. richtig? |
Wenn du reines Backtracking ohne irgendwelche Modifikationen durchführst, gibt es so viele Rekursionsebenen, wie du zu Beginn leere Felder hast. Nicht alle Schritte führen aber notwendigerweise immer bis zur tiefsten Ebene.
| Revilo hat Folgendes geschrieben: | 3) Jede Backtracking - Ebene "kümmert" sich grundsätzlich nur um eine
einzige Zelle, also quasi um ihre "eigene persönliche Privatzelle". richtig?
4) Wie nachfolgende Zellen behandelt werden, ist Sache der nachfolgenden Backtracking-Ebenen. richtig?
5) Beim Starten des Backtrackings sucht das Programm also nach der ersten Zelle, die noch nicht sicher festgelegt ist, wo also noch Einträge möglich sind. richtig?
6) Ist eine freie Zelle gefunden, klappert das Programm alle Werte von 1 - 9
ab, ob sie noch "erlaubt" sind. Ein Wert w ist nicht mehr erlaubt, wenn er bereits in derselben Zeile oder derselben Spalte oder im jeweiligen Block vorkommt. (Sudoku-Regel) richtig?
7) Ist ein Wert w noch erlaubt, wird er "probeweise" dort eingetragen.
Er ist zwar nur probeweise, wird den nachfolgenden "Instanzen" aber als bereits gesichert "verkauft". richtig?
8) diese suchen dann erneut nach einer (noch) freien Zelle, und rufen Backtracking erneut auf, aber unter der Annahme, dass w als bereits sicher gilt. richtig? |
Soweit richtig.
| Revilo hat Folgendes geschrieben: | 9) Das läuft solange durch, bis sich ein Fehler, eine Sackgasse ergibt.
Definition Sackgasse: Es gibt eine noch leere Zelle, in die aber kein Wert w mehr eingetragen werden kann. richtig?
Gibt es weitere Definitionen für eine Sackgasse? |
Das ist die einzige Form von Sackgasse, die aber nach oben durchgereicht wird. Für die aktuelle Rekursionsebene bedeutet das: Ich habe ein freies Feld gefunden, alle Zahlen von 1 bis 9 durchprobiert und festgestellt, dass keine eingesetzt werden darf - entweder, weil die Zahl schon in der Zeile/Spalte/Block vorkommt oder weil sie von der Unterebene "abgelehnt" wurde.
Bekommt eine Rekursionsebene von ihrer Unterebene die Rückmeldung "Sackgasse", weiß sie, dass die aktuell ausprobierte Zahl nicht funktioniert.
| Revilo hat Folgendes geschrieben: | 10) Wie würde es ab hier weitergehen?
Spätestens hier kommen doch True und False in's Spiel. |
Wenn die Rekursionsebene eine Sackgasse feststellt, gibt sie False zurück, um "nach oben" zu signalisieren, dass der aktuelle Versuch nicht funktioniert.
Wenn die Rekursionsebene kein leeres Feld mehr findet, wurden offensichtlich alle Felder passend ausgefüllt, und sie gibt True zurück. Des Weiteren gibt sie True zurück, wenn sie von der Unterebene True geliefert bekommen hat. Das True wird also nach oben durchgereicht, um jeder Rekursionsebene zu signalisieren: "Jetzt nichts mehr anfassen - wir haben die Lösung!"
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
Revilo
Anmeldungsdatum: 26.12.2022
Beiträge: 123
|
| Verfasst am: 29.11.2024, 17:39 Titel: |
|
|
Hallo nemored,
Berkeley schrieb mir folgendes:
| Zitat: | | Ich wiederhole mich nur ungern: Rekursion ist hierfür nicht nötig. Und als "Rekursion" bezeichnet man, wenn ein Unterprogramm sich selbst aufruft - und sich natürlich Daten übergibt. |
Du schreibst über Backtracking, sprichst aber von "Rekursionsebenen". Sorry, aber das verwirrt mich etwas.
Backtracking ruft sich doch auch immer wieder selbst auf, so wie die Rekursion es ja auch tut. Beides ist doch letztlich dieselbe Vorgehensweise, folgt also demselben Schema.
Für Backtracking, wie du es beschreibst, ist Rekursion quasi zwingender Bestandteil des Verfahrens. Für Berkeley ist Rekursion offenbar nicht nötig.
Was gilt denn nun?
Gruß Revilo |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4664
Wohnort: ~/
|
| Verfasst am: 29.11.2024, 20:42 Titel: |
|
|
Backtracking ist der Rücksetz-Algorithmus, also "versuche der Reihe nach alle Möglichkeiten, und wenn es nicht klappt, setze zurück". Das lässt sich auch iterativ lösen, ist rekursiv aber meist eleganter. Meiner Ansicht nach ist ein iterativer Backtracking-Sudoku-Löser unnötig kompliziert und nicht leichter zu verstehen.
@Berkeley:
Du kannst jederzeit mit -exx kompilieren, wenn du Speicherzugriffsfehler vermeiden willst. Automatische Überprüfungen von Grenzen kosten halt Rechenzeit.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
Berkeley
Anmeldungsdatum: 13.05.2024
Beiträge: 74
|
| Verfasst am: 29.11.2024, 21:39 Titel: |
|
|
| Revilo hat Folgendes geschrieben: |
Du schreibst über Backtracking, sprichst aber von "Rekursionsebenen". Sorry, aber das verwirrt mich etwas.
Backtracking ruft sich doch auch immer wieder selbst auf, so wie die Rekursion es ja auch tut. Beides ist doch letztlich dieselbe Vorgehensweise, folgt also demselben Schema. |
"Backtracking" ist englisch und heißt einfach "Zurückverfolgen". Wie Spurenlesen. Das MUSS u.a. auch keine Rekursion beinhalten. Und meistens benutzt man das eher im Zusammenhang mit Debugging, also wenn man Fehler in einem Programm sucht, aber auch Reverse Engineering.
Genauso ist Rekursion ein allgemeiner Begriff, der bei Programmiersprachen wie gesagt aber eine Eigenschaft von Unterprogrammen="Funktionen" bezeichnet, nämlich, dass sie sich selbst aufrufen können. Diese Rekursion vereinfacht dir die Arbeit erheblich, weil die Programmiersprache sich um die komplizierte Zwischenspeicherei kümmert.
- In C bezeichnet man alle Unterprogramme einfach als "Funktion", egal, ob sie einen Wert zurückgeben oder nicht. Bei letzterem ist der "Rückgabewert" der Funktion schlicht der "Datentyp" "void", also "nichts". BASIC unterscheidet aber zwischen SUBs und FUNCTIONs. Ein Unterprogramm, u.a. auch "Prozedur" genannt - SUB(routine) => "Unter-Routine" ist einfach ein Stück Code, den man im Programm immer wieder verwendet. Jeder Befehl wie PRINT ist prinzipiell auch nur ein Unterprogramm/Funktion.
nemoreds Beispiel mit dem rekursiven Ordnerdurchsuchen ist großartig. Du hast ja diese DIR-Funktion mit der du dir jedes Objekt in einem Verzeichnis geben lassen kannst. Ein Verzeichnis kann aber Unterverzeichnisse enthalten und diese wiederum Unterverzeichnisse. Wenn du alle enthaltenen Dateien in einem Ordner erfassen willst, musst du dich also durch alle Unterordner durchackern.
Deine Funktion ermittelt ein Objekt nach dem anderen in dem angegebenen Ordner. Ist es eine Datei, wird sie dem "Rückgabewert" - einer Liste in dem Fall - hinzugefügt. Sagen wir einfach, es wär' ein String, dem jede neue Datei angehängt wird. Ist es ein Ordner, wird dieser vielleicht auch der Liste hinzugefügt, jenachdem wozu's gut sein soll, aber vorallem ruft sich deine Funktion nochmal selbst auf, mit dem Ordner als Ziel. Dann wird von der Funktion dieser Ordner so bearbeitet wie dein Ursprungsordner. Dieser Schritt ist eine Rekursionsebene, und mit jedem Unterverzeichnis geht es eine Rekursionsebene "höher" (oder "tiefer", wie man will).
Das wiederholt sich so oft wie Unterverzeichnisse in Unterverzeichnissen gefunden werden. Wenn dann irgendwann ein Unterverzeichnis erreicht ist, das keine Unterverzeichnisse mehr enthält, endet die Bearbeitung dieses Unterverzeichnisses mit der letzten Datei die darin gefunden wird, und dann kehrt die Funktion das erste Mal zu ihrem vorherigen Aufruf zurück, steigt eine Rekursionsebene ab. In diesem übergeordneten Ordner ist vermutlich das nächste Objekt wieder ein Ordner, dann geht's gleich wieder eine Rekursionsebene "hoch".
Visualisiert:
+ start
L abc
| L adac
| | L elec
| | wish.txt
| L adec
| abc.inf
L bac
L cab
liesmich.txt
liezl.txt
Wir rufen unsere DIR-Funktion für den Ordner "start" auf - Hauptebene - diese stößt auf den Ordner "abc", ruft sich dann selbst auf für den Ordner "abc" - 1. Rekursionsebene. Dabei stößt sie auf den Ordner "elec", ruft sich selbst auf für den Ordner "elec" - 2. Rekursionsebene. Im Ordner "elec" findet sich nur noch die Datei "wish.txt", dann endet die Suche, Rückkehr zu 1. Rekursionsebene, Ordner "abc". Es geht weiter und der Ordner "adec" wird gefunden, also wieder Selbstaufruf, diesmal für "adec". In dem Ordner adec ist nichts, Rückkehr zur 1. Rekursionsebene, Ordner "abc". Das nächste ist die Datei "abc.inf". Danach wird auch nichts mehr gefunden, Rückkehr zur Hauptebene, Ordner "start". Das nächste ist dann der Ordner "bac". Das Ganze läuft so lange bis die letzte Datei "liezl.txt" gefunden wurde. Danach endet dann auch der allererste Aufruf unserer DIR-Funktion und sie gibt die komplette Liste gefundener Dateien zurück.
So ein Verfahren ist auch z.B. bei klassischen Schachcomputern nötig. Es werden rekursiv alle möglichen Spielverläufe bis zu einer bestimmten Zahl an Zügen vorausberechnet. Der Computer braucht dann "nur noch" den Zug wählen, bei dem das Spiel für ihn am günstigsten läuft... Allerdings potentiert sich die Zahl möglicher Züge pro Runde, und jede zusätzlich berechnete Runde braucht zehnmal oder mehr Rechenzeit als die vorherige.
Mein Lösungsalgorithmus benutzt erst mal keine Rekursion, sondern arbeitet immer wieder alle Kästchen durch, wendet die Sudoku-Regeln an. In den besagten seltenen Sonderfällen wo zwei Ziffern austauschbar sind würde dann Rekursion obendrauf nötig, weil man wie beim Schach ausprobieren muss, welcher Eintrag zu einem gültigen Endergebnis führt. Wie gesagt können auch mehrere richtige Lösungen rauskommen, das berücksichtigt unser Entwurf gar nicht. |
|
| Nach oben |
|
|
Berkeley
Anmeldungsdatum: 13.05.2024
Beiträge: 74
|
| Verfasst am: 29.11.2024, 21:43 Titel: |
|
|
| nemored hat Folgendes geschrieben: |
@Berkeley:
Du kannst jederzeit mit -exx kompilieren, wenn du Speicherzugriffsfehler vermeiden willst. Automatische Überprüfungen von Grenzen kosten halt Rechenzeit. |
Das hilft leider kaum, wenn man mit einem 0-basierten Index arbeitet und aus Unachtsamkeit einen Wert für einen 1-basierten Index verwendet. Wenn man also irgendwo 3 statt 2 nimmt. Klassisches Problem Syntaxfehler vs. semantischer Fehler. |
|
| Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010
Beiträge: 1245
Wohnort: Ruhrpott
|
| Verfasst am: 29.11.2024, 23:05 Titel: |
|
|
Ein ungenutztes Element in einem Array ist doch bei den heutigen Speichergrößen kein Problem mehr. Wenn man ein Array ab Index 0 DIMensioniert und ab Index 1 benutzt, räkeln sich halt 4 oder 8 Bytes untätig im Speicher herum. Was soll's? 
Eventuell kann man das Element 0 noch irgendwie als Zwischenspeicher benutzen...
Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
| Nach oben |
|
|
Berkeley
Anmeldungsdatum: 13.05.2024
Beiträge: 74
|
| Verfasst am: 30.11.2024, 11:45 Titel: |
|
|
| Das Problem ist doch nur, dass man richtig adressiert. Dazu gehört u.a. auch, wenn man "FOR x=0 TO 9" macht, was 10 statt 9 Elemente sind. Eine smarte Debugfunktion könnte prüfen, ob sowohl das niedrigste als auch das höchste Element benutzt werden, und dann Alarm schlagen. Aber die üblichen "Speicherschutz"-Funktionen schlagen höchstens an, wenn man den erlaubten Bereich verlässt. Und für eine klassische Speicherschutzverletzung muss man etliche Bytes über den erlaubten Bereich schreiben, bis man über die Pagegrenze kommt... So bleiben derartige Fehler oftmals unentdeckt. |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4664
Wohnort: ~/
|
| Verfasst am: 30.11.2024, 13:29 Titel: |
|
|
Es steht dir frei, in FreeBASIC Debugging einzusetzen. Oder du lässt deine Schleifen grundsätzlich von LBOUND(array) bis UBOUND(array) laufen. Ich will umgekehrt auch keine Fehlermelder von einem integrierten Debugger, nur weil ich absichtlich nicht das ganze Feld durchlaufen wollte.
Ehrlich gesagt verstehe ich das Problem nicht. Wenn ich fehlerhaft programmieren will, schaffe ich das in jeder Programmiersprache.
| Zitat: | | Und für eine klassische Speicherschutzverletzung muss man etliche Bytes über den erlaubten Bereich schreiben, bis man über die Pagegrenze kommt |
Ein mit -exx kompiliertes Programm bricht ab, sobald du die Arraygrenzen überschreitest. Egal um wie viel.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
Berkeley
Anmeldungsdatum: 13.05.2024
Beiträge: 74
|
| Verfasst am: 30.11.2024, 17:44 Titel: |
|
|
| nemored hat Folgendes geschrieben: | | Es steht dir frei, in FreeBASIC Debugging einzusetzen. |
Was ist DAS für ne Aussage ???
Wie der Name "Debugger" schon sagt, ist das ein Tool mit dem man Fehler im Programm aufspürt - damit man sie beseitigen kann. - So denn die Entwicklungsumgebung über einen Debugger verfügt...
Beim RELEASE macht man ein Release-Build, ohne Debughilfen. Wie du schon sagst: so ein Debug-Build ist viel langsamer, außerdem kann man viel leichter die Quelltexte rekonstruieren, was auch nicht jeder Programmierer will.
| nemored hat Folgendes geschrieben: | | Ehrlich gesagt verstehe ich das Problem nicht. Wenn ich fehlerhaft programmieren will, schaffe ich das in jeder Programmiersprache. |
Es geht nicht ums Wollen, sondern Können. Natürlich unabsichtlich. Der Nachteil bei FreeBASIC ist eben, dass mit DIM x(9) sowohl x(0) als auch x(9) gültig sind, wenn man sich verhaut, schmeißt da auch -exx keine Warnung. Erst ab x(10). Wie ausgeführt ist natürlich der Vorteil, dass es menschenlesbarer ist. x(9) ist quasi das neunte Feld, und nicht x(8) - leider sowohl als auch.
Bezüglich Speicherschutzverletzung: das wird bei vielen Debugbuilds ja auch gemacht, dass bei neu allozierten Speicherpuffern vorne und hinten Bitmuster geschrieben werden - wenn diese verändert werden, wird Alarm geschlagen. Jedes Byte das außerhalb geschrieben wird wird so sofort entdeckt. Oftmals überschreiten Strings z.B. mit ihrem Nullbyte den Zielpuffer eben nur um ein Byte, weil man z.B. ein "+1" vergessen hat, und das fiele dann ewig nicht auf. |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4664
Wohnort: ~/
|
| Verfasst am: 30.11.2024, 23:05 Titel: |
|
|
Ok, dann formuliere ich es um, wenn es dir so herum lieber ist: Ich kann in jeder Programmiersprache unbeabsichtigte Fehler machen. Vor allem, wenn ich mich nicht ausreichend mit der Dokumentation beschäftige.
Wenn ich Angst hätte, die untere Arraygrenze zu vergessen, würde ich DIM array(1 TO 10) einsetzen; dafür gibt es diese Möglichkeit ja. Deutlich problematischer als das Zählungsbeginn bei 0 (der aus informatorischer Sicht vollkommen Sinn ergibt) finde ich, dass in FreeBASIC einzelne Funktionen aus historischen Gründen dann doch wieder bei 1 zu zählen beginnen. (Das sind aber in der Regel Funktionen, die ich gar nicht verwende.)
Das zusätzliche Byte im FB-String finde ich ebenfalls deutlich weniger intuitiv als ein DIM array(9), denn was DIM array(9) macht, steht in der Dokumentation praktisch gleich an erster Stelle. Für die Speicherverwaltung eines FB-Strings muss man da schon etwas weiter lesen.
Allerdings sind wir jetzt ziemlich vom Thread-Thema abgekommen ...
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
Revilo
Anmeldungsdatum: 26.12.2022
Beiträge: 123
|
| Verfasst am: 02.12.2024, 00:11 Titel: |
|
|
Hallo nemored,
freudige Nachricht.
Dank deiner und der Hilfe aller anderen bin ich in meinem Programm etwas vorangekommen.
Ersteinträge werden sauber erfasst, positioniert und in den Zeilen, Spalten und Blöcken so weit, wie möglich, eliminiert.
Durch verschiedene (klassische) Lösungsverfahren konnte ich weitere sichere Einträge finden. Aber deren Möglichkeiten sind jetzt ausgeschöpft.
Jetzt geht es also wirklich ans Probieren (Backtracking).
Hierzu mal eine Frage:
Muss man zwingend so weit wie möglich oben links beginnen?
Da könnte man ja auf eine noch freie Zelle treffen, in der z.B. noch 8 Einträge möglich wären. Man müsste also alle 8 Werte der Reihe nach abklappern.
Wäre es zur Beschleunigung des Verfahrens nicht effektiver, wenn man mitten im Lösungsschema mit einer Zelle beginnt, die nur noch 2 mögliche Einträge erlaubt? Einer davon muss ja stimmen.
Es ist doch bestimmt effektiver, nur 2 statt 8 Werte abklappern zu müssen.
Oder würde das den "Spielregeln" des Backtracking widersprechen?
PS: Schönen 1. Advent
Gruß Revilo |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4664
Wohnort: ~/
|
| Verfasst am: 02.12.2024, 13:48 Titel: |
|
|
Du musst mit irgendeinem Feld beginnen; mit welchem, ist zunächst einmal egal. Du kannst also durchaus mit einem Feld beginnen, für das bereits nur noch wenige Optionen bestehen.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
dreael
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 2518
Wohnort: Hofen SH (Schweiz)
|
| Verfasst am: 02.12.2024, 19:53 Titel: |
|
|
| Revilo hat Folgendes geschrieben: | Hierzu mal eine Frage:
Muss man zwingend so weit wie möglich oben links beginnen?
Da könnte man ja auf eine noch freie Zelle treffen, in der z.B. noch 8 Einträge möglich wären. Man müsste also alle 8 Werte der Reihe nach abklappern. |
Und hier greift genau die bei meiner seinerzeit programmierten Version gewählte Optimierung: Noch ohne Rekursion wird überall bestimmt, wieviele Kandidaten es gibt. Anschliessend wird von der Reihenfolge alles so sortiert, dass diejenigen Felder mit am wenigsten möglichen Kandidaten zuerst gefüllt werden, was die Anzahl Rekursionsschritte massiv reduziert.
Deshalb auch die Anregung, testweise einmal verkehrt herum sortieren, was die Rechenzeit sofort massiv erhöht, weil viel mehr Zweige im Rekursionsbaum abgeklappert werden müssen.
_________________
Teste die PC-Sicherheit mit www.sec-check.net |
|
| Nach oben |
|
|
Berkeley
Anmeldungsdatum: 13.05.2024
Beiträge: 74
|
| Verfasst am: 02.12.2024, 20:40 Titel: |
|
|
| Revilo hat Folgendes geschrieben: |
Wäre es zur Beschleunigung des Verfahrens nicht effektiver, wenn man mitten im Lösungsschema mit einer Zelle beginnt, die nur noch 2 mögliche Einträge erlaubt? |
Bzw. die wenigsten möglichen Einträge.
Das ist klassische Optimierung eines Algorithmus. Es ist vorallem für den Programmierer aufwändiger, dafür spart ein Algorithmus dann entweder Speicher oder läuft schneller. Im Fall von gesparten Rekursionebenen sogar beides. Beim Sudokuproblem und den üppigen Ressourcen spielt es aber keine Rolle.
| dreael hat Folgendes geschrieben: |
Und hier greift genau die bei meiner seinerzeit programmierten Version gewählte Optimierung: Noch ohne Rekursion wird überall bestimmt, wieviele Kandidaten es gibt. Anschliessend wird von der Reihenfolge alles so sortiert, dass diejenigen Felder mit am wenigsten möglichen Kandidaten zuerst gefüllt werden, was die Anzahl Rekursionsschritte massiv reduziert. |
Es ist effizienter, mit einem "flachen" Algorithmus an das Problem ranzugehen, so lange, bis es nicht mehr weitergeht. "Flach" heißt: es gibt keine Rekursion, sondern es wird jedes Kästchen von 0|0 bis 8|8 immer wieder abgearbeitet, bis sich nichts mehr ändert.
Für jedes Kästchen wird gespeichert, welche Ziffern möglich sind, beginnend natürlich mit 1-9. Wird ein Kästchen ermittelt, wird dessen Wert für alle damit zusammenhängenden Kästchen - Zeile, Spalte, Kasten - gelöscht. Bleibt nur eine Möglichkeit übrig, wird diese gesetzt, und für alle damit zusammenhängenden Kästchen gelöscht. So lange, bis sich bei einem Durchlauf aller Kästchen nichts mehr ändert, was meistens der Fall sein dürfte, wenn das Sudoku gelöst wurde.
Hier gibt's auch einige Optimierungsmöglichkeiten, u.a. braucht man ein Kästchen, das bereits ermittelt wurde(gesetzt ist), nicht mehr abarbeiten. => IF kaestchen(x%,y%,0)=0 THEN ... Ist der Wert ungleich 0, also 1-9, kann man die Bearbeitung überspringen. Man muss nur prüfen, ob nur noch eine Möglichkeit übrig ist, und in dem Fall das Kästchen setzen, wobei alle daran hängenden Kästchen aktualisiert werden. |
|
| Nach oben |
|
|
Revilo
Anmeldungsdatum: 26.12.2022
Beiträge: 123
|
| Verfasst am: 03.12.2024, 17:07 Titel: |
|
|
Hallo Berkeley,
| Zitat: | Für jedes Kästchen wird gespeichert, welche Ziffern möglich sind, beginnend natürlich mit 1-9. Wird ein Kästchen ermittelt, wird dessen Wert für alle damit zusammenhängenden Kästchen - Zeile, Spalte, Kasten - gelöscht. Bleibt nur eine Möglichkeit übrig, wird diese gesetzt, und für alle damit zusammenhängenden Kästchen gelöscht. So lange, bis sich bei einem Durchlauf aller Kästchen nichts mehr ändert, was meistens der Fall sein dürfte, wenn das Sudoku gelöst wurde.
|
Das meinte ich mit "klassisch". Entspricht ja etwa dem "Scannen" bei manueller Lösung eines Sudokus. Ich nenne es mal "Solosuche".
Also die Suche nach Zellen, in denen nur noch ein Wert w möglich ist.
Jedes gefundene Solo wird eingetragen und in den betreffenden Nachbarzellen eliminiert, so als wäre es schon zu Anfang vorgegeben gewesen. Soweit läuft mein Programm ja auch.
Aber erfahrungsgemäß ist mit der "Solosuche" irgend wann Schluss. Es gibt keine Verbesserung also keinen weiteren Lösungsfortschritt mehr.
Jetzt müsste man sich der über 40 Lösungsverfahren bedienen. Also Suche nach Zwillingen, Drillingen, Vierlingen... um nur einige zu nennen.
Sie alle führen entweder zu neuen Solos oder schließen zumindest aus, was nicht mehr möglich ist.
Diese über 40 Verfahren der Reihe nach zu programmieren, weil man ja nie weiß, ob und wann sie mal gebraucht werden könnten, ist mir zu zeitaufwendig, zumal man sie ja erst mal logisch verstanden haben muss, um sich an deren Programmierung wagen zu können.
Hier beginnt also das Probieren:
Manuell würde man jetzt zu Bleistift und Radiergummi greifen.
Digital wäre das Backtracking quasi "Bleistift und Radiergummi".
Und genau hier klemmt es. Ich kriege es einfach nicht hin.
Ich habe noch nicht mal eine Vorstellung, welche Befehle dazu überhaupt nötig wären, geschweige denn in welcher Reihenfolge sie einzugeben wären.
Ferner weiß ich nicht, welche Funktionen für das Backtracking überhaupt zuvor eingerichtet werden müssen und in welcher Reihenfolge sie abgearbeitet werden müssen.
Wenn meine "klassische" Vorgehensweise keinen Fortschritt mehr bringt,
steht in meinem Programm:
Print "Klassisch ohne Fortschritt, --> Backtracking": SLEEP
(soweit bin ich bisher gekommen)
Aber ich habe keinerlei Vorstellung, wie es ab jetzt weitergehen müsste.
Gruß Revilo |
|
| Nach oben |
|
|
Berkeley
Anmeldungsdatum: 13.05.2024
Beiträge: 74
|
| Verfasst am: 03.12.2024, 18:45 Titel: |
|
|
| Revilo hat Folgendes geschrieben: |
Das meinte ich mit "klassisch". Entspricht ja etwa dem "Scannen" bei manueller Lösung eines Sudokus. Ich nenne es mal "Solosuche". Also die Suche nach Zellen, in denen nur noch ein Wert w möglich ist.
Jedes gefundene Solo wird eingetragen und in den betreffenden Nachbarzellen eliminiert, so als wäre es schon zu Anfang vorgegeben gewesen. Soweit läuft mein Programm ja auch.
Aber erfahrungsgemäß ist mit der "Solosuche" irgend wann Schluss. Es gibt keine Verbesserung also keinen weiteren Lösungsfortschritt mehr. |
Hab' leider nicht die Zeit es selbst auszuprobieren, aber IMO müsste der Algorithmus mindestens 80% aller Sudokus lösen können.
Das mit der Rekursion ist in der Tat ziemlich kompliziert, du musst deine Schritte speichern, und wenn's fehlschlägt, wieder rückgängig machen. Den Stand deines Sudokus immer wieder kopieren, einen Wert ausprobieren, und den "flachen" Algorithmus anwenden bis nichts mehr geht.
Am einfachsten ist, wenn dein Algorithmus ganz stur von links oben nach rechts unten alle Kästchen aufsteigend mit allen möglichen Werten durchexerziert. Besser ist eine äußere Schleife, die zuerst alle Kästchen systematisch durchexerziert, für die es 2 mögliche Werte gibt, dann 3 usw. Also so:
| Code: |
FOR i = 2 TO 9
FOR y = 0 TO 8
FOR x = 0 TO 8
...
NEXT
NEXT
NEXT |
Einmal im ganzen Sudoku Kästchen mit 2 möglichen Werten suchen und abarbeiten, dann im ganzen Sudoku Kästchen mit 3 möglichen Werten, usw. bis zu 9 möglichen Werten - was eigentlich auf keinen Fall je erreicht werden sollte und sicher auch zu keiner Lösung mehr führen könnte.
Für deine Sudoku-Kopie brauchst du lokale Variablen, speziell ein Array. Kann aber nicht sagen wie das bei QBasic ausschaut. Du musst dein aktuelles Array mit "BYREF" (als Pointer/Adresse) übergeben, und dann Wert für Wert in dein neues lokales Array kopieren, welches du ggf. an die nächste Rekursionsebene weiterreichst...
| Code: |
FUNCTION ichrufmichselbst(versuch)
...
FOR i = 1 to 9
IF ichrufmichselbst(i)=TRUE THEN EXIT
NEXT
...
END FUNCTION
... |
So in etwa schaut Rekursion aus, du hast hier eine Schleife und die ruft hier bis zu 9 mal die Funktion in der sie ist auf, unabhängig von ihrer Rekursionsebene. Du übergibst ihr aktuelle Daten und jenachdem geht es immer tiefer oder ein Ergebnis wird gefunden und zurückgeliefert, bis zur Hauptprogramm-Ebene. Je Rekursionsebene oder besser gesagt "Instanz" kannst du also eine Funktion beliebig oft sich selbst aufrufen lassen um alle Möglichkeiten durchzuprobieren.
- "Instanz" deshalb, weil damit die Funktion in einem ganz bestimmten Zustand gemeint ist, nicht nur auf derselben Rekursionsebene. Beim Beispiel mit den Ordnern/Verzeichnissen wär's z.B. der Funktionsaufruf für den Ordner "abc". - "bac" und "cab" wären auch auf derselben Rekursionsebene, aber eben nicht mit identischen Daten. Von "abc" ausgehend werden alle Unterordner durchsucht, und der Algorithmus kehrt dann immer wieder zu "abc" zurück. |
|
| Nach oben |
|
|
dreael
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 2518
Wohnort: Hofen SH (Schweiz)
|
| Verfasst am: 03.12.2024, 20:59 Titel: |
|
|
| Berkeley hat Folgendes geschrieben: | | Es ist effizienter, mit einem "flachen" Algorithmus an das Problem ranzugehen, so lange, bis es nicht mehr weitergeht. "Flach" heißt: es gibt keine Rekursion, sondern es wird jedes Kästchen von 0|0 bis 8|8 immer wieder abgearbeitet, bis sich nichts mehr ändert. |
In der seinerzeitig bereitgestellten ZIP-Datei gibt es auch noch eine alternative Version, welche visuell Schritt für Schritt ein Sudoku so löst (kann man per Tastendruck wie ein Powerpoint bedienen), wie man es von Hand üblicherweise lösen würde. Kommt logischerweise ohne Rekursion aus, kann aber dafür nicht jedes Suduku lösen.
Als ich Sudokus erstmals kennenlernte, hatte ich gleich ans PC das Rätsel lösen lassen gedacht und so übrigens die Version mit Rekursion entstehen lassen, die jedes Rätsel lösen kann. Hat dank der genannten Optimierung schon ganz früh mit älterer Hardware (Pentium 4 damals) und sogar nur 16-Bit-MS-DOS recht effizient funktioniert.
Erst später hatte ich mich dann auch fürs händische Lösen zu interessieren begonnen, so ist die zuvor genannte Version ohne Rekursion entstanden.
_________________
Teste die PC-Sicherheit mit www.sec-check.net |
|
| Nach oben |
|
|
SpionAtom
Anmeldungsdatum: 10.01.2005
Beiträge: 356
|
| Verfasst am: 04.12.2024, 10:00 Titel: |
|
|
| Revilo hat Folgendes geschrieben: | Hier beginnt also das Probieren:
Manuell würde man jetzt zu Bleistift und Radiergummi greifen.
Digital wäre das Backtracking quasi "Bleistift und Radiergummi".
Und genau hier klemmt es. Ich kriege es einfach nicht hin.
Ich habe noch nicht mal eine Vorstellung, welche Befehle dazu überhaupt nötig wären, geschweige denn in welcher Reihenfolge sie einzugeben wären.
Ferner weiß ich nicht, welche Funktionen für das Backtracking überhaupt zuvor eingerichtet werden müssen und in welcher Reihenfolge sie abgearbeitet werden müssen.
[...]
Aber ich habe keinerlei Vorstellung, wie es ab jetzt weitergehen müsste.
|
Hier ist das Dilemma, welches ich mit dir habe: Einerseits bist du hochmotiviert, andererseits ist deine Erfahrung mit Algorithmen zu gering, als dass ich dir zu einer Implementierung eines Sudoku-Backtracking raten würde.
Die Leute hier versuchen dir Konzepte von boolscher Algebra, Funktionen, Rückgabewerten, Rekursion, usw. näher zu bringen. Denn es ist unverzichtbar für einen komplexen Backtracking-Algorithmus, der auch noch mit einem mehrdimensionalen Array hantiert, dass man jedes dieser Konzepte wirklich gut verstanden haben muss und auch anwenden kann. Und da ist meine Prognose leider, dass dir da noch einiges an Erfahrung fehlt.
Man muss erst kriechen um später zu laufen.
Mir gefällt, dass du ein konkretes Problem hast, und alle nötigen Schritte zur Problembewältigung angehen willst. Jedoch reicht es einfach nicht, die Schritte nur zu kennen, man muss sie gehen - und das ist kleinschrittig und kostet Zeit. Alle Konzepte, die hier angesprochen wurden, würden vermutlich ein ganzes Semester füllen.
Und der Spaß am Programmieren ist - meiner Meinung nach - nicht nur das Endergebnis, welches man präsentieren kann, sondern der Weg dahin, das selber ausprobieren und tüfteln.
Mein Tipp ist nach wie vor: Fang mit kleineren Problemen an. Davon hast du mehr, als wenn man dir alles vorkaut und du nur die Musterlösung abschreibst.
Entschuldige meine Negativität, aber ich bin davon überzeugt, dass du ohne Grundlagenkenntnisse nicht wirklich etwas lernst. Und dafür gibt es keine Abkürzung.
Hier ist meine Analogie zum Zeichnen:
Wenn du irgendwann etwas komplexes Zeichnen können willst, wie schicke Häuser, oder Figuren und Gesichter, solltest du dich erst mit Grundlagen auseinandersetzen: Linien, Formen, Proportionen, Perspektive. Und zwar viele Stunden lang.
Um auf einer positiven Note zu enden: Es ist nie zu spät damit anzufangen, Einen Marathon läuft man mit vielen kleinen Schritten. 
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht. |
|
| Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
