Aufbau einer EFFIZIENTEN Sudoku Solver

Ja, ich weiß, das ist nichts neues und es gibt viele Fragen, die schon draußen (es hat sogar seinen eigenen tag), aber ich möchte ein Sudoku-Solver in Java ausschließlich für den Zweck der Ausbildung selbst code zu schreiben, der ist effizienter.

Wahrscheinlich der einfachste Weg, dies zu tun in einem Programm haben eine Tonne von for-Schleifen analysieren durch jede Spalte und Zeile, sammeln die möglichen Werte der einzelnen Zelle, dann Unkraut aus den Zellen mit nur einer Möglichkeit (ob Sie enthalten nur 1 Zahl, oder Sie sind die einzige Zelle in die Zeile/Spalte mit dieser Nummer), bis Sie haben ein puzzle gelöst. Natürlich, eine schiere gedacht, die Aktion sollte eine rote fahne, in jeder Programmierer in den Sinn.

Was ich Suche ist die Methode zum lösen dieser Sauger in die effizienteste Art und Weise möglich (bitte versuchen Sie nicht, zu viel code - ich will herausfinden, dass ein Teil aus, mich).

Möchte ich vermeiden mathematische algorithmen, die-wenn überhaupt möglich - diese wäre zu einfach und zu 100% nicht meine Arbeit.

Wenn jemand könnte eine Schritt-für-Schritt, effiziente denk-Prozess für die Lösung eines Sudoku-Rätsel (ob von einem Menschen oder computer), wäre ich sehr glücklich :). Ich bin auf der Suche nach etwas, das vage ist (es ist also eine Herausforderung), aber informativ genug (also ich bin nicht Total verloren), mich zu beginnen.

Vielen Dank,

Justian Meyer

EDIT:

Blick auf meinen code, ich habe mir überlegt: was wäre, einige der Möglichkeiten für die Speicherung dieser Lösung Mitgliedstaaten (D. H. die Sudoku-raster). 2D-Arrays und 3D-Arrays in den Sinn kommen. Die wohl am besten? 2D-möglicherweise leichter zu verwalten, von der Oberfläche, aber 3D-Arrays wäre die "box"/"Käfig" - Nummer als auch.

EDIT:

Nevermind. Ich werd mal mit einem 3D-array.

  • Auch, wenn Sie gehen mit dem "aussortieren, bis nur noch eine Möglichkeit übrig:" du wirst noch nicht in der Lage zu lösen einige sudokus. Es gibt eine gute Menge von "härter" sudokus, wo Sie eigentlich zu erfüllen haben irgendeine Art von suchen, bevor Sie sicher sein können, die Zahl zu setzen, wo (DFS/BFS). Andernfalls wird die Schleife durch jede Spalte und so weiter ist nicht wirklich so schrecklich oder ist ineffizient, solange Sie die Datenstrukturen entsprechend, aber wie gesagt, es wird nicht lösen -alle - sudokus.
  • Ja, ich habe getan ein wenig Forschung und fand, dass. Aber es sieht aus wie so viele andere Menschen gefunden haben, effizienter work-around, dass, obwohl ich hasse es zuzugeben, weit über meine Ebene des Verständnisses.
  • Ich habe einige schnelle googeln und fand einige Empfehlungen für die Verwendung von den "Dancing Links-Algorithmus" (en.wikipedia.org/wiki/Dancing_Links). Ich habe nicht gesehen, dieser Algorithmus vor (und ich nicht wirklich Zeit haben, zu Lesen in Sie, genau in diesem moment), aber es sieht vielversprechend aus. Vielleicht etwas, lohnt sich einen Blick auf? 🙂
  • Danke für den link, aber das ist eine jener Methoden, die "... über meine Ebene des Verständnisses" ;). Eine person, die auch erklärt es im Sinne von Java, aber ich finde es immer noch verwirrend (ocf.berkeley.edu/~jchu/publicportal/sudoku/...). Leute konsultiert haben, die, SO Gemeinschaft für die Hilfe zu erklären, aber von dem, was ich gesehen habe, hat niemand eine solide Antwort.
  • Dies ist eine ziemlich interessante Visualisierung des backtracking-Methode: youtube.com/watch?v=JtTThE93WNI&feature=related
  • Meyer: vor dem Lesen auf sehr komplizierte Sachen, die Sie wahrscheinlich tun wollen, Lesen Sie auf backtracking, das ist immer beweisen, dass Sie etwas wertvolles für Sie als Programmierer (es sei denn, sagen, Tanz-links, die, ehrlich gesagt, sehr viele tolle Programmierer haben eigentlich nie verwendet). Lösung des Sudoku programmgesteuert ist die typisches Beispiel für backtracking. Ich hab eine super schnelle Löser, die die rekursive Methode ist, die über 12 Zeilen code lang. Das ist die Schönheit der recursivity und backtracking: en.wikipedia.org/wiki/Backtracking
  • Meyer: Hier sind ein paar gute Ansatzpunkte: en.wikipedia.org/wiki/Algorithmics_of_sudoku Beachten Sie, dass die naive angeblich schwer Beispiel Sie geben, die nehmen "45 Minuten zu lösen, das auf einer 3 Ghz-Maschine" ist gelöst in 80 Sekunden durch mein völlig nicht optimierten backtracking+Randomisierung solver (Stapellauf vier Löser, die in parallels, drehen Sie die platine um 90 Grad jedes mal + mit Randomisierung). I lol ' ed, wenn ich warf, die "hard" - Beispiel auf meiner kleinen solver 🙂
  • Könnte ich vielleicht sehen, Ihren source-code? Wie gesagt, dies ist nur zum Spaß, aber ich würde gerne sehen, was Sie gemacht haben mit dem Konzept. Ich habe versucht, es zu tun, der lange Weg, wie wasatz vorgeschlagen, aber mein code ist schon viel zu lange, wie es ist, und es deckt nur zwei SEHR einfache sudoku soving Strategien.
  • Sie haben gegensätzliche Anforderungen zu erfüllen: (1) einfach und leicht zu verstehen, und (2) schneller als die offensichtlichen brute-force-Methoden. Ich denke, Sie müssen wählen Sie eine oder das andere.
  • Verständlich, denn das ist oft der Fall mit effizienten code. Ich hatte wirklich gehofft, für eine Vielzahl von Antworten, so konnte ich Wiege meine Optionen. @alle: ich habe eine Anzahl von oben/unten Stimmen für diese Frage. Ich würde es vorziehen, dass es eine Erklärung für die nach unten Stimmen, wenn du gehst, um so; ansonsten bitte nicht zu Stimme überhaupt. Es gibt keine Weise, die ich verstehen kann, was eine einzige Zahl soll das bedeuten.
  • Ich empfehle Ihnen, verbringen einige mehr Zeit mit dem Versuch zu verstehen, den Dancing-Links-Implementierung.
  • Glaubst du, ich würde eher davon profitieren zu lernen, dass über backtracking? (in Bezug auf die Langzeit-Erfahrung)
  • Nein, nicht langfristig, es ist nur gut geeignet, um diese Art von problem.
  • Seit dem Dancing-Links-Implementierung ist nicht wirklich meine Lösung und lernen die richtige backtracking kann mir helfen in der Zukunft, ist es vielleicht besser, dass ich versuche, Brute-Force-Methode?
  • Sie müssen backtracking oder so, ob Sie Tanzen Links oder brute-force.

InformationsquelleAutor Justian Meyer | 2010-07-27
  1. 1

    Es hängt davon ab, wie Sie definieren, effizient.

    Können Sie einen brute-force-Methode, das sucht sich durch jede Spalte und Zeile, erfasst die möglichen Werte der einzelnen Zelle, dann Unkraut aus den Zellen nur eine Möglichkeit.

    Wenn Sie Zellen, die übrigen mit mehr als eine Möglichkeit, speichern Sie das puzzle Zustand, wählen Sie die Zelle mit den wenigsten Möglichkeiten, wählen Sie eine der Möglichkeiten, und versuchen, das puzzle zu lösen. Wenn die Möglichkeit, dass Sie abgeholt führt zu einem puzzle Widerspruch, wiederherstellen der gespeicherten Zustand, gehen Sie zurück auf die Zelle und wählen Sie eine andere Möglichkeit. Falls keine der Möglichkeiten in der Zelle, die Sie ausgewählt löst das puzzle, wählen Sie die nächste Zelle mit den wenigsten Möglichkeiten. Zyklus über die verbleibenden Möglichkeiten und Zellen, bis das puzzle gelöst ist.

    Versuch, das Rätsel zu lösen, bedeutet die Suche durch jede Spalte und Zeile, sammeln die möglichen Werte der einzelnen Zelle, dann die Ausmerzung der Zellen mit nur einer Möglichkeit. Wenn alle Zellen werden entfernt, Sie haben das Rätsel gelöst.

    Können Sie eine logische /mathematische Methode, bei der die code versucht verschiedene Strategien, bis das Rätsel gelöst ist. Google-Suche mit "sudoku-Strategien" zu sehen, die verschiedenen Strategien. Mit logischen /mathematischen Methoden, die Ihr code kann "erklären", wie das Rätsel gelöst wurde.

    • Das ist ein bisschen eine bessere Erklärung backtracking (vielen Dank dafür), aber das scheint immer noch wie ein Durcheinander. Mit Ihrer Beschreibung der Rückverfolgung ("... und VERSUCHEN DAS RÄTSEL ZU LÖSEN ..."), es scheint, als ob der computer unter eine schwache Statistik und blind, es zu finden, ist der Weg nach unten einen dunklen tunnel in der Hoffnung, nicht stoßen, das nichts. Gibt es eine Möglichkeit, ich kann guide Sie ihn ein bisschen?
    • Meyer: Nein. Das ist, warum es heißt, einen brute-force-Methode. Du gehst zu tun eine Menge backtracking auf den meisten logisch komplexen sudoku-Rätsel. Aber Sie haben, um code für die Möglichkeiten.
    • Ich erwartete so viel =/. Ich bin wahrscheinlich zu tun haben, eine Anzahl dieser Probleme, mich zu entscheiden, Wann und wo ich das anwenden bestimmter Strategien für eine bessere Perspektive.
    InformationsquelleAutor Gilbert Le Blanc
  2. 1

    Wenn ich meine, ich dachte, dass ich Sie lösen kann jedes board mit einer Reihe von Regeln ohne backtracking. Dies erwies sich als unmöglich, als auch Rätsel-targeting menschliche Spieler möglicherweise erfordern, dass ein paar Hypothese.

    Also habe ich angefangen mit der Umsetzung der grundlegenden "Regeln" für die Lösung eines Rätsels zu finden versuchen, um die nächste Regel zu implementieren, die es erlauben würde, die Auflösung, wo Sie aufgehört letzten Zeit. Am Ende war ich gezwungen, fügen Sie eine rekursive brute Force-Algorithmus, aber die meisten Rätsel tatsächlich gelöst werden, ohne mit diesem.

    Schrieb ich einen blog-post über meinem sudoku-solver. Lesen Sie einfach durch den "Algorithmus" - Abschnitt und Sie erhalten eine ziemlich gute Idee, wie ich ging über es.

    http://www.byteauthor.com/2010/08/sudoku-solver/

    InformationsquelleAutor Kevin Coulombe
  3. 1

    Sollte jemand eine Referenz benötigen Android-Umsetzung, schrieb ich eine Lösung, verwendet der Algorithmus aus dem post oben.

    Vollständige open-source-code hier: https://github.com/bizz84/SudokuSolver

    Darüber hinaus ist diese Lösung lädt Sudoku-Rätsel im JSON-format von einem web-server und postet die Ergebnisse zurück.

    InformationsquelleAutor bizz84
  4. 0

    Sollten Sie sich Gedanken über die Verringerung der Sudoku-Problem auf eine Erfüllbarkeit problem.

    Diese Methode wird vermieden, dass Sie zu denken, zu mathematically aber mehr logically über die AI.

    Dem Ziel Schritt für Schritt ist im Grunde : 

    * Find all the constraints that a Sudoku has. (line, column, box).
* Write these constraints as boolean constraints.
* Put all these constraints in a Boolean Satisfiability Problem.
* Run a SAT solver (or write your own ;) ) on this problem.
* Transform the SAT solution into the solution of the initial Sudoku.

    Es wurde von Ivor Spence mithilfe SAT4J und finden Sie das Java-Applet, sein Werk hier : http://www.cs.qub.ac.uk/~I.Spence/SuDoku/SuDoku.html.

    Können Sie den download auch direkt der Java-code, der von SAT4J-website, um zu sehen, wie es Aussehen : http://sat4j.org/products.php#sudoku.

    Und schließlich der große Vorteil dieser Methode ist : Sie lösen kann N*N Sudokus, und nicht nur die typischen 9*9, das ist, denke ich, viel schwieriger für AI :).

    InformationsquelleAutor Valentin Montmirail
Schreibe einen Kommentar