Sudoku Solver

    • Release
    • Open Source

    Es gibt 39 Antworten in diesem Thema. Der letzte Beitrag () ist von Plexian.

      @ErfinderDesRades

      1. Was meinst du er stürtzt ab bzw tut ienfach nix, hast du iwas was ich reproduzieren kann ?
      2. Ist "du lieber Himmel" positiv oder negativ gemeint ? ^^
      3. Stimmt, der Beep war geplant aber hatte ich vergessen, eig sollte auch eine visuelle Warnung kommen.

      Danke soweit ! :thumbsup:
      »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

      Das ist merkwürdig, bei mir öffnet sich die Form mit einer MessageBox:
      Bilder

      • shot.JPG

        43,47 kB, 431×538, 208 mal angesehen
      »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

      na sowas.
      Ich hab die Datei so erstellt und geladen, und er macht da die 3 4en hin - kann das als Sudoku-Aufgabe aber nicht lösen.

      vlt. kommst du mit dieser Darstellung besser klar (ein 9*9 - Feld):

      Brainfuck-Quellcode

      1. .4.......
      2. ....4....
      3. .......4.
      4. .........
      5. .........
      6. .........
      7. .........
      8. .........
      9. .........
      das müssteste auch abtippen könne

      So, die 1.0 ist draußen :thumbsup:

      Neuerungen:
      - Lösen mit Hilfe des BackTracking Algorithmus'
      - Benachrichtigungssystem
      - Stabilitätsverbesserungen

      BITTE: Testet, ob die Benachrichtungen richtig funktionieren, ich zweifele sehr, konnte aber keine Fehler feststellen.

      Download-, sowie Quellcodelink sind im Startpost, viel Spaß!
      »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

      Ich habe seit dem letzten Update weder Defizite festgestellt, noch Vorschläge bekommen. Daher wird auch in nächster Zukunft nichts weiter kommen, es sei denn es besteht der Wunsch.

      Ich würde mich außerdem freuen, wenn du, @ErfinderDesRades , deine Probleme noch mal testen würdest :)
      »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

      Hi,

      Super Programm mal wieder von dir :)

      Was mir noch aufgefallen ist:
      - Korrigiere die gelbe Infomeldung: "You have to enter more than 17 ...." (then -> than)
      - Wenn kein Feld ausgewählt (also rot) ist und man Entf drückt, gibt's eine Exception
      - Ich persönlich würde das Exit aus dem Menü nehmen und das in's File-Menü packen (also nach Save ein Strich und dann Exit).

      Was vielleicht noch ne Idee wäre, dass man in so einem exportierten File mehrere Sudokus speichert mit Zeilenumbrücken o.ä. getrennt. Und man dann in einer Listbox auswählen kann welches reingeladen wird. Das spart denk ich mal ne Menge Dateien. Zum Beispiel dass man ne Textbox hat und und dann den namen dafür eingibt.

      Vielleicht so in der Art:

      Quellcode

      1. Sudoku 1:.141.7.66.45.9.4..6.2...694..69..4832......2...1..68...7.5..1.5683.1967.889...2..
      2. Mein erstes Sudoku:...1..3.19354.4.5..295184198....318941...48..21646.4272..1..7.7155...133.16...95.
      3. Test:..3.971199..6691..46..91..1....14.439..8...8...12..2...3.2927..125.18...43995.1.1
      4. Blabla:689.82.11..9.717995..68.575...3.92.8.4.355362.32..51.3181..7.4......8393.2.83..5.
      5. Hurr:..3752..2....4..76..586..58..37.7..3.13259693....58535.9.9.33.914..444..3....54..
      6. Durr:2.....5...53...1.9.8.22.8534.9.9.......4...5.3.23..69..8542.35.5918.2.99..5389.1.
      7. temp:3..3....62515....5544499.37.5.4.4.9....988.3.87532.....39.9514..4..7..7...94.6.7.
      8. Wasweissich:6.2....2.7.79.29...6.5.34671.5798...3.86.84....152....39.1......42..8....6....76.
      9. Noch eins:.6.2..585.....4.4.89...9.2.5.7513....6..8....5..5.97..6257..4.3..5..1...1177..8.1
      10. Und nochmal:776.4.6247.5116.8.5.4.7..4..3.6..3199.24.5.4..8..31.7..7.4.3.8..13.188..426964...
      11. Und wieder eins:3..93.9..3..463.......67.63687.2..16.1.2.136...1..342.14....934.8.9.4.662.3744..9
      12. Und:951...3.35...1.3...1...357.......72...658.9.3.9...23.2...123886.6..71.2..15835..9
      13. So:24..822....99.6.6379...5...5..56..8941.54654.298.77.......8253.66.6.5...98.....37
      14. Weiter:7.9....1.8.4....68...29.3.14..19.19.4.45.8.187955.57457.6.881.739763.1...59.38...
      15. Und:6.41.9..7.8..1.8.8.6.3.9213.291...7...39.1.1.3..22.6..656....44.72495.9.7.477...4
      16. So:..7293..7442...87.4..69217.297....7.6..37....3..95..2.7...3..7.....6.3..53.9.....
      17. Fort:.161.723.35.88.....6211.71..2327.....8.3159.4..6.629....121...8...41.4.4.....277.
      18. abc:.74.9791..4.985.2.....41.59527.946.34...16..4.4...15....7.9....587.2..36...8.8.28
      19. xyz:4..62.36..7.12..873...31224.5...1...667.84...54.3.1.3.2.4.4...68199.66.416.5257.9


      Und man dann in ner Listbox oder Combobox auswählt welches man reinladen möchte.

      Ne weitere Idee wär, dass man das aktuelle Sudoku beim FormClose in den My.Settings speichert oder so, damit man das beim nächsten Start wieder drin hat.


      Ansonsten find' ich den SudokuSolver super :)

      Link :thumbup:
      Hello World

      naja, Mini-Eingaben lehnt er jetzt ja ab, das ist halt gelöst. Meine Probs waren ja mit Mini-Eingaben - weil ich bin ja zu faul, mir 17 widerspruchsfreie Zellen auszudenken und reinzuschreiben.
      Aber zb das heutige Sudoku der Zeit hab ich abgeschrieben, und kannernich 8|
      Datei ist im Anhang.
      Edit: Ah - mit Backtracking kanners doch :thumbsup: - (das HumanSolving - wozu ist das also gut?)

      Durch deinen Lösungs-Code blicke ich absolut nicht durch - ist zuviel, und ich weiß den Plan nicht, der dahinter steht
      Also bei meinen Klassen mach ich immer ausführliche File-Header, die die Konzepte gründlich erläutern, mit erkennbarem Bezug auf die Namen der KlassenMember.
      Dadurch ist klargestellt, was die Member dieser Klasse zu tun haben, und man kann den Code verstehen.
      Und ich hab auch festgestellt: grade diese Art der Doku hilft mir selbst, das Teil nochmal zu durchdenken, und oft ergeben sich daraus gleich wieder wesentliche architektonische Verbesserungen.
      Ist interessant, denn jeder weiteren Kommentation gegenüber bin ich ja sehr reserviert, denn guter Code erklärt sich selbst, sodass 90% aller Kommentare sowohl Anzeichen schlechten Codes sind, als auch ihn aktiv verschlechtern.
      EDRs Sudoku

      VB.NET-Quellcode

      1. #Region "FileHeader"
      2. #If False Then
      3. Über Zeilen, Spalten und 3*3er-Boxen ist jedes Sudoku-Feld mit insges 21 anneren verknüpft. In dieser Gesamtgruppe darf der Feld-Wert nicht ein zweites Mal auftreten - so ist die Sudoku-Regel, von der 2D-Darstellung abstrahiert.
      4. Die Such-Logik ist nu: Jedes Feld hat 9 Zähler - "Handicaps", für jeden möglichen Wert eines. Wird nun ein Feld-Wert gesetzt, so werden in allen verlinkten Feldern das entsprechenden Handicap hochgezählt.
      5. Zusätzlich wird dabei noch ein Zähler für die "Freiheiten" mitgeführt, das ist die Anzahl möglicher Werte, die das Feld noch annehmen kann. Die Freiheiten sind also schlicht die Anzahl der auf 0 stehenden Handicaps.
      6. Die Freiheiten sind unabhängig davon, ob ein Feld belegt ist oder nicht: ZB bei einem beilegten Feld bedeuten 3 Freiheiten, dasses noch 3 annere Belegungs-Möglichkeiten gibt.
      7. Also ein unbelegtes Feld ist gültig mit 1 - 9 Freiheiten, ein belegtes mit 0 - 8 Freiheiten.
      9. Der Algo wendet einen verschärften Sudoku-Algo an:
      10. 1) Erst setzt er ein Feld, und aktualisiert Handicap und Freiheiten aller verlinkter Felder.
      11. 2) Dann testet das Feld seine Validität wie folgt:
      12. Ungültig ist, wenn das Handicap seines Values nicht genau 1 ist.
      13. Ungültig ist aber auch, wenn es unter den verlinkten ein unbelegtes Feld gibt **ohne** Freiheiten.
      14. 2a) Nur bei Gültigkeit holt sich der Algo das nächste Feld und geht damit in die Rekursion.
      15. (Das Holen ist besonders listiger Bestandteil des Algos: Er holt nämlich das Feld mit den wenigsten Freiheiten!)
      16. 3) egal ob gültig (und in Rekursion) gewesen oder nicht - vor dem Verlassen der Methode wird das Feld wieder hergestellt, wies war, inklusive Rück-aktualisierung der LinkedFields.
      18. Die Bevorzugung niedriger Freiheiten beim Holen des nächsten Feldes lässt den Algo sehr sehr schnell der ersten Lösung zustreben.
      19. Es ist aber nur eine **Sortierung** der Optionen - kein Ausschluss.
      20. Würden also **alle** Lösungen gesucht, so wäre es unnötiger Aufwand, ziemlich teuer sogar.
      21. Auch bei unlösbaren Sudokus ist das ineffizient, denn Unlösbarkeit ist erst gezeigt, wenn alle Möglichkeiten durchprobiert sind - egal in welcher Reihenfolge.
      22. #End If
      23. #End Region 'FileHeader
      25. <DebuggerDisplay("{Value} {Location} ({Freedom})")> _
      26. Public Class Field
      27. Public Value As Integer = 0
      28. Public Freedom As Integer = 9
      29. Private Handicaps(9) As Integer
      30. Public LinkedFields(20) As Field
      31. Public Location As Point 'only for debugging
      33. Public Sub Reset()
      34. Value = 0 : Freedom = 9 : ReDim Handicaps(9)
      35. End Sub
      36. Private Sub SetHandicap(ByVal value As Integer)
      37. Handicaps(value) += 1
      38. If Handicaps(value) = 1 Then Freedom -= 1
      39. End Sub
      40. Private Sub RemoveHandicap(ByVal value As Integer)
      41. Handicaps(value) -= 1
      42. If Handicaps(value) = 0 Then Freedom += 1
      43. End Sub
      44. Public Sub SetValue(ByVal value As Integer)
      45. For Each fld In LinkedFields : fld.SetHandicap(value) : Next
      46. Me.Value = value
      47. End Sub
      48. Public Sub RemoveValue()
      49. For Each fld In LinkedFields : fld.RemoveHandicap(Value) : Next
      50. Value = 0
      51. End Sub
      52. Public Function IsValid() As Boolean
      53. If Handicaps(Value) <> 1 Then Return False
      54. Return LinkedFields.All(Function(fld) fld.Value > 0 OrElse fld.Freedom > 0)
      55. End Function
      57. End Class


      Das aufwändigste am ganzen Sudoku ist die richtige Initialierung der 81 Felder - danach die rekursive Methode solve issn Klacks

      VB.NET-Quellcode

      1. Public Class Sudoku
      3. 'die Verarbeitung der Fields ist mal im 2-dimensionalen Array praktischer, mal in 1-D.
      4. Public Fields(8, 8) As Field
      5. Public FieldsLinear(80) As Field
      7. Public Sub New()
      8. For y = 0 To 8
      9. For x = 0 To 8
      10. Dim fld = New Field With {.Location = New Point(x, y)}
      11. Fields(y, x) = fld
      12. FieldsLinear(y * 9 + x) = fld
      13. Next
      14. Next
      15. For y = 0 To 8
      16. For x = 0 To 8
      17. Dim linkeds = New HashSet(Of Field)
      18. For i = 0 To 8 : linkeds.Add(Fields(y, i)) : Next
      19. For i = 0 To 8 : linkeds.Add(Fields(i, x)) : Next
      20. Dim xBox = (x \ 3) * 3, yBox = (y \ 3) * 3 'top-left Box-Location
      21. For yy = yBox To yBox + 2
      22. For xx = xBox To xBox + 2
      23. linkeds.Add(Fields(yy, xx))
      24. Next
      25. Next
      26. Fields(y, x).LinkedFields = linkeds.ToArray
      27. Next
      28. Next
      29. End Sub
      31. Public Function Solve(ByVal bytes As Byte()) As Boolean
      32. FieldsLinear.ForEach(Sub(fld) fld.Reset())
      33. For i = 0 To bytes.Length - 1
      34. Dim val = bytes(i)
      35. If val = 0 Then Continue For
      36. With FieldsLinear(i)
      37. .SetValue(val)
      38. If Not .IsValid Then Return False
      39. End With
      40. Next
      41. Solve = Solve(GetNextField)
      42. For i = 0 To bytes.Length - 1
      43. bytes(i) = CByte(FieldsLinear(i).Value)
      44. Next
      45. End Function
      47. Private Function Solve(ByVal fld As Field) As Boolean
      48. If fld.Null Then Return True 'gelöst! GetNextField hat kein weiteres Feld gefunden
      49. For val = 1 To 9
      50. fld.SetValue(val)
      51. If fld.IsValid Then
      52. If Solve(GetNextField) Then Return True
      53. End If
      54. fld.RemoveValue()
      55. Next
      56. Return False
      57. End Function
      59. Private Function GetNextField() As Field
      60. 'ein unbelegtes Feld mit minimaler Freiheit, oder Nothing, wenn alle Felder belegt
      61. Return (Aggregate f In From fld In FieldsLinear Where fld.Value = 0 Into Extremum(f.Freedom)).Min
      62. End Function
      64. End Class

      Edit:

      Link schrieb:

      noch ne Idee wäre, dass man in so einem exportierten File mehrere Sudokus speichert mit Zeilenumbrücken o.ä. getrennt. Und man dann in einer Listbox auswählen kann welches reingeladen wird. Das spart denk ich mal ne Menge Dateien.
      Zustimm.
      Wie wärs mit einem typisierten Dataset? ;)
      Dateien

      • Sudok3.txt

        (81 Byte, 116 mal heruntergeladen, zuletzt: )

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „ErfinderDesRades“ ()

      Erstmal, danke euch :)

      @Link :
      Die ersten drei Punkte sind erledigt, die Idee mit mehreren Sudokus pro Datei finde ich gut, mal sehen wie ich das umsetze. Das mit dem Abspeichern beim Speichern wird auch gleich erledigt ^^
      Danke soweit!

      @ErfinderDesRades :
      Du musst aufpassen. Ist vllt unglücklich gelöst, aber im MenuStrip unter Options kannst du die Lösungsmethode wählen. "HumanSolving" schafft halt nicht alle, dass sind nun mal die Methoden die ein durchschnittlicher Mensch ebenfalls im Kopf hat (ca. 30% aller möglichen Sudokus lösbar). Stellst du das um auf BackTracking dann gehts prima.
      Dass du meinen Code nicht verstehst, finde ich schade, hätte ich gedacht. Also ich finde mich prima zurecht, auch jeztt nach etwa 2 Monaten nichtstun.
      Aber letztendlich ist deine Methode nicht sehr viel kürzer als meine. Nur arbeite ich noch mit einem Klon pro Stack (Rekursion), muss ich noch ausbessern.
      »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ThePlexian“ ()

      jetzt hab ich dein studiert und peils im groben auch - zumindest den Backtracking-Teil.
      Jo, die Methode ist nicht länger als meine, unübersichtlich sind halt die 400 Zeilen drumrum, die nix erkennbares damit zu tun haben.

      Ich hab übrigens noch ein besonders schwieriges Sudoku gefunden, wo er sehr lange dran arbeitet (s.Anhang)
      Also ich habs nicht bis Ende laufen lassen.
      Dateien

      • Sudok2.txt

        (81 Byte, 125 mal heruntergeladen, zuletzt: )

      @ErfinderDesRades :
      Da gebe ich dir nicht Unrecht, liegt halt daran, dass in dieser (partial) class zwei Lösungsmethoden sind, einmal HumanLike und BackTracking. Nur sortiert hab ich es nicht schön, ändere ich. Mein BackTracking läuft nur so, dass am Anfang der Methode einmal HumanLike gelöst wird, zur Permorfanceverbesserung. D.h im groben, es wird eine Zahl geraten, dann wird erstmal geprüft wie das Sudoku logisch zu lösen wäre (Eine Zelle nur eine Zahl möglich etc.) und dann weiter raten.

      Zu deinem Sudoku: Dauert bei mir mit BackTracking knappe 300ms ?
      Bilder

      • s.bmp

        17,6 kB, 410×410, 169 mal angesehen
      »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

      Soooooo. Habe ewig nicht mehr dieses Projekt angesehen, aber dann doch was festgestellt:

      @Link 's Wunsch bzgl. des Speicherns hatte ich schon lange implementiert, aber die Version nie hochgeladen.
      Deswegen hier das Update auf Version 1.1 und wahrscheinlich auch das letzte Update, da ich mittlerweile bei anderen zu schaffen bin. Voraussetzung für das Abschließen dieses Projekts ist jedoch, dass es keine weiteren Dinge zu beheben gibt.
      Sudokus lassen sich nun in TXT und XML speichern / laden. Sowohl eins als auch mehrere pro Datei. Wenn mehrere Sudokus in einer Datei vorhanden sind, dann öffnet sich ein weiterer Dialog nach dem Laden, in dem dann das gewünschte Sudoku auszuwählen ist.
      Der Unterschied zwischen TXT und XML ist einfach: In einer TXT wird ein Sudoku (81 Zahlen) mit 81Bytes gespeichert. Also nur die Zahl. In einer XML werden die Zahlen, ein Name, das Datum und die "Presets" (vorgegebenen Zahlen) mit gespeichert.

      Bevor Fragen zum Code kommen: Ich bin mir relativ sicher, dass ich das Abspeichern als XML nicht optimal gelöst habe. Ich erstelle alles manuell über die XmlDocument-Klasse, das heißt nicht mit richtiger Serialisierung. Sorry dafür, aber irgendeinen Grund werde ich damals gehabt haben :D

      Viel Spaß weiterhin an meine zig tausend Nutzer ;)
      »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

      Habe nochmal drüber geschaut, und ne Kleinigkeit beim Control verbessert, da wurde manchmal nicht richtig invalidatet.
      Update im Startpost.
      »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

      Hey
      Hab dein Programm mal getestet. Funktioniert echt toll, nur schade ist das man immer einzeln in jedes Feld klicken muss um die Zahl einzugeben. Du könntest ja das ja auch machen das man mit den Pfeiltasten steuern kann...
      Ansonsten top und funktioniert!
      Gruss Mirco

      Danke fürs Feedback @MircoTuor !

      Man kann aber mit den Pfeiltasten steuern, die Tabulator-Taste funktioniert auch. Sicher, dass das bei dir nicht geht ?
      »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

      Wäre natürlich machbar, die Idee war auch schon mal da, nur steht der Aufwand mit dem Ergebnis mMn in keinem Verhältnis. Alle Texte in Resourcen-Files auszulagern und Localization einbauen, nur um letztendlich 50 Wörter auf Deutsch dazuhaben - ich weiß nicht.
      »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais