Sudoku-Algorithmus

  • VB.NET

Es gibt 7 Antworten in diesem Thema. Der letzte Beitrag () ist von Kangaroo.

    Sudoku-Algorithmus

    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 :cursing:

    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

    VB.NET-Quellcode

    1. Private Sub lösen()
    3. Dim x As Integer = 1
    4. Dim y As Integer = 1
    5. Dim aktuelleRichtung As String = "vorwärts"
    6. Dim nächsteRichtung As String = "vorwärts"
    8. Do
    9. aktuelleRichtung = nächsteRichtung
    10. If Not istVorgegeben(x, y) Then 'Auf vorgegebene Zahl überprüfen
    12. For zahl = (sudokuFeld(x, y) + 1) To 10 Step 1 'For einleiten: Nach geeigneter Zahl suchen
    13. If istRegelkonform(zahl, x, y) Then
    14. sudokuFeld(x, y) = zahl 'Ermittlete Zahl dem Sudokufeld zuteilen, wenn regelkonform und
    15. nächsteRichtung = "vorwärts" 'Richtung auf vorwärts setzen und
    16. Exit For 'For anschließend verlassen
    17. Else
    18. If zahl = 10 Then 'Wenn keine geeignete Zahl gefunden wurde,
    19. nächsteRichtung = "rückwärts" 'dann Richtung auf rückwärts und
    20. sudokuFeld(x, y) = 0 'SudokuFeld an Stelle x,y =0 setzen
    21. Exit For 'For verlassen
    22. End If
    23. End If
    24. Next
    25. End If
    27. If nächsteRichtung = "vorwärts" Then 'Bei vorwärts
    28. y += 1 'y um 1 erhöhen
    29. If y > 9 Then 'Wenn y 9 überschreitet, in neue Zeile wechseln
    30. y = 1
    31. x += 1
    32. End If
    33. If x = 9 Then
    34. zahlenEintragen()
    35. MsgBox("Erfolg")
    36. Exit Sub
    37. End If
    38. End If
    40. If nächsteRichtung = "rückwärts" Then 'Bei rückwärts
    41. y -= 1 'Von y 1 abziehen
    42. If y < 1 Then 'Wenn y 1 unterschreitet, in vorhergehende Zeile wechseln
    43. y = 9
    44. x -= 1
    45. If x < 1 Then
    46. nichtLösbarAusgeben() 'Zusatz: wenn Zeilennummer 1 unterschreitet, ist das Sudoku nicht lösbar;
    47. Exit Sub 'zusätzlich Vorgang beenden
    48. End If
    50. End If
    52. End If
    54. Loop
    56. 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!“ ()

    Hallo und willkommen im Forum,

    ich denke, dass es an der Stelle hängt, nachdem es einmal Rückwärts geht. Denn dann bist du beim vorherigen Feld und dieses Mal ist es VORGEGEBEN, egal ob es vom Rätsel/der Aufgabe vorgegeben wurde oder vom Programm eingetragen wurde. !?
    Du musst die Felder, in die von dir eine Zahl eingegeben wurde anders verarbeiten lassen, als die, die vom Programm ausgefüllt wurden....
    Kann es das sein?
    Des weiteren finde ich es irritierend, dass die Zeilen X sind und die Spalten Y.... ist das normalerweise nicht anders herum?! ;)

    Gruß!
    Maddin

    btw: hab selber auch schon ein Sudokulösprogramm mit vb.bet geschrieben... aber noch mit Automatischer Einlese- und Ausfüllfunktion ;)

    Erstmal danke für die schnelle Antwort :)

    Eig setz er ja, wenn er einmal zurückgegangen ist und dann im vorherigen Feld eine zweite regelkonforme Zahl findet, die Richtung wieder auf vorwärts - oder is des mein Denkfehler?

    Du musst die Felder, in die von dir eine Zahl eingegeben wurde anders verarbeiten lassen, als die, die vom Programm ausgefüllt wurden....
    Dafür hab ich ja des Booleanfeld istVorgegeben; wenn eine Zahl vorgegeben ist, wird die ganze For-Schleife ja garnicht ausgeführt und er geht gleich ins nächste Kästchen(Am Anfang: If Not istVorgegeben(x,y) ...)

    Des weiteren finde ich es irritierend, dass die Zeilen X sind und die Spalten Y.... ist das normalerweise nicht anders herum?! ;)
    Naja ich hab mich da am Koordinatensystem orientiert... da ist x ja waagerecht(wie die Reihen) und y senkrecht(wie die Spalten) ;)


    Mfg RUDI!

    Dafür hab ich ja des Booleanfeld istVorgegeben; wenn eine Zahl vorgegeben ist, wird die ganze For-Schleife ja garnicht ausgeführt und er geht gleich ins nächste Kästchen(Am Anfang: If Not istVorgegeben(x,y) ...)

    was wird bei dem "If Not istVorgegeben(x,y)" eigtl. gemacht? Da wird doch eine andere Funktion aufgerufen, oder nicht?! Wenn ja, dann möcht ich diesen Code sehen...
    Weil wenn da was nicht stimmt, wird jedes Feld, sobald vom Programm etwas eingetragen wird, als "Vorgegeben" behandelt, sprich: Die folgende For-Schleife wird übersprungen.

    Sry, wenn ich jetzt irgendwas falsch verstehe, ich hab gerade eine lange vb.net Pause hinter mir ;)

    was wird bei dem "If Not istVorgegeben(x,y)" eigtl. gemacht? Da wird doch eine andere Funktion aufgerufen, oder nicht?!
    ne des is keine Funktion des is ein feld mit booleanwerten
    Da wird an der Stelle x,y beim Auffüllen true eingetragen wenn an dieser Stelle eine Zahl steht

    Eigentlich ein guter Ansatz: diese Vorgehensweise nennt man in der Spieltheorie Brute-Force-Methode und man kann damit dem Computer beibringen auch bei schwierigen Spielen noch gute Züge zu machen. Bei Tic-Tac-Toe oder Mühle kann er sogar alle Züge bis zum Rnde durchrechnen und wird unbesiegbar.

    Bei Deinem Verfahren sind noch ein paar Bugs drin:
    - die "nicht vorgegeben" If-Abfrage ist unnötig
    - bei "vorwärts" die nächste regelkonforme Zahl eintragen, falls geht nächstes Feld besetzen, sonst Unlösbar
    - bei Rückwärst letzte Eintragung rückgängig machen

    regelkonform: Feld nicht besetzt, Zahl nicht im 3x3 Feld, nicht in der Zeile und nicht in der Spalte

    Wird normalerweise mit Rekursion gelöst, aber lässt sich auch mit Schleifen lösen.

    Kangaroo schrieb:

    Eigentlich ein guter Ansatz
    Danke :D

    Kangaroo schrieb:

    - die "nicht vorgegeben" If-Abfrage ist unnötig
    Wieso? wenn ich des rauslasse, dann wir die for-schleife doch auch für die vorgegebenen Zahlen ausgeführt...


    - bei "vorwärts" die nächste regelkonforme Zahl eintragen, falls geht nächstes Feld besetzen, sonst Unlösbar
    - bei Rückwärst letzte Eintragung rückgängig machen
    Ähm... danke für die Vorschläge... leider versteh ich des net ganz ?(
    des mit vorwärts wird doch jetz auch schon ausgeführt
    und was bringt des dass ich die letzte Eintragung rückgangig mache?

    Und nomml danke für deine Antwort :thumbup:

    Machen wir ein Beispiel für das Feld (x,y)=(1,1):

    - ich versuche das Feld mit einer "1" zu besetzten
    - ist das nun regelkonform (nicht besetzt, nicht im gleichen Block, Zeile, Spalte) ?
    - falls ja versuche ich das nächste Feld (1,2) mit der Zahl 1
    - falls nein, versuche ich es mit der Zahl "2" im Feld (1,1)

    Jetzt kann es sich aber rausstellen, dass die "1" zwar regelkonform war, ich aber später auf Widersprüche stosse: also war die "1" wohl doch keine gute Idee, ich muss sie dort wieder rausnehmen und es mit der 2 versuchen.

    Du wolltest wissen warum es (noch) nicht funktioniert ...

Facebook
Telefonspende