Backtracking Algorithmus

Status
Nicht offen für weitere Antworten.
Werte Javagenossen,

Euer JavaMaximum5000 braucht eure Hilfe. Folgendes:
Es geht um die Erstellung eines Sudokus mittls dem Backtracking Algorithmus. Ich weiss nicht ob ich
das Vorgehen richtig verstanden habe. Funktioniert er so:

1. Ein Array[][] mit 9*9 Elementen
2. Ich generiere eine Zeile mit den Zahlen von 1 bis 9 die zufällig angeordnet werden und zeilenweise
in das Array.
3. Nach jeder neuen Zeile prüfe ich ob die neueste mit den vorherigen im Regeleinklang steht.
4. Falls nein wird die letzte Zeile nochmals generiert.
5. Die Schritte 2 - 4 werden so lange wiederholt bist das Sudoku regelkonform mit Zahlen gefüllt ist.

Stimmt das so?

Euer JavaMaximum5000
 

Dante

Bekanntes Mitglied
hi,

evtl. musst du mehr als eine zeile zurückgehen, ansonsten sollte das so funktionieren.
 
Meinen Dank zum Gruß. Whoer weiss wie viele Schritte ich zurückgehen muss? Wenn ich immer nur einen zurückgehe wird es ja nichts. Gibt es eine feste Anzahl an Schritten?
 
G

Gast

Gast
Ich kann dir leider nicht weiterhelfen, wollte nur sagen, dass ich ein ähnliches Problem habe.
 

mikachu

Top Contributor
Das ist IMO ein guter Kandidat für eine rekursive Anweisung.
Das erfordert aber ein genaues Verständnis über Rekursion allgemein.
Wann wo Abbruchbedingungen einbauen und was wo wie handlen.
 

mikachu

Top Contributor
Wenn die schon rekursiv ist, dann musst du dir keine Gedanken über die Schritte machen, wieviele zurückgegangen werden.
Das meine ich mit den Abbruchbedinungen.
 
S

SlaterB

Gast
ds Problem ist hier, dass eine Zeile zufällig generiert wird,
so ist es unmöglich festzustellen, dass alle Zeilen falsch sind und dann in die nächsthöhere Ebene zu gehen
 

mikachu

Top Contributor
stimmt...
du musst bei jeder neuen Zeile eh alle anderen, schon erstellten Zeilen mit der neu erstellten auf die Regeln prüfen.
Verdammt harte Knochenarbeit :wink:
 
also würde ich immer die Zeilen erzeugen und wenn ich genug habe die Blöcke prüfen. Wenn die Blöcke nicht passen muss ich z.B. die letzten drei Zeilen neu erzeugen...usw.
 

Dante

Bekanntes Mitglied
beim backtracking ist es wichtig zu wissen, welche lösungen man schon ausprobiert hat, sonst kann die kiste ja ewig rechnen.

daher könnte es für das sudoku-probvlem besser sein, wenn man das nicht zeilenweise macht.

wenn du dir das problem genau überlegst, wirst du darauf kommen, das du hier einen baum entlang gehst. im wurzelknoten hast du zB. 9 entscheidungen für das erste feld (0,0), danach hast du 8 entscheidungen für das zweite feld (1,0), usw..

der baum ist natürlich sehr groß, daher nimmt man auch backtracking. wenn du dir in diesem baum nun alle kanten markierst, die du bereits 'gegangen' bist, dann merkst du auch, wenn du in einer sackgasse steckst. in diesme falle gehst du einen schritt zurück, also die elternkante des knotens zurück nach oben. wenn dort auch schon alles abgegrast ist, gehst du noch weiter nach oben.

das ist die theorie, die kann man nun mehr oder weniger intelligent auf dein problem anwenden. du könntest zum beispiel jedes feld geordnet hochzählen, sprich du fängst mit dem ersten möglichen wert an (1) und probierst aus, wenn es nicht geht, gehst du zurück und tust den nächsthöheren wert hinein. wenn du beim letzten wert angekommen bist, weisst du, das du noch ein feld zurückmusst, da hier alles abgegrast ist. in diesem falle löschst du das aktuelle feld, gehst eins zurück und erhöhst dieses (und das dann rekursiv bis du eine lösung hast).

das ist, sagen wir mal einer der weniger intelligenten wege, aber er macht denke ich deutlich, worauf es ankommt. du kannst dir nun natürlich noch zig optimierungen überlegen, sudoku bietet da ja durchaus ansätze ;)
 

Marco13

Top Contributor
Das mit dem zufälligen Generieren klingt ungünstig. Das ist dann sozusagen ein "Zustand mittendrin", also ein Zustand, den man "irgendwann während des Backtrackings" erreicht hätte. Das einfache (und langsame :roll: ) beim Backtracking ist ja, dass man einfach ALLE Kombinationen durchprobiert. Sinngemäß und EXTREM Pseudocodig (eher eine Mischung aus Code und Trace) wäre das dann sowas:
Code:
Setze auf das 1. Feld, wo die 1. Zahl hinpasst
    Setze auf das 1. Feld, wo die 2. Zahl hinpasst
        Setze auf das 1. Feld, wo die 3. Zahl hinpasst
            ...
            Setze auf das 1. Feld, wo die 80. Zahl hinpasst
                Setze auf das 1. Feld, wo die 81. Zahl hinpasst
                Wenn du fertig bist 
                     Gib das ergebnis aus und ende

                Setze auf das 2. Feld, wo die 81. Zahl hinpasst
                Wenn du fertig bist 
                     Gib das ergebnis aus und ende

                Setze auf das 3. Feld, wo die 81. Zahl hinpasst
                Wenn du fertig bist 
                     Gib das ergebnis aus und ende
                ...

                Setze auf das letzte Feld, wo die 81. Zahl hinpasst
                Wenn du fertig bist 
                     Gib das ergebnis aus und ende
                
                Die 81. Zahl hat nirgends hingepasst

            Setze auf das 2. Feld, wo die 80. Zahl hinpasst

                Setze auf das 1. Feld, wo die 81. Zahl hinpasst
                Wenn du fertig bist 
                     Gib das ergebnis aus und ende

                Setze auf das 2. Feld, wo die 81. Zahl hinpasst
                Wenn du fertig bist 
                     Gib das ergebnis aus und ende
                ...

                Setze auf das letzte Feld, wo die 81. Zahl hinpasst
                Wenn du fertig bist 
                     Gib das ergebnis aus und ende
                
                Die 81. Zahl hat nirgends hingepasst
            ...

            Setze auf das letzte. Feld, wo die 80. Zahl hinpasst

                Setze auf das 1. Feld, wo die 81. Zahl hinpasst
                Wenn du fertig bist 
                     Gib das ergebnis aus und ende

                Setze auf das 2. Feld, wo die 81. Zahl hinpasst
                Wenn du fertig bist 
                     Gib das ergebnis aus und ende
                ...

                Setze auf das letzte Feld, wo die 81. Zahl hinpasst
                Wenn du fertig bist 
                     Gib das ergebnis aus und ende
                
                Die 81. Zahl hat nirgends hingepasst
           Die 80. Zahl hat nirgends hingepasst
    ....
....

Naja. Fertiger code wäre vielleicht weniger gewesen :D
 
JavaMaximum500 hat verstanden. Also:

1. Es werden in einem Zahlenarray[81][1] Zahlen erzeugt. Die 81 Zahlen sind immer von 1-9 zufällig erzeugte zahlen. Die [1] zeigt an ob die Zahl schon ins Spielfeld gesetzt wurde. (wenn 0 nein wenn 1 ja)

2. Es gibt ein Spielfeld[9][9] mit lauter Nullen.

3. In dem Zahlenarray wird die erste Zahl (an Stelle [0][0]) genommen und in das Speilfeld gesetzt. Die Gültigkeit wird auf 1 gesetzt.

4. Es wird geprüft ob die Zahl regelkonform in das Spielfeld gesetzt werden kann( an der 1. passenden Position). Fall die Position nicht ok ist wird sie auf das 2. mögliche Feld gesetzt. usw.

5. Sollte die Zahl nicht platziert werden könen wird die zuvorige Zahl auf die nächste mögliche Stelle gesetzt. (quasi einen Schritt rückwärts)

6. Die vorherige Zahl wird erneut versucht.

Das ganze wird so lange gemacht bis alle 81 Zahlen gesetzt wurden.

Kommt das so hin
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
Max246Sch 3D Box Filler BAcktracking Java Basics - Anfänger-Themen 1
P Frage zu Rekursion und Backtracking Java Basics - Anfänger-Themen 2
districon Backtracking Java Basics - Anfänger-Themen 2
districon Backtracking Java Basics - Anfänger-Themen 14
districon Dynamisch Programmierung/Backtracking/Memoization Java Basics - Anfänger-Themen 3
districon Backtracking funktioniert nicht ganz Java Basics - Anfänger-Themen 3
V Backtracking und Rekursion Java Basics - Anfänger-Themen 15
G Subset sum problem mit Backtracking Java Basics - Anfänger-Themen 18
O Backtracking Java Basics - Anfänger-Themen 5
C Rekursives Backtracking beim Spiel Peg Java Basics - Anfänger-Themen 22
A Backtracking Java Basics - Anfänger-Themen 56
R Backtracking Java Basics - Anfänger-Themen 1
V Feld sortieren mit Backtracking Java Basics - Anfänger-Themen 1
A Sudoku mit Backtracking lösen Java Basics - Anfänger-Themen 3
L Sudoku Backtracking Pseudocode Java Basics - Anfänger-Themen 3
N Backtracking - Labyrinth/Irrgarten Java Basics - Anfänger-Themen 14
I Backtracking Schach Java Basics - Anfänger-Themen 5
L Magisches Quadrat und Backtracking Java Basics - Anfänger-Themen 19
M Backtracking/Solve Methode Java Basics - Anfänger-Themen 7
P Labyrinth, Backtracking, verzögerte Anzeige Java Basics - Anfänger-Themen 15
D Sudoku lösen mit Backtracking Java Basics - Anfänger-Themen 20
E backtracking und Induktionsprinzip Java Basics - Anfänger-Themen 2
D Backtracking Waage Problem Java Basics - Anfänger-Themen 23
N Backtracking Solohalma Java Basics - Anfänger-Themen 2
W Backtracking und Frustration Java Basics - Anfänger-Themen 6
X Sudoku Backtracking Java Basics - Anfänger-Themen 6
J Solitaire via Backtracking Java Basics - Anfänger-Themen 7
A Backtracking - kennt Java keine Rücksprungmarken? Java Basics - Anfänger-Themen 15
G Backtracking mit globaler Variable Java Basics - Anfänger-Themen 5
M BackTracking Java Basics - Anfänger-Themen 22
laxla123 Eigenschaften eines Algorithmus (determiniert vs.. deterministisch) Java Basics - Anfänger-Themen 2
C Gewinnspiel erstellen mit Algorithmus Java Basics - Anfänger-Themen 3
C negamax-Algorithmus für Tic-Tac-Toe spielt manchmal falsch Java Basics - Anfänger-Themen 10
H Minimax Algorithmus in Tic Tac Toe Java Basics - Anfänger-Themen 3
M Minimax-Algorithmus für Vier gewinnt Java Basics - Anfänger-Themen 11
ohneInformatik; Trockentest Algorithmus, mathematischen Zusammenhang angeben Java Basics - Anfänger-Themen 3
M Minimax-Algorithmus Java Basics - Anfänger-Themen 17
mervanpolat Binary Search Algorithmus ausführen Java Basics - Anfänger-Themen 1
J Rekursiver Algorithmus Java Basics - Anfänger-Themen 9
M monte carlo Algorithmus für 4 gewinnt Java Basics - Anfänger-Themen 12
izoards Sortier Algorithmus für Bounding Box Elememte Links nach Rechts und von Oben nach Unten Java Basics - Anfänger-Themen 33
S Algorithmus entwicklen, der zu einem gegebenen Datum die Jahreszeit ermittelt Java Basics - Anfänger-Themen 13
rosima26 Merge-Algorithmus Java Basics - Anfänger-Themen 53
C Ein Algorithmus soll schneller werden Java Basics - Anfänger-Themen 24
D Dijkstra Algorithmus Hilfe!! Java Basics - Anfänger-Themen 9
U Den Kuchen aufteilen - aber wie? (Rebalancing-Algorithmus) Java Basics - Anfänger-Themen 14
s_1895 Pseudocode Naiver Algorithmus Java Basics - Anfänger-Themen 17
H String verschlüsseln - eigener Algorithmus Java Basics - Anfänger-Themen 104
T Algorithmus für Index mit min-Wert Java Basics - Anfänger-Themen 2
Düsseldorf2002 Testen meines Algorithmus Java Basics - Anfänger-Themen 1
D Primzahlen Rechner nach Eratostenes von Kyrene Algorithmus Java Basics - Anfänger-Themen 2
KogoroMori21 Frage zum Euklidischen Algorithmus Java Basics - Anfänger-Themen 11
S Algorithmus java searchAll IKey Java Basics - Anfänger-Themen 4
S Algorithmus Datensätze einfügen wenn... Java Basics - Anfänger-Themen 26
KogoroMori21 MergeSort Algorithmus Java Basics - Anfänger-Themen 2
KogoroMori21 Textdatei einlesen im Array (Selection Sort Algorithmus) Java Basics - Anfänger-Themen 3
fendix Compiler-Fehler Algorithmus zur Bestimmung von Primzahlen Java Basics - Anfänger-Themen 7
S Algorithmus (reelle Zahl <65536 von dezimal zu dual) max. 10 Nachkommastellen Java Basics - Anfänger-Themen 4
G Algorithmus Graphen Java Basics - Anfänger-Themen 10
D Input/Output fehlerhafter Algorithmus zum Ersetzen von Array-Werten nach logischem Schema Java Basics - Anfänger-Themen 1
N Selection Algorithmus: Methode wird nicht erkannt (BlueJ) Java Basics - Anfänger-Themen 3
U Meinung zum Dijkstra Algorithmus Java Basics - Anfänger-Themen 6
U Dijkstra Algorithmus Laufzeit Java Basics - Anfänger-Themen 3
L Math.exp also eigenen Algorithmus Java Basics - Anfänger-Themen 2
Kirby.exe Algorithmus entwickeln Java Basics - Anfänger-Themen 37
M Algorithmus Max-Heap? Java Basics - Anfänger-Themen 3
I Labyrinth auf der Basis eines rekursiven Algorithmus Java Basics - Anfänger-Themen 27
CptK Best Practice Algorithmus nach jedem Schritt zum Visualisieren pausieren Java Basics - Anfänger-Themen 3
A Algorithmus effizienter machen Java Basics - Anfänger-Themen 1
V Algorithmus zur fortlaufenden Berechnung des duechscjnt Java Basics - Anfänger-Themen 1
M Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen Java Basics - Anfänger-Themen 11
O Labyrinth Algorithmus Java Basics - Anfänger-Themen 3
G Quicksort Algorithmus Java Basics - Anfänger-Themen 12
S Binäre-Suche Algorithmus Java Basics - Anfänger-Themen 1
D Algorithmus in Pseudocode mit log2(n) Operationen erstellen Java Basics - Anfänger-Themen 3
C Laufzeit eines Sortier-Algorithmus ermitteln Java Basics - Anfänger-Themen 4
H aufgabe java luhn algorithmus Java Basics - Anfänger-Themen 10
A Datenstruktur für Savings Algorithmus und Planung von kleinen Programmierprojekten Java Basics - Anfänger-Themen 1
J Algorithmus für eine Reihe implementieren Java Basics - Anfänger-Themen 2
S Dijkstra Algorithmus funktioniert nicht Java Basics - Anfänger-Themen 4
N Denksportaufgabe durch Algorithmus lösen Java Basics - Anfänger-Themen 2
S Problem mit einem rekursivem FloodFill Algorithmus Java Basics - Anfänger-Themen 62
B Algorithmus Square und Multiply Java Basics - Anfänger-Themen 3
J Algorithmus - Strings auf eigene Reihenfolge miteinander vergleichen Java Basics - Anfänger-Themen 4
D Frage Boyer-Moore Algorithmus Java Basics - Anfänger-Themen 7
M Komplexität Algorithmus Java Basics - Anfänger-Themen 8
H Zeichen im algorithmus Java Basics - Anfänger-Themen 4
B Code Verständnisfragen - FLoyd Warshall Algorithmus Java Basics - Anfänger-Themen 1
B Algorithmus zum entmischen einer Zahlenfolge Java Basics - Anfänger-Themen 15
X Minimax-Algorithmus über alle Kanten möglich? - Kanten darstellen Java Basics - Anfänger-Themen 1
T Algorithmus zur Überprüfung eines binären Suchbaums Java Basics - Anfänger-Themen 2
K Best Practice Algorithmus für Berechnung von Zahlenreihenfolge Java Basics - Anfänger-Themen 12
M Simpler Algorithmus läuft extrem langsam. Java Basics - Anfänger-Themen 3
K Erste Schritte Brute Force Algorithmus Java Basics - Anfänger-Themen 2
L Frage zu BubbleSort Algorithmus Java Basics - Anfänger-Themen 2
B gibt es ein Stundenplan-Algorithmus? Java Basics - Anfänger-Themen 11
O Algorithmus-Problem Java Basics - Anfänger-Themen 5
P Euklidischer Algorithmus Java Basics - Anfänger-Themen 9
L Greates Commong Dividend - euklidischer Algorithmus, modulos not positive Java Basics - Anfänger-Themen 5
J Euklidischer Algorithmus Java Basics - Anfänger-Themen 1

Ähnliche Java Themen

Neue Themen


Oben