@Dow_Jones : danke, das werde ich mir später mal ansehen.
Gerade der Sudoku-Generator ist natürlich praktisch.
Wo hast du die “extremen” Sudokus her? Der Generator produziert ja nur bis “expert”.
Unter Minimum Sudoku findest du 49151 Sudokus in minimaler Konfiguration (17 gesetzte Positionen). Da sind auch die richtig miesen dabei. 
Unter Fast Sudoku Solver · GitHub gibt es eine Haskell-Version die alle 49151 Puzzel in 50 Sek. löst (auf einem Core Duo 2.4 Ghz). Unter Collection of random thoughts and insights: Sudoku puzzels revisited (Part 1) findet man die Beschreibung der ersten nicht ganz so schnellen Lösungen die dann zur Endlösung geführt haben.
[ot]Jetzt schreibt ihr hier so lange über ein so altes und ausgelutschtes Thema (und seine potentiell interessanten Details), dass ich fast versucht bin, es auch mal zu probieren…[/ot]
@ThreadPool : danke für die Links. Die werd ich dann auch mal durch meinen Solver jagen.
[ot]@Marco13: der Charme liegt ja auch darin, eine möglichst außergewöhnliche oder schnelle Lösung zu programmieren. Einen simplen Solver bekommt man ja ziemlich problemlos hin.
Wenn du auch einen Solver basteln solltest, dann kannst du ja ggf. das oben gepostete Interface implementieren:
[spoiler]```package net.byte_welt.sudoku;
public interface Sudoku {
/**
* Solve the sudoku.
*
* @return {code true} if sudoku could be solved
*/
boolean solve();
/**
* @return how many steps were needed to solve the sudoku.
*/
long getSteps();
}```[/spoiler][/ot]
Dann bitte in Frege, damit du auch noch was für das Leben lernst 
@Mod, kann man das ganze OT nicht in einen eigenen Thread auslagern?
Nun, was heißt “O” - es geht immernoch um einen Solver und seine Implementierung. Wenn’s das mit dem OT jetzt dann war, kann das wohl so bleiben.
Wenn ich mir die hier geposteten Sudokus so ansehe bekomme ich allerdings Zweifel, inwiefern die generierten „Expertensudokus“ wirklich repräsentativ für schwierige Rätsel sind (s.u.). Die „extremen“ hatte ich hier und da im Netz gefunden. Das sind die schon erwähnten Sudokus die von irgendwelchen Genies in die Welt gesetzt wurden. Die haben Namen wie **Escargot **oder Golden Nugget, muss man mal nach suchen.
Wenn ich die im Thread genannten Sets teste komme ich im Schnitt auf folgende Anzahl von Iterationen:
qt: 19.101
Minimum Sudoku*: 472.559
magictour**: 819.238
Hmm. 19000 geht ja noch. Aber der Rest… Cmrudolph, kannst du auch mal irgendein Maß dafür posten, wie gut dein Solver mit den Sets zurechtkommt? Würde mich interessieren.
Na, hau rein, Keule! 
PS:
[QUOTE=CyborgBeta;117118]@ down : Ich kann dir in dem Fall, ohne irgendeine Gegenleistung und ohne Häme, leider nicht weiterhelfen, wer was (wann) falsch gemacht hat, interessiert mich nicht. […]
Also wer Häme birgt und mich stört, dem helfe ich auch nicht, meinte ich damit.^^ [/QUOTE]
Ööhm - falls das an mich adressiert ist dann möchte ich dich um Entschuldigung bitten. Ich hatte nie die Absicht dich zu verhöhnen oder dich bei irgendetwas zu stören. (Ich muss zugeben das ich die vorherigen Postings nicht alle genau gelesen hatte; möglicherweise stand da etwas drin, in dessen Kontext mein Posting missverständlich wurde?!)
Klaro!
- für diese 49151 Rätsel braucht mein Java-Teil satte 5 Minuten…
**: http://magictour.free.fr/top1465
Werde ich tun, muss dafür meine Main noch ein bisschen anpassen, sodass sie die Dateien direkt laden kann. Ich werde die Laufzeiten dann auch nochmal mit deinem Solver vergleichen, damit man die Maße in etwa in Relation setzen kann.
Heute wird das wohl nichts mehr. Ich versuche es morgen noch einmal 
::haue ::slap1
Die Problemstellung von Sudoku an sich erschien mir wie ein Paradebeispiel eines Constraint Satisfaction Problems, wie ich es damals :grampa: im Studium in Artificial Intelligence: A Modern Approach durcharbeiten durfte. Und ich erinnerte mich an die „Landkarte von Australien“ und speziell den AC-3 algorithm - Wikipedia, the free encyclopedia . Irgendwann hatte ich auch mal angefangen, den selbst zu implementieren, aber da sowas bei mir dann immer in einer Generalisierungsorgie ausartet und versickert, habe ich jetzt mal auf existierenden Code zurückgegriffen. Der ist natürlich auch extrem high-level-abstrakt, und aus diesem CSP-Solver kriegt man erstmal nur ein „Assigment“ raus, wo man sich dann händisch wieder den Array zusammenpflücke müßte - das hab’ ich bisher auch nicht gemacht. Zusätzlich fehlt mir (mindestens) noch eine Methode, bevor ich hier was poste:
boolean thisSolutionIsReallyValid(int[][] array)
Aber es KÖNNTE sein, dass der (trotz seiner extremen High-Leveliggkeit und un-Optimiertheit) gar nicht sooo schlecht ist. Die „Anzahl der Schritte“ ist ein schwieriges Maß, wenn man (stark) unterschiedliche Verfahren vergleicht. Aber für dieses „1465“-Ding hat er z.B. ausgegeben:
Solving with SudokuExactCover
total steps: 261547762
total time : 30105 ms
Solving with SudokuCSPTest
total steps: 3119251
total time : 131206 ms
(nochmal: Nicht verifiziert!)
Ein komplexer Sudoku-Solver in nur wenigen Stunden - Respekt!
Soweit zur Pflicht. Kommen wir nun zur Kür: den Optimierungen. Ich kann dir schonmal sagen, das mein Java-Solver für dieses „1465“-Ding ca. 20 Sekunden benötigt. Und das heisst für Dich: Abmarsch, zurück ans Reißbrett!
::slap1
Komm schon, Marco, das kannst du besser!
@cmrudolph
Ich bin gespannt! 
“Komplex” - viel mehr als einen array in ein “CSP” zu packen, war das jetzt gar nicht…
[spoiler]
package net.byte_welt.sudoku.ac3;
import aima.core.search.csp.CSP;
import aima.core.search.csp.Domain;
import aima.core.search.csp.NotEqualConstraint;
import aima.core.search.csp.Variable;
public class SudokuCSP extends CSP
{
private void collectVariables()
{
int rows = 9;
int cols = 9;
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
addVariable(new Variable("F" + r + c));
}
}
}
public SudokuCSP(int array[][])
{
collectVariables();
Domain values = new Domain(new Integer[]
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 });
int rows = 9;
int cols = 9;
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
Variable v = getVariables().get(c+r*cols);
if (array[r]``` != 0)
{
setDomain(v, new Domain(new Integer[] { array[r]``` }));
}
else
{
setDomain(v, values);
}
}
}
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
for (int x = c+1; x < cols; x++)
{
Variable v0 = getVariables().get(c+r*cols);
Variable v1 = getVariables().get(x+r*cols);
addConstraint(new NotEqualConstraint(v0, v1));
}
}
}
for (int c = 0; c < cols; c++)
{
for (int r = 0; r < rows; r++)
{
for (int x = r+1; x < rows; x++)
{
Variable v0 = getVariables().get(c+r*cols);
Variable v1 = getVariables().get(c+x*cols);
addConstraint(new NotEqualConstraint(v0, v1));
}
}
}
for (int cc = 0; cc < 3; cc++)
{
for (int cr = 0; cr < 3; cr++)
{
for (int c0=0; c0<3; c0++)
{
for (int r0=0; r0<3; r0++)
{
int gc0 = cc * 3 + c0;
int gr0 = cr * 3 + r0;
for (int c1=c0+1; c1<3; c1++)
{
for (int r1=r0+1; r1<3; r1++)
{
int gc1 = cc * 3 + c1;
int gr1 = cr * 3 + r1;
Variable v0 = getVariables().get(gc0+gr0*cols);
Variable v1 = getVariables().get(gc1+gr1*cols);
addConstraint(new NotEqualConstraint(v0, v1));
}
}
}
}
}
}
}
}
(ja, ist nur hingehackt…)
[/spoiler]
… aber das jetzt noch “Mikrooptimieren” ist nicht zuletzt genau deswegen schwierig: Man hat praktisch keine Angriffspunkte mehr. VIelleicht die Reihenfolge der Constraints umsortieren oder so…? Aber ich denke, wenn man die Ideen vom AC3 in ein Programm einfließen läßt, das schön effizient auf rohen arrays arbeitet, könnte das was bringen. (BTW: Der konkrete Solver macht auch noch andere, methodische Optimierungen - ich müßte auch noch probieren, ob eine von denen für das Sudoku vielleicht nachteilhaft ist…)
@Dow_Jones : Mein Ansatz mit pre Proces nach den bekannten Regeln für Sudoku war glaube ich folgender:
*
*
*
*/
package sudoku;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
/**
* @author CB
*/
public class Sudoku {
private int[] sudoku;
private int[][] rowIdxs;
private int[][] colIdxs;
private int[][] sqrIdxs;
private LinkedList<Integer>[][] offen;
public Sudoku(int[] sudoku) {
if (sudoku == null || sudoku.length != 81) {
//...
}
this.sudoku = new int[81];
rowIdxs = new int[81][9];
colIdxs = new int[81][9];
sqrIdxs = new int[81][9];
offen = new LinkedList[81][2];
for (int i = 0; i < 81; i++) {
this.sudoku** = sudoku**;
for (int j = 0; j < 9; j++) {
//row**[j]= , col , sqr...
}
offen**[0] = new LinkedList<Integer>(Arrays.asList(i)); // nur Idx
offen**[1] = new LinkedList<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
}
preProces();
Arrays.sort(offen, new Comparator<LinkedList<Integer>[]>() {
@Override
public int compare(LinkedList<Integer>[] t, LinkedList<Integer>[] t1) {
return Integer.compare(t[1].size(), t1[1].size());
}
});
}
private void preProces() {
throw new UnsupportedOperationException("Not supported yet.");
//entferne aus offen, welche für i in row col sqr schon eingesetzt sind
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
}
}
Weiter kann ich wirklich nicht zaubern.^^
Riesige Mengen von Sudoku s verarbeiten. : /
So, einmal holterdipolter die Sudokus durch die Solver gejagt. Ich habe die Einlesezeit immer mitgemessen.
@Dow_Jones : dein Solver ist etwa doppelt so schnell wie meiner. Allerdings habe ich auch noch nicht optimiert. Ich muss da nochmal den Profiler anschmeißen
Die Ergebnisse:
Solver @Dow_Jones :
Puzzles: 49.151
Solved: 49.151
472.559 backtracking iterations per sudoku
Total time: 434.610ms
Puzzles: 1.465
Solved: 1.465
819.238 backtracking iterations per sudoku
Total time: 20.927ms
Mein Solver:
Puzzles: 49.151
Solved: 49.151
Duration: 619.552ms
Total steps: 3.166.151.515
Steps/Sudoku: 64.417
Puzzles: 1.465
Solved: 1.465
Duration: 52.001ms
Total steps: 261.547.762
Steps/Sudoku: 178.531
@Marco13 : du hast 'nen schnelleren Rechner als ich
Interessant. Aber vielleicht reichte es ja schon wenn du das Rätsel ersteinmal mit simplen Logikregeln vereinfachst? Ohne die würde das Backtracking bei mir 4-5 Stunden für das 49.151er Set brauchen… (hochgerechnet, gemessen habe ich es nicht).
Hier das Set nochmal nach Anwendung der beiden single Regeln (wodurch schon mehr als 60% der freien Zellen befüllt werden konnten). Magst du das noch mal fix durch deinen Solver jagen? Damit sollte er doch abgehen wie Schmidts Katze.
49.151 Sudokus: Share-Online - dl/WIXH6BONRG
Ich sag doch, erst in die Felder einzusetzen, die die wenigsten Zahlen habn, ist schon optimale Strategie/Kalkül.
Ich probiert das gleich mal aus, aber ich hab vorhin den dotNetFx-Ordner partiell permanent gelöscht, jetzt ist die Kacke am dampfen.
[QUOTE=CyborgBeta]Ich sag doch, erst in die Felder einzusetzen, die die wenigsten Zahlen habn, ist schon optimale Strategie/Kalkül.
Ich probiert das gleich mal aus, aber ich hab vorhin den dotNetFx-Ordner partiell permanent gelöscht, jetzt ist die Kacke am dampfen.[/QUOTE]
Da drücke ich dir mal die Daumen, bei der Wiederherstellung! 
Ich hatte damals ebenfalls damit experimentiert die Reihenfolge der auszufüllenden Zellen zu variieren, dazu noch die Reihenfolge, in welcher die Ziffern ausprobiert wurden. Mit beiden Ansätzen hatte ich leider keinen Erfolg. Die produzierten bei handelsüblichen Sudokus zu viel Overhead und zu wenig Benefit, als das sich damit unterm Strich eine kürzere Laufzeit erreichen liess. -_-
Wie handhabst du das denn? Ersteinmal die Anzahl der möglichen Ziffern für jede Zelle ermitteln, und diese Anzahlen+zugehörige Zellen dann mit irgendeinem coolen Algo sortieren? Oder ermittelst du dynamisch welche Zelle als nächstes ausgefüllt werden soll? Ich selbst bin leider mit beiden Verfahren auf keinen besonders grünen Zweig gekommen, daher interressieren mich die Ergebnisse anderer Leute sehr! 
Bin erst am Montag wieder zu Hause, werde das dann aber gleich mal ausprobieren. Ich hatte mir gestern noch einmal mit dem Profiler angesehen, wo mein Solver Zeit „verschwendet“. Das sind alles elementare Operationen, sodass ich nicht glaube, dass man durch „Codeoptimierung“ noch etwas herausholen kann. An ein Preprocessing mit Naked Singles und Hidden Singles hatte ich auch gedacht, weil das den Zustandsraum ggf. deutlich verkleinert.
*** Edit ***
Das hatte ich auch ausprobiert - deshalb sind bei mir teilweise noch Komparatoren implementiert.
Ich habe die vorbearbeitete Sudokuliste jetzt doch (auf einem deutlich langsameren Rechner) lösen lassen. Die Ergebnisse fielen aber eher enttäuschend aus.
Ohne Preprocessing:
Total steps: 3.166.151.515
Steps per sudoku: 64.416
Total duration: 852.907ms
Solved: 49.151
Mit Preprocessing (die Zeit, die für das Preprocessing benötigt wird, ist natürlich nicht enthalten, da die Ausgangsliste die Optimierungen enthält):
Total steps: 3.112.281.039
Steps per sudoku: 63.320
Total duration: 855.250ms
Solved: 49.151
Bei den langen Laufzeiten ist die Verbesserung also nicht spürbar.
Sehr viele Sudokus sind nach dem Preprocessing komplett gelöst. Aufgrund der geringen Differenz der Schritte hatte ich zuerst vermutet, dass ich den Vergleich falsch angestellt hatte. Allerdings ist es offensichtlich so, dass der Solver mit den durch Preprocessing lösbaren Sudokus auch extrem gut zurecht kommt.
In der linken Spalte habe ich mal die Anzahl der Iterationen ohne Preprocessing und in der rechten die mit Preprocessing der ersten 10 Sudokus in der Liste aufgeführt:
2099 0
2110 0
923 0
2080 0
832 211
949 0
1560 530
5159 4471
1196 546
1581 777
Die meisten Sudokus lassen sich in unter 10.000 Schritten lösen. Einige wenige benötigen dafür sehr viele (mehr als 1.000.000) und reißen den Schnitt nach oben. Interessant wären vielleicht noch Häufigkeitsanalysen, die über ein arithmetisches Mittel hinausgehen.