Servus zusammen,
ich arbeite gerade an einem Programm, das mir Sudokus lösen soll.
Dass es diese schon zu hauf im Internet gibt, ist mir klar(nur um solche Antworten zu vermeiden )
Ich hab auch schon viele Algorithmen gefunden, die funktionieren.
Trotzdem hab ich mir selber noch einen überlegt, der(meiner Meinung nach) theoretisch auch funktionieren sollte, das faktisch aber nicht tut
Mein Algorithmus ist folgender:
-Alle Spalten und Zahlen nacheinander durchlaufen
-Bei jedem Kästchen die kleinstmögliche regelkonforme Zahl einsetzen
-Wenn es keine regelkonforme Zahl für ein Kästchen mehr gibt, dann im vorherigen die nächste Zahl einsetzen usw.
-Sobald es wieder eine regelkonforme Zahl in einem Kästchen gibt, wieder "vorwärts" Zahlen einsetzen
Die gesamte Funktion hier:
Spoiler anzeigen
istVorgegeben ist ein Boolean-Feld, das je nach Vorgabe true oder false enthält und
istRegelkonform() ist eine eigene Funktion, die true oder false zurückgibt
So weit, so gut.
Bei mir kommt er aber immer nur bis zu einer bestimmten Zahl, geht ein bisschen hin und her und löst dann die Funktion nichtLösbarAusgeben aus, hat also an irgendeiner Stelle anscheinend Probleme, wieder vorwärts zu kommen.
Jetz die Frage an euch :
Wo liegt mein Denkfehler?
ich arbeite gerade an einem Programm, das mir Sudokus lösen soll.
Dass es diese schon zu hauf im Internet gibt, ist mir klar(nur um solche Antworten zu vermeiden )
Ich hab auch schon viele Algorithmen gefunden, die funktionieren.
Trotzdem hab ich mir selber noch einen überlegt, der(meiner Meinung nach) theoretisch auch funktionieren sollte, das faktisch aber nicht tut
Mein Algorithmus ist folgender:
-Alle Spalten und Zahlen nacheinander durchlaufen
-Bei jedem Kästchen die kleinstmögliche regelkonforme Zahl einsetzen
-Wenn es keine regelkonforme Zahl für ein Kästchen mehr gibt, dann im vorherigen die nächste Zahl einsetzen usw.
-Sobald es wieder eine regelkonforme Zahl in einem Kästchen gibt, wieder "vorwärts" Zahlen einsetzen
Die gesamte Funktion hier:
VB.NET-Quellcode
- Private Sub lösen()
- Dim x As Integer = 1
- Dim y As Integer = 1
- Dim aktuelleRichtung As String = "vorwärts"
- Dim nächsteRichtung As String = "vorwärts"
- Do
- aktuelleRichtung = nächsteRichtung
- If Not istVorgegeben(x, y) Then 'Auf vorgegebene Zahl überprüfen
- For zahl = (sudokuFeld(x, y) + 1) To 10 Step 1 'For einleiten: Nach geeigneter Zahl suchen
- If istRegelkonform(zahl, x, y) Then
- sudokuFeld(x, y) = zahl 'Ermittlete Zahl dem Sudokufeld zuteilen, wenn regelkonform und
- nächsteRichtung = "vorwärts" 'Richtung auf vorwärts setzen und
- Exit For 'For anschließend verlassen
- Else
- If zahl = 10 Then 'Wenn keine geeignete Zahl gefunden wurde,
- nächsteRichtung = "rückwärts" 'dann Richtung auf rückwärts und
- sudokuFeld(x, y) = 0 'SudokuFeld an Stelle x,y =0 setzen
- Exit For 'For verlassen
- End If
- End If
- Next
- End If
- If nächsteRichtung = "vorwärts" Then 'Bei vorwärts
- y += 1 'y um 1 erhöhen
- If y > 9 Then 'Wenn y 9 überschreitet, in neue Zeile wechseln
- y = 1
- x += 1
- End If
- If x = 9 Then
- zahlenEintragen()
- MsgBox("Erfolg")
- Exit Sub
- End If
- End If
- If nächsteRichtung = "rückwärts" Then 'Bei rückwärts
- y -= 1 'Von y 1 abziehen
- If y < 1 Then 'Wenn y 1 unterschreitet, in vorhergehende Zeile wechseln
- y = 9
- x -= 1
- If x < 1 Then
- nichtLösbarAusgeben() 'Zusatz: wenn Zeilennummer 1 unterschreitet, ist das Sudoku nicht lösbar;
- Exit Sub 'zusätzlich Vorgang beenden
- End If
- End If
- End If
- Loop
- End Sub
istVorgegeben ist ein Boolean-Feld, das je nach Vorgabe true oder false enthält und
istRegelkonform() ist eine eigene Funktion, die true oder false zurückgibt
So weit, so gut.
Bei mir kommt er aber immer nur bis zu einer bestimmten Zahl, geht ein bisschen hin und her und löst dann die Funktion nichtLösbarAusgeben aus, hat also an irgendeiner Stelle anscheinend Probleme, wieder vorwärts zu kommen.
Jetz die Frage an euch :
Wo liegt mein Denkfehler?
Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „RUDI!“ ()