ich weiß nicht ob sich das auf vorher genannte Tatsachen bezieht,
ansonsten sind solche Unterstellungen, dass es nicht bereits so wäre, unabhängig von den sonstigen Code-Hinweisen und unabhängig von allen Vorkommnissen vollkommen deplatziert,
kann man bei einem beliebigen Gast evtl. so dahin sagen, wobei auch eher zu vermeiden,
aber dann hat es ja auch keine größere Bedeutung, aber nicht zwischen Forum-Mitgliedern
Also nur, um das mal einzuordnen, obige Implementierung gehört mit zu den schnellsten für Sudoku (noch nicht beliebiger Größe).
Es ging mir einfach mal darum, das so aufzuteilen, um zu sehen, ob das mit 3x 2-d. Arrays Sinn macht.
i, j, k, l, m, n,… lese ich lieber, als wenn da irgendein Scheiß steht. Außerdem wieso dürfen Methodennamen nicht deutsch sein, wenn man Umlaute vermeidet?
Wenn man von der Sprache absieht, entspricht Obiges auch den offiziellen Code-Conventions, die gibt es nämlich auch, wenn du das noch nicht wusstest, und die sind auch nicht 200 Seiten lang.
Egal, ich wollte mymax helfen. Eigentlich wollte ich gar nicht, das das im Internet geschrieben wird. Nu is passiert.
Ich denke/hoffe auch nicht, das das in Schule/Abi drankommen wird, weil er eine Stunde dafür brauchen wird, das hinzuschreiben.
Ack.?
Ich weiß, meine Erklärungen sind immer Scheiße.
(Methoden/Ausgabe) Verbessert und dokumentiert:
[spoiler]```/*
/**
@author CB at http://forum.byte-welt.net/
*/
public class Sudoku {
private int[][] row = new int[9][9];
private int[][] col = new int[9][9];
private int[][] sqr = new int[9][9];
/**
public boolean solveOne(int i) {
if (!richtig(i)) {
return false;
}
if (vollstae(i)) {
return true;
}
int j = i / 9, k = i % 9, l = j / 3 * 3 + k / 3, m = (j * 3 + k % 3) % 9, i2 = i + 1;
if (row[j][k] == 0) {
for (int n = 1; n <= 9; n++) {
row[j][k] = n;
col[k][j] = n;
sqr[l][m] = n;
if (solveOne(i2)) {
return true;
}
}
row[j][k] = 0;
col[k][j] = 0;
sqr[l][m] = 0;
} else if (solveOne(i2)) {
return true;
}
return false;
}
private boolean richtig(int i) {
if (i > 0) { // etwas unschön
i–;
}
int j = i / 9, k = i % 9, l = j / 3 * 3 + k / 3;
// überprüfe (schnell) jeden mit jedem (fast unnötig)
return pruefe(row, j) && pruefe(col, k) && pruefe(sqr, l);
}
private boolean vollstae(int i) {
return i >= 81;
}
private boolean pruefe(int[][] array, int i) {
for (int j = 0; j < 8; j++) { // überprüfe (schnell) jeden mit jedem (fast unnötig)
if (array**[j] == 0) {
continue;
}
for (int k = j + 1; k < 9; k++) {
if (array**[j] == array**[k]) {
return false;
}
}
}
return true;
}
public void printSudoku() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (row**[j] != 0) {
System.out.print(row**[j] + " “);
} else {
System.out.print(“x “);
}
if ((j + 1) % 3 == 0) {
System.out.print(” “);
}
}
if ((i + 1) % 3 == 0) {
System.out.println(””);
}
System.out.println(”");
}
}
public static void main(String[] args) {
Sudoku sudoku = new Sudoku(new int[][]{ // leicht
{3, 0, 0, 0, 1, 5, 0, 4, 2},
{7, 5, 6, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 9, 0, 0, 0, 8},
{0, 0, 0, 3, 0, 0, 4, 0, 0},
{0, 0, 0, 5, 0, 2, 8, 0, 0},
{1, 7, 0, 0, 0, 0, 0, 5, 3},
{0, 0, 1, 0, 0, 7, 9, 8, 6},
{2, 0, 8, 1, 0, 0, 0, 0, 0 },
{0, 0, 0, 0, 3, 6, 1, 2, 5}
});
sudoku.printSudoku();
System.out.println(sudoku.solveOne(0));
sudoku.printSudoku();
sudoku = new Sudoku(new int[][]{ // unmöglich
{3, 0, 0, 0, 1, 5, 0, 4, 2},
{7, 5, 6, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 9, 0, 0, 0, 8},
{0, 0, 0, 3, 0, 0, 4, 0, 0},
{0, 0, 0, 5, 0, 2, 8, 0, 0},
{1, 7, 0, 0, 0, 0, 0, 5, 3},
{0, 0, 1, 0, 0, 7, 9, 8, 6},
{2, 0, 8, 1, 0, 0, 0, 0, 9 },
{0, 0, 0, 0, 3, 6, 1, 2, 5}
});
sudoku.printSudoku();
System.out.println(sudoku.solveOne(0));
sudoku.printSudoku();
sudoku = new Sudoku(new int[9][9] // zeitintensiv
);
sudoku.printSudoku();
System.out.println(sudoku.solveOne(0));
sudoku.printSudoku();
}
}
Ausgabe:
[spoiler]```run:
3 x x x 1 5 x 4 2
7 5 6 x x x x x x
x x x x 9 x x x 8
x x x 3 x x 4 x x
x x x 5 x 2 8 x x
1 7 x x x x x 5 3
x x 1 x x 7 9 8 6
2 x 8 1 x x x x x
x x x x 3 6 1 2 5
true
3 8 9 7 1 5 6 4 2
7 5 6 2 8 4 3 9 1
4 1 2 6 9 3 5 7 8
8 2 5 3 7 1 4 6 9
6 9 3 5 4 2 8 1 7
1 7 4 9 6 8 2 5 3
5 3 1 4 2 7 9 8 6
2 6 8 1 5 9 7 3 4
9 4 7 8 3 6 1 2 5
3 x x x 1 5 x 4 2
7 5 6 x x x x x x
x x x x 9 x x x 8
x x x 3 x x 4 x x
x x x 5 x 2 8 x x
1 7 x x x x x 5 3
x x 1 x x 7 9 8 6
2 x 8 1 x x x x 9
x x x x 3 6 1 2 5
false
3 x x x 1 5 x 4 2
7 5 6 x x x x x x
x x x x 9 x x x 8
x x x 3 x x 4 x x
x x x 5 x 2 8 x x
1 7 x x x x x 5 3
x x 1 x x 7 9 8 6
2 x 8 1 x x x x 9
x x x x 3 6 1 2 5
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
true
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2
BUILD SUCCESSFUL (total time: 0 seconds)
```[/spoiler]
Das braucht alles 0 Sekunden, das ist schnell und für alle Fälle anwendbar, die man sich denken kann. :verzweifel:
@mymaksimus : Hast du das Prinzip der rekursion verstanden? Deine Erklärung, das klingt alles schlüssig.
freundliche Grüße@CyborgBeta
Ich glaube er hatte es schon vorhin verstanden, als er danke für die Hilfe schrieb und festgestellt hatte, das er hätte auch selber die Idee hätte haben können, das null ein valider Rückgabewert ist. Den ganzen restlichen Code den du fabriziert hast, hast du nur für dich gemacht und für niemanden anderes.
Also kurz zusammengefasst
Ja bei einer Rekursion sollte der Aufruf nur die Informationen haben/verwenden, die er übergeben bekommen hat.
Üblicherweise sieht eine Rekursion so aus
abbruchbedingung erfüllt?
wenn ja, gebe Ergebnis zurück
andernfalls rufe dich selber mit Schritt+1 auf
…
check.
ich bin mir sicher das ich das prinzip von rekursion auch vor diesem thread verstanden habe.
die sache mit dem null zurückgeben schwirrte mir sogar kurz im kopf rum, ich habe diesen
gedanken aber verworfen, weil null returns doch eigentlich zu schlechtem stil gehören, oder?
Aber das ist wieder ein thema, worüber man lieber einen neuen thread aufmacht. ist auf jedenfall
umstritten das thema.
aber hier wohl volkommen legitim 
[QUOTE=Unregistered]@CyborgBeta
Ich glaube er hatte es schon vorhin verstanden, als er danke für die Hilfe schrieb und festgestellt hatte, das er hätte auch selber die Idee hätte haben können, das null ein valider Rückgabewert ist. Den ganzen restlichen Code den du fabriziert hast, hast du nur für dich gemacht und für niemanden anderes.
Also kurz zusammengefasst
Ja bei einer Rekursion sollte der Aufruf nur die Informationen haben/verwenden, die er übergeben bekommen hat.
Üblicherweise sieht eine Rekursion so aus
abbruchbedingung erfüllt?
wenn ja, gebe Ergebnis zurück
andernfalls rufe dich selber mit Schritt+1 auf
[/QUOTE]
Das stimmt, wenn du neue Ergebnisse hast, immer her damit. Akkumulierender Parameter der rekursiven Methode/Funktion, ist gemeint. Es wurde noch nicht darüber gesprochen, wie man ein Sudoku erstellt, ob Durchlauf Links, rechts, oben und unten optimal wäre. Ich bin erst mal ein paar Tage raus/ außer Gefecht. Sry, man sieht sich, bis dann bald hoffentlich.
@ mymax : Wenn du zwei Tage Beiträge nicht liest, wäre das nicht (so) schlimm. ^^ Sry, bitte nicht fertigmachen.
Mein Kopf brummt schon wieder.
Mich regt das auf, und hab mir Gedanken drüber gemacht.
Man kann Algo minimal beschleunigen und verbessern, wenn man mehr über das als Parameter übergebene Sudoku weiß.
Ist es leer?
Ist es teilweise (richtig) ausgefüllt?
Ist es vollständig (richtig) ausgefüllt?
Also 5 Fälle.
Je nachdem, an welcher Stelle im Algo man richtig() aufruft, können 3 bis 5 dieser Fälle abgedeckt werden.
Wenn man einen anderen Algo “vorschaltet”, der bereits (teilweise) ausgefüllte Sudokus prüft, und richtig() innerhalb des Schleifenrumpfs schreibt, dann kann der eigentliche Algo “beschleunigt” werden. Auch minimiert das die vielen rekursiven Aufrufe.
Also man bleibt bei der Rekursion, aber der Algo kann optimiert werden.
Richtig, true, valide, akzeptiert, schön geschrieben, verständlich,… ?
Warum sollte man diese Fälle unterscheiden? Und was sollte das für Geschwindigkeitsvorteile bringen?
Nebenbei bemerkt lassen sich die Fälle noch nicht einmal sauber trennen: Ein “leeres” Sudoku (ich vermute mal, du meinst eine Vorgabe, wie sie in der Zeitung steht) ist nicht unbedingt “minimal”: Es sind meist mehr Zahlen vorgegeben, als für eine eindeutige Lösung nötig wären, weil es sonst für die Leser zu schwer würde. Und damit gibt es keinen klaren Unterschied zwischen “leeren” und “teilweise ausgefüllten” Sudokus.
Du verkomplizierst wieder, ohne ein Ziel oder einen Nutzen. Selbst wenn da ein minimaler Geschwindigkeitsvorteil drin wäre (was ich nicht glaube), rechtfertigt das nicht unbedingt, die API oder die Programmstruktur zu verschandeln.
Ich sag ja, ist nicht so ganz trivial…
Wenn ein teilweise richtig ausgefülltes Sudoku vorgeben ist, dann müssen die schon ausgefüllten Felder nicht vor der Schleife übergeprüft werden, die die übrigen “Kandidaten” einsetzt, sondern nur die “neu” eingesetzten Kandidaten.
Je nachdem, wie viele Aufrufe und Länge des Sudokus, könnte es da “real” schon um Millisekunden oder Nanosekunden gehen.
Ist das zu vorschnelle Optimierung?
Mal aus dem Bauch raus: Ja.
erstens… und zweitens war das in diesem thread sowas von überhaupt nicht thema…
OK, vielleicht bin ich ein bisschen verrückt/denk in alle Richtungen, aber heute wird das definitiv nix mehr.^^
<einigermaßen offtopic>
[QUOTE=CyborgBeta]Mich regt das auf, und hab mir Gedanken drüber gemacht.
Man kann Algo minimal beschleunigen und verbessern, wenn man mehr über das als Parameter übergebene Sudoku weiß.[/QUOTE]
Ich begrüße es immer sehr, wenn sich jemand interessehalber Gedanken über solche „Probleme“ macht. Man müsste sie anschließend natürlich an der Praxis messen, und diese Arbeit kann ich dir vielleicht z.T. abnehmen: Ich hatte vor Jahren mal einen Sudokusolver gebastelt, und im Zuge dessen einige Strategien getestet. Dabei kam ich zu der Erkenntnis, das die schnellste allgemeingültige* Methode einfach darin besteht
a) in einem preprocessing-Schritt die 2-3 simpelsten Logikregeln auf das Sudoku anzuwenden und
b) anschließend einen Brute-Force darüber laufen zu lassen, der in die noch freien Felder die noch verfügbaren Ziffern einträgt
Weitere lohnende Optimierungen habe ich nicht gefunden. Die BF-Schleife war einfach so schnell, das jeder Versuch die Anzahl der Schleifendurchläufe zu minimieren in einer überproportionalen Verlängerung des Schleifenkörpers ausartete**. Auch die Anwendung komplizierterer Logikregeln in a) führte zu einer verschlechterung der Laufzeit***.
Aus dieser Erfahrung heraus wäre ich vorsichtig damit Beschleunigungen zu prophezeien solange ich es nicht selber getestet habe. Falls du das Thema weiterverfolgen möchtest würde ich mich allerdings freuen wenn du deine Erkenntnisse anschließend an uns/mich weitergibst. 
PS: Ich war damals über ein Paper gestolpert, in welchem Mathe Profs (von der Uni Notre Dame, wenn ich mich richtig erinnere) darlegten wie man ein Sudoku rein durch Mathematik, also ganz ohne herumprobieren, lösen kann. Gelesen habe ich das Paper allerdings nicht, sah mir beim überfliegen zu kompliziert aus… :nevreness:
</einigermaßen offtopic>
Danke für deinen Beitrag. Ich wiederhole mal:
Preprocessing
“Mikro-Optimierung”
extrem schwer
GNU-Tool.
Wenn ich jetzt sehr lange krame, finde ich vielleicht auch noch ein 2 Jahre altes Programm. Der Brute-Force ist schon schnell hat aber bei einem schwierigen Sudoku eine längere Laufzeit. Extrem schwer wäre es, wenn ein/zwei/oder mehrere falsche Kandidaten erst in einer hohen Aufrufkettentiefe bemerkt würden, ein Sudoku bis dahin aber ‘richtig’ “ausgefüllt werden kann”.
Ich suche mal, kann dir aber nicht zu viel versprechen.
[OT][quote=Dow_Jones;117087]<einigermaßen offtopic>…</einigermaßen offtopic>
[/quote]
Kein html erlaubt… 
[…] nun ja [/…] ← BB
Der ‚einigermaßen offtopic‘ Tag wäre trotzdem interessant - so zum abschwächen. :)[/OT]
Nebenbei: Der Premierminister von Singapur hat seinen Sudoku-Solver (in C#, etwas älter) auf Facebook gestellt: https://www.facebook.com/leehsienloong/photos/a.344710778924968.83425.125845680811480/905828379479869/
@Dow_Jones : Ich hatte oben ja schon meinen Exact Cover-Ansatz gepostet. Kannst du vielleicht auch mal deine beste Lösung zeigen? Mich würde interessieren, wie die miteinander verglichen abschneiden.
*** Edit ***
Ah, der Exact Cover-Ansatz ist der Dancing-Links-Algorithmus 
Hatte ich mittlerweile komplett vergessen.
Dass du das für kleine Mikrocontroller programmiert hast, bedeutet wahrscheinlich, dass du das eher in C entwickelt hast und daher keinen vergleichbaren Java-Quellcode hast.
*** Edit ***
Es war dieses Paper, an dem ich mich bei der Implementierung entlanggehangelt habe.
[ OT unauffällig]
Soso, der Premierminister von Singapur ist (auch) Programmierer, die Welt ist ‘eigentlich’ klein. Ich hab nachgeschaut, Permutationen mit O/Theta(n * n!) (Fakultät) Laufzeit gehört nicht mit zu den schwierigsten Problem, die wir kennen, glaube ich.
@ 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.
Nach 36 Stunden kann ich nun auch endlich schlafen.^^
Hier muss wirklich nicht optimiert werden, ausschließlich Mathematiker, wenn auch Algo.künstler, bin ich wirklich nicht.
[ /OT unauffällig]
Für den Controller war’s in Assembler, aber vorher hatte ich, der Bequemlichkeit halber, erstmal in Java herumexperimentiert (Quellcode im Anhang). Interessant ist dabei eigentlich nur die Methode Solver.solve(short[] sudoku). Das Array muss halt 81 Elemente groß sein und enthält das vorgegebene Sudoku, leere Felder werden durch den Wert 0 repräsentiert. Die Methode füllt das Rätsel dann aus.
Für verschiedene von QQWinggenerierte Sudokus benötigt das Backtracking im Schnitt soviele Iterationen :
[table=„width: 600“]
simpleeasyintermediateexpertextreme
ohne Logik338.993330.357351.471276.4551.638.556
mit naked single0174.879232.03168.8961.638.556
mit hidden single3.4412.43320.28113.5901.476.404
mit ns und hs0015.0649.8391.476.404
[/table]
Zeiten kann ich dir nicht nennen, weiss nur noch das der Controller jedes Rätsel „augenblicklich“ gelöst hatte (abgesehen von den extremen natürlich, aber die sind sowieso eine Klasse für sich…)
Also wer Häme birgt und mich stört, dem helfe ich auch nicht, meinte ich damit.^^ [ /OT]
Selbst extrem, bei 1GHz wäre das eine tausendstel Sekunde.
Extrem: 81. Feld, wird in der größten Rek.Tiefe geprüft, vertikal und horizontal schon vorher, so muss alles vorher überprüft und richtig ausgefüllt werden können.
0 0 0
0 9 0
0 0 9 als 9. Block vielleicht.
Edit: Sollen wir uns wieder vertragen?