Einen EFFIZIENTEN Sudoku Solver erstellen

Question

Ja, ich weiß, das ist nichts Neues und es gibt bereits viele Fragen (es hat sogar ein eigenes Tag), aber ich würde gerne einen Sudoku Solver in Java nur für den Zweck erstellen Ich trainiere mich selbst, um Code zu schreiben, der effizienter ist.

Wahrscheinlich die einfachste Möglichkeit, dies in einem Programm zu tun ist eine Tonne for Schleifen durch jede Spalte und Zeile analysieren, sammeln Sie die möglichen Werte jeder Zelle, dann die Zellen mit nur einer Möglichkeit (ob sie nur enthalten 1 Zahl, oder sie sind die einzige Zelle in ihrer Reihe/Spalte, die diese Zahl enthält), bis Sie ein gelöstes Puzzle haben. Natürlich sollte ein bloßer Gedanke an die Aktion in jedem Programmierer eine rote Fahne aufkommen lassen.

Was ich suche ist die Methodik, um diesen Sucker auf die effizienteste Weise zu lösen, die möglich ist (bitte versuchen Sie, nicht zu viel Code aufzunehmen - ich möchte diesen Teil herausfinden, ich selbst).

Ich möchte mathematische Algorithmen möglichst vermeiden - das wäre zu einfach und 100% nicht meine Arbeit.

Wenn jemand einen Schritt-für-Schritt, effizienten Denkprozess für die Lösung eines Sudoku Puzzlespiels (ob durch einen Menschen oder einen Computer) zur Verfügung stellen könnte, würde ich am glücklichsten sein :). Ich suche nach etwas, das vage ist (so ist es eine Herausforderung), aber informativ genug (damit ich nicht völlig verloren bin), um mich zu beginnen.

Vielen Dank,

Justian Meyer

EDIT:

an meinem Code Sehen, ich zum Denken habe: was sind einige der Möglichkeiten zur Speicherung dieser Lösung Zustände (dh wäre die Sudoku-Gitter). 2D-Arrays und 3D-Arrays kommen mir in den Sinn. Was könnte das Beste sein? 2D könnte von der Oberfläche aus leichter zu verwalten sein, aber 3D-Arrays würden auch die "Box"/"Käfig" -Nummer liefern.

EDIT:

Nevermind. Ich werde mit einem 3D-Array gehen.

Answer 1

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

Sie können eine Brute-Force-Methode verwenden, die jede Spalte und Zeile durchsucht, die möglichen Werte jeder Zelle sammelt und dann die Zellen mit nur einer Möglichkeit ausräumt.

Wenn Sie Zellen mit mehr als einer Möglichkeit übrig haben, speichern Sie den Puzzlezustand, wählen Sie die Zelle mit den wenigsten Möglichkeiten, wählen Sie eine der Möglichkeiten und versuchen Sie das Rätsel zu lösen. Wenn die von Ihnen gewählte Möglichkeit zu einem Puzzle-Widerspruch führt, stellen Sie den gespeicherten Puzzlezustand wieder her, gehen Sie zurück zur Zelle und wählen Sie eine andere Möglichkeit. Wenn keine der Möglichkeiten in der ausgewählten Zelle das Rätsel löst, wählen Sie die nächste Zelle mit den wenigsten Möglichkeiten. Gehe durch die verbleibenden Möglichkeiten und Zellen, bis du das Rätsel gelöst hast.

Der Versuch, das Rätsel zu lösen, bedeutet, jede Spalte und Zeile zu durchsuchen, die möglichen Werte jeder Zelle zu sammeln und dann die Zellen mit nur einer Möglichkeit auszusortieren. Wenn alle Zellen ausgesondert sind, hast du das Rätsel gelöst.

Sie können eine logisch/mathematische Methode verwenden, bei der Ihr Code verschiedene Strategien ausprobiert, bis das Puzzle gelöst ist. Suchen Sie in Google nach "Sudoku-Strategien", um die verschiedenen Strategien zu sehen. Mit logischen/mathematischen Methoden kann Ihr Code "erklären", wie das Puzzle gelöst wurde.

Answer 2

Als ich meins machte, dachte ich, ich könnte jedes Board mit einer Reihe von Regeln lösen, ohne irgendwelche Backtracking zu machen. Dies erwies sich als unmöglich, da sogar Rätsel, die auf menschliche Spieler abzielen, möglicherweise einige Hypothesen erfordern.

Also begann ich mit der Umsetzung der grundlegenden "Regeln" für die Lösung eines Puzzles, zu versuchen, die nächste Regel zu finden, um die Auflösung zu ermöglichen, wo es das letzte Mal aufgehört hat. Am Ende war ich gezwungen, einen rekursiven Brute-Forcing-Algorithmus hinzuzufügen, aber die meisten Rätsel sind tatsächlich gelöst, ohne dass man sie benutzt.

Ich habe einen Blogpost über meinen Sudoku-Solver geschrieben. Lies dir einfach den Abschnitt "Der Algorithmus" durch und du wirst eine ziemlich gute Idee bekommen, wie ich das gemacht habe.

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

Answer 3

Sollte jemand eine Referenz Android-Implementierung erforderlich ist, habe ich eine Lösung schrieb, dass der Algorithmus von der Post oben verwendet.

Voll Open-Source-Code hier: https://github.com/bizz84/SudokuSolver

Zusätzlich lädt diese Lösung Sudoku Rätsel im JSON-Format von einem Webserver und Beiträge die Ergebnisse zurück.

Answer 4

Sie sollten darüber nachdenken, das Sudoku-Problem auf SATisfiability problem zu reduzieren.

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

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 unter Verwendung SAT4J getan worden und Sie können das Java-Applet seiner Arbeit finden Sie hier: http://www.cs.qub.ac.uk/~I.Spence/SuDoku/SuDoku.html.

Sie können auch direkt den Java-Code von SAT4J-Website herunterladen, um zu sehen, wie es aussieht: http://sat4j.org/products.php#sudoku.

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