Entwickler-Ecke
Alle Sprachen - Alle Plattformen - Java Sudoku Löser
LINUS19 - Sa 30.12.17 13:21
Titel: Java Sudoku Löser
Hallo,
Ich wollte einen Sudoku Löser machen, den Lösungsalgorithmus mit rekursivem backtracking habe ich so weit verstanden, doch ich komme bei der Lösemethode nicht weiter. Vielleicht kann mir ja wer einen Tipp geben.
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
|
public class SudokuSolver {
static boolean solve(int i, int j,int Matrix[][]) {
if(i==9 && j==9)
return true; //rechtes unteres Feld erreicht
if(i==9) { // Eine Zeile weiter nach unten
i=0;
j++;
}
if(Matrix[i][j] ==0) {
for(int value=1; value<=9; value++) { // Alle Zahlen von 1-9 werde getestet
if(save(i, j, value, Matrix)==true) { // GEhe auf nächstes freies Feld
return solve(i+1, j, Matrix);
}
}
}
Matrix[i][j]=0; //Feld wird auf Null gesetzt
return false;
}
static boolean save(int i,int j, int value, int Matrix[][]) {
for(int k=0; k<9; k++) { // Zahl in Reihe doppelt
if(value== Matrix[i][k])
return false;
}
for(int k=0; k<9; k++) { // Zahl in Spalte doppelt
if(value== Matrix[k][j])
return false;
}
// Block{
//return false; Zahl im 3*3 Block doppelt
//}
return true; // Zahl ist richtig
}
public static void print(int Matrix[][]) { // Sudoku Ausgabe
System.out.printf("Lösung:");
System.out.println();
for (int x = 0; x < Matrix.length; x++) {
for (int y = 0; y < Matrix.length; y++) {
System.out.print(Matrix[x][y] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int Matrix[][] = // Sudoku was gelöst wird
new int[][] {{ 1,0,0,0,0,0,0,0,3},
{ 4,6,0,0,0,0,7,0,0},
{ 6,0,5,0,0,8,0,0,0},
{ 0,7,0,8,0,2,0,3,0},
{ 0,0,2,0,9,0,0,0,0},
{ 0,0,0,0,7,0,0,0,5},
{ 0,0,0,0,0,9,4,0,0},
{ 0,8,0,4,0,0,0,0,1},
{ 3,0,0,0,0,1,0,8,6}};
solve(1, 1, Matrix);
print(Matrix); // bei der Ausgabe verändert sich nichts
System.out.println(save(0, 0, 3, Matrix));
}
} |
Jann1k - Sa 30.12.17 14:30
Es wäre gut, wenn du etwas mehr beschreiben könntest, wo genau das Problem ist. Terminiert der Algorithmus nicht? Kommst du mit der "Blocküberprüfung" nicht weiter? Bekommst du falsche Ergebnisse?
Beim ersten Überlesen: Ich glaube deine Abbruchbedingung ist nicht korrekt (i und j sollten niemals beide 9 sein, da j nur erhöht wird, wenn i wieder auf 0 gesetzt wird. Ich denke da müsste eher ein
(i==9 && j==8) hin. Habs aber nicht getestet.
Moderiert von 
Th69: Code-Tags hinzugefügt
LINUS19 - Sa 30.12.17 15:21
Die Blocküberprüfung wollte ich später machen.
Das Programm hört auch auf, aber das Sudoku was ausgegeben wird ist unverändert zu dem was ich eingegeben habe.
Th69 - Sa 30.12.17 15:36
Du veränderst die Matrix ja auch nicht (außer das Nullsetzen)...
Am besten du verwendest dafür den Debugger, um Schritt für Schritt durch den Code zu gehen.
PS: Du solltest in der main für den solve-Aufruf bei (0,0) anfangen (Arrays sind null-basiert) - und daher auch die Abbruchbedingung anpassen (wundert mich allerdings, daß keine Exception fliegt)...
LINUS19 - Sa 30.12.17 16:05
Ich habe die solve( Methode jetzt so verändert:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
| if(i==8 && j==8)
return true; //rechtes unteres Feld erreicht
if(i==9) { // Eine Zeile weiter nach unten
i=0;
j++;
}
if (Matrix[i][j] != 0) { // Nur Felder mit 0 sollen verändert werden
solve(i+1,j,Matrix); //-> gehe einen Schritt weiter
}
for(int value=1; value<=9; value++) { // Alle Zahlen von 1-9 werde getestet
if(save(i, j, value, Matrix)==true) { // Gehe auf nächstes freies Feld
Matrix[i][j]=value; //setze den Wert
if(solve(i+1,j,Matrix)==true)
return true;
}
}
Matrix[i][j]=0; //Feld wird auf Null gesetzt
return false; |
Und das Ergebnis:
Lösung:
0 2 4 5 6 7 8 9 3
0 6 1 2 3 8 9 7 5
0 1 5 3 2 9 7 4 8
0 7 6 9 8 1 2 3 4
0 8 3 1 9 4 5 6 2
0 4 9 8 1 6 3 5 7
0 5 2 6 7 3 4 1 9
0 3 8 7 4 5 6 2 1
0 9 7 4 5 2 1 8 6
Achso wegen dem Debbuger, ich habe schon öfter versucht ihn einzusetzen hat mir aber auch nicht viel gebracht ,weil ich damit nicht umgehen kann
Th69 - Sa 30.12.17 17:14
Aber wie willst du programmieren (lernen), wenn du die Tools nicht beherrschst?
Welche IDE verwendest du denn?
Und wegen dem Ergebnis (die Null-Spalte) schau dir mein PS aus meinem vorherigen Beitrag an.
LINUS19 - Sa 30.12.17 19:32
Ich verwende Eclipse Oxygen.
Das mit der Nullten Spalte funktioniert immer noch nicht(auch nicht mit
i==9 && j==8), ich weiss nicht was ich da noch ändern könnte.
Warum wird die 8 zu so einem Smiley?
Moderiert von Th69: Code-Tags hinzugefügt
LINUS19 - So 31.12.17 16:14
Ich habe den Fehler jetzt gefunden vordem solve(i+1,j,Matrix)
Quelltext
1:
2:
3:
| if (Matrix[i][j] != 0) { // Nur Felder mit 0 sollen verändert werden
return solve(i+1,j,Matrix); //-> gehe einen Schritt weiter
} |
fehlte einfach ein return, damit es übersprungen wird.
Das ist jetzt das Ergebnis:
Lösung:
1 2 4 5 6 7 8 9 3
4 6 1 3 8 5 7 2 9
6 1 5 7 3 8 9 4 2
5 7 9 8 1 2 6 3 4
7 3 2 6 9 4 1 5 8
2 4 8 9 7 6 3 1 5
8 5 3 1 2 9 4 6 7
9 8 6 4 5 3 2 7 1
3 9 7 2 4 1 5 8 6
Christian S. - So 31.12.17 16:37
Da kommt im oberen, linken Block jetzt aber dreimal eine Eins vor. Oder habe ich Deine Darstellung missverstanden :gruebel:
LINUS19 hat folgendes geschrieben  : |
Lösung:
1 2 4 5 6 7 8 9 3
4 6 1 3 8 5 7 2 9
6 1 5 7 3 8 9 4 2
5 7 9 8 1 2 6 3 4
7 3 2 6 9 4 1 5 8
2 4 8 9 7 6 3 1 5
8 5 3 1 2 9 4 6 7
9 8 6 4 5 3 2 7 1
3 9 7 2 4 1 5 8 6 |
//edit: Ah, sorry, hatte das hier überlesen:
| LINUS19 hat folgendes geschrieben : |
| Die Blocküberprüfung wollte ich später machen. |
LINUS19 - So 31.12.17 18:50
Bei der Blocküberprüfung habe ich doch noch ein Problem, wenn ich folgendes in die Methode einfüge:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| for (i = 0; i < 9; i = i + 3) { // Blocküberprüfung
for (j = 0; j < 9; j = j + 3) {
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
if (Matrix[a + i][b + j] == value)
return false;
}
}
}
} |
Wird das Sudoku was gelöst werden soll unverändert ausgegeben.
ub60 - So 31.12.17 20:44
Du prüfst hier alle Blöcke auf einmal. Du solltest jeweils nur einen Block prüfen und (in einer eigenen Funktion) i und j (und value) als Parameter übergeben.
ub60
LINUS19 - Mo 01.01.18 16:14
Ich habe die Blocküberprüfung nochmal verändert:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
| int n =i-(i%3); //Blocküberprüfung
int m = j-(j%3);
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
if (Matrix[a + n][b + m] == value)
return false;
}
} |
Das Sudoku verändert sich wieder nicht. Dann habe ich den Debugger verwendet und das ganze Schrittweise ausgeführt und habe mir die Variablen anzeigen lassen, bis sich der erste Wert verändert hat : [[1, 0, 3, 0, 0, 0, 0, 0, 0] ( vorher { [0,0,3,0,0,0,0,0,0]}ich habe ein anderes Sudoku eingegeben, als beim ersten Post,nicht das ihr euch wundert).
Dann habe ich das Programm bis zum Ende ausgeführt und das ausgegebene Sudoku ist genauso geblieben wie das was ich eingeben habe. Ich kann mir nicht erklären woran das liegt
ub60 - Mo 01.01.18 18:06
Mein Java ist gerade etwas eingerostet, aber ich meinte etwa so:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| public boolean untersucheBlock(int i, int j, int value)
{
gefunden=false;
for (int a = 0; a < 3; a++)
{
for (int b = 0; b < 3; b++)
{
if (Matrix[3*i+a][3*j+b] == value)
gefunden=true;
}
}
return gefunden;
} |
Hiermit kannst du
einen Neunerblock (i von 0-2, j von 0-2) auf das Vorhandensein eines bestimmten Wertes (value) untersuchen.
Ich hoffe zumindest, dass das Prinzip klar wird.
ub60
LINUS19 - Mo 01.01.18 19:26
Das Prinzip ist mir einigermaßen klar, ich hatte bei meinem Post vorher es ja auch ähnlich gemacht wie du, bei deinem Beispiel wird nur eine ArrayindexoutofBounds Exception geworfen. Und brauche ich dafür unbedingt noch eine extra Methode?
LINUS19
LINUS19 - Di 02.01.18 19:56
Ich habe es jetzt hinbekommen. Sowie ich die Blocküberprüfung vorher geschickt habe war es doch richtig, es wird jetzt die die richtige Lösung ausgegeben ich hatte mich wohl nur bei der Eingabe vom Sudoku vertippt.
Und ich habe ewig irgendwo anders nach einem Fehler gesucht...
GuaAck - So 07.01.18 00:02
Hallo Linus19,
ich wollte Deinen Code nachvollziehen und mal laufen lassen. (Ich habe mal einen eigenen Löser nach einem ganz anderen Algorithnus gemacht.) Leider habe ich dabei aber den Überblick über die verschiedenen Versionen verloren. Wäre sdhön, Du würdest den jetzt anscheindend korrekt laufenden Code noch einmal vollständig posten.
Gruß
GuaAck
LINUS19 - So 07.01.18 00:50
Hallo GuaAck,
Hier ist der der Code:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
| import java.util.Scanner;
public class SudokuSolver { // Löst Sudokus von der Kommandozeile
static boolean solve(int i, int j, int Matrix[][]) {
if (i == 9 && j == 8)
return true; // rechtes unteres Feld erreicht,abbruch
if (i == 9) { // Eine Zeile weiter nach unten
i = 0;
j++;
}
if (Matrix[i][j] != 0) { // Nur Felder mit 0 sollen verändert werden
return solve(i + 1, j, Matrix); // -> gehe einen Schritt weiter
}
for (int value = 1; value <= 9; value++) { // Alle Zahlen von 1-9 werde getestet
if (check(i, j, value, Matrix) == true) { // Gehe auf nächstes freies Feld
Matrix[i][j] = value; // setze den Wert
if (solve(i + 1, j, Matrix) == true)
return true;
}
}
Matrix[i][j] = 0; // Feld wird auf Null gesetzt(backtrack)
return false;
}
static boolean check(int i, int j, int value, int Matrix[][]) {
for (int k = 0; k < 9; k++) { // Zahl in Reihe doppelt
if (value == Matrix[i][k])
return false;
}
for (int k = 0; k < 9; k++) { // Zahl in Spalte doppelt
if (value == Matrix[k][j])
return false;
}
int n = i - (i % 3); // Blocküberprüfung
int m = j - (j % 3);
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
if (Matrix[a + n][b + m] == value)
return false;
}
}
return true; // Zahl ist richtig
}
public static void print(int Matrix[][]) { // Sudoku Ausgabe
System.out.println("Lösung:");
System.out.println();
int x;
int y;
for (x = 0; x < Matrix.length; x++) {
if (x % 3 == 0)
System.out.println("---------------------");
for (y = 0; y < Matrix.length; y++) {
if (y % 3 == 0)
System.out.print("|");
System.out.print(Matrix[x][y] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int Matrix[][] = // Sudoku was gelöst wird direkt übergeben
new int[][] {{ 0,5,0,0,0,0,0,0,0},
{ 4,0,0,0,8,0,0,0,3},
{ 0,0,0,0,2,5,0,0,0},
{ 0,0,0,0,0,0,6,0,0},
{ 0,1,0,0,0,2,0,0,0},
{ 5,0,0,6,0,9,0,0,4},
{ 0,0,0,2,0,0,7,3,0},
{ 0,0,9,0,0,6,0,2,0},
{ 7,2,8,0,0,0,0,1,0}};
solve(0,0,Matrix);
// Oder über die Konsole eingeben
int Matrix[][] = new int[9][9];
Scanner sc = new Scanner(System.in); // Scanner zur Eingabe von Konsole
System.out.println("Gib die Zahlen so ein:123456789, wenn das Feld leer ist -> 0 und 9 Zeilen 9 Spalten");
for (int m = 0; m < 9; m++) {
String eingabe = sc.nextLine();
for (int n = 0; n < 9; n++) {
Matrix[m][n] = eingabe.charAt(n) - '0'; // charAt() gibt Zeichencode zurück -'0' umwadlung in lesbar
}
}
final long timeStart = System.currentTimeMillis(); // Zeitmessung
solve(0, 0, Matrix);
if (solve(0, 0, Matrix) == true) // wenn Sudoku lösbar ->
print(Matrix); // wird es ausgegeben
else
System.out.println("Keine Lösung");
final long timeEnd = System.currentTimeMillis();
System.out.println("Lösungszeit: " + (timeEnd - timeStart) + " Millisek.");
}
} |
Welches Lösungsverfahren hast du den verwendet?
Gruß
LINUS19
GuaAck - So 07.01.18 19:56
Hallo Linus19,
ich hatte vor ein paar Jahren meine Lösung an die Logik angelenht, die ein Mensch auch macht, habe also Kriterien untersucht wie
- Ist für ein feld nur eine einzige Zahl erlaubt?
- Ist das Feld die einzige Möglichkeit in einer Zeile, ein bestimmte Zahl unterzubringen?
- usw.
Leider ist bei diesem Verfahren nicht sicher, dass man die Lösung findet. Ich habe 20 Beipiele, bei einem davon wird die Lösung nicht gefunden. Bei diesem Beispiel wird mit Deinem Algorithmus die Function Solve fast 2 Mio. mal aufgerufen, das ist deutlich mehr als bei allen anderen meiner Beispiele.
Gruß
GuaAck
Delphi-Laie - Mo 08.01.18 00:04
Wie man so etwas löst, ist mir seit Jahren klar. Nur hatte ich nie echte Muße und Antrieb, das umzusetzen.
Also, man geht das gesamte Feld - egal, bei welcher Zelle man beginnt - einmal durch. Für jede Zelle prüft man, wieviele Zahlen (oder irgendein anderes Symbol*) infragekommen. Ist nur eine(s) möglich, hat man den nächsten Lösungs(fort)schritt, und der nächste, das gesamte Feld durchschreitende Zyklus kann beginnen. Gelangt man jedoch ohne einen solchen Fortschritt wieder zur Ausgangszelle, ist man mit seinem Latein erstmal am Ende. Und jetzt kommt der zweite Teil:
| GuaAck hat folgendes geschrieben : |
| Leider ist bei diesem Verfahren nicht sicher, dass man die Lösung findet. |
Eben. Ist es nicht mehr so determiniert zu lösen, wie zuvor beschrieben, hilft nur noch - möglichst syxstematisches - Probieren, weshalb bei den Wettkämpfen auch Bleistifte verwandt werden. Dazu gibt es auf dem Computer die mächtige Möglichkeit der Rekursion, die sog. Backtracking ermöglicht. Damit kommt man noch viel weiter.
In einem Spektrum-Sonderheft (Mathematische Unterhaltungen, Nr. weiß ich jetzt nicht) gibt es ein ganzes Kapitel zu Sudokus. Dort ist eines mit nur 17 belegten Zellen enthalten, das dennoch eindeutig lösbar ist, allerdings mit systematischem Probieren.
*
"Für Freunde der Zahlenlogik", wenn ich einen solchen Blödsinn schon lese. Erstmal gibt es keine "Zahlenlogik", zweitens spielen nur die (verschiedenen) Symbole eine Rolle, es könnten also genausogut auch Buchstaben oder sonstwas sein, und drittens vergrault man sich per se schon viele potentielle Rätsler mit einer solchen Ankündigung, weil die meisten Mathematik nicht ausstehen können. Diese (fehlerhafte!) "Anpreisung" ist die größte, widersinnigste Abwerbung, die mir bis dato unterkam.
GuaAck - Mo 08.01.18 01:16
Hallo Delphi-Laie,
stimmt, das war im Jahrgang 2012 des Spektrum. Die Aufgabe ist im Anhang. Genau diese Aufgabe kann mein Programm nicht lösen. Und diese Aufgabe braucht auch mit dem Proggramm von Linus die mit Abstand größte Anzahl von Solve-Aufrufen.
Als ich das Programm gemacht habe, da ging es mir nicht um Brute-Force. Ich wollte wissen, ob meine Lösungsmethode immer zum Erfolg führt. Wenn ich eine Aufgabe nicht lösen kann, dann kann das daran liegen, dass ich eine Kombination einfach nicht sehe, oder daran, dass meine Lösungsmethode bei der Aufgabe nicht zum Ziel führt. Bei der angeführten Aufgane aus dem Spektrum 2012 kam ich mit logischen Schließen nicht weiter und musste probieren. Mein Programm bestätigte, dass ich nichts übersehne habe.
Viele Grüße
GueAck
LINUS19 - Di 09.01.18 16:15
Dieses Sudoku,was ich gemacht habe braucht sogar 6.967.860 Aufrufe.
000040000
180037000
500010000
700054000
000000080
000000090
000970000
200000000
009300000
---------------------
|9 2 6 |5 4 8 |1 3 7
|1 8 4 |2 3 7 |5 6 9
|5 3 7 |6 1 9 |8 4 2
---------------------
|7 9 2 |8 5 4 |6 1 3
|3 1 5 |7 9 6 |2 8 4
|4 6 8 |1 2 3 |7 9 5
---------------------
|6 4 1 |9 7 2 |3 5 8
|2 5 3 |4 8 1 |9 7 6
|8 7 9 |3 6 5 |4 2 1
Lösungszeit: 556 Millisek.
6967860
Fiete - Di 09.01.18 16:46
Moin GuaAck,
das Beispiel habe ich ich mit meinem Programm getestet, es ist nicht eindeutig lösbar!
Bei 8000 Lösungen hab ich es abgebrochen.
SimpleSudoku zeigt dies ebenfalls an.
Ich schätze mal, Dein Programm erwartet eine eindeutige Lösung, was ja auch richtig ist.
Gruß Fiete
LINUS19 - Di 09.01.18 16:53
Das kann aber eigentlich nicht sein,weil das Sudoku 17 Zahlen hat und damit eindeutig lösbar sein müsste.
Fiete - Di 09.01.18 17:27
Meine Lösung
Horst_H - Di 09.01.18 20:04
Hallo,
da bin ich froh, dass Grishnaks Solver auch 9734 Lösungen findet,
Gruß Horst
Delphi-Laie - Di 09.01.18 22:27
| LINUS19 hat folgendes geschrieben : |
| Das kann aber eigentlich nicht sein,weil das Sudoku 17 Zahlen hat und damit eindeutig lösbar sein müsste. |
Hängt das wirklich nur von der Anzahl der vorgegebenen Zahlen (oder anderweitigen Symbole) ab? Oder vielmehr auch davon, wie diese placiert sind (was ich vermute)?
LINUS19 - Di 09.01.18 22:34
Stimmt du hast recht, hier ein Zitat das ich gefunden habe:
"Damit weiß man nun also, dass es keine eindeutig lösbaren Sudokus mit 16 oder weniger vorgegebenen Zahlen gibt. Doch schon wartet die nächste große Frage auf die Mathematiker: Wie viele eindeutig lösbare Sudokus mit 17 vorgegebenen Zahlen gibt es nun tatsächlich? "
Dann muss ich wohl meinen Sudoku Löser so erweitern das er auch mehrere Lösungen findet.
LINUS19 - Di 09.01.18 22:45
Was mich nur wundert ist das dieses Sudoku vom Spektrum eindeutig lösbar sein soll, hast du jedenfalls geschrieben und es jetzt anscheinend knapp 10000 Lösungen gibt.
Delphi-Laie - Mi 10.01.18 00:58
| LINUS19 hat folgendes geschrieben : |
| Was mich nur wundert ist das dieses Sudoku vom Spektrum eindeutig lösbar sein soll, hast du jedenfalls geschrieben und es jetzt anscheinend knapp 10000 Lösungen gibt. |
"Eindeutig lösbar" war wohl unglücklich ausgedrückt. Es kann auch "nur" überhaupt lösbar sein, dann ggf. sogar mehrfach. Daß es Sudokus gibt, die zwar lösbar sind, das aber nicht eindeutig, also mehr als eine Lösung haben, war mir bis dato unbekannt, könnte aber tatsächlich so sein, deshalb mein Formulierungsmangel. Ich krame deswegen aber nicht das Spektrumheft wieder hervor, so sehr interessiert es mich nicht.
Delphi-Laie - Mi 10.01.18 21:42
| LINUS19 hat folgendes geschrieben : |
| Was mich nur wundert ist das dieses Sudoku vom Spektrum eindeutig lösbar sein soll, hast du jedenfalls geschrieben und es jetzt anscheinend knapp 10000 Lösungen gibt. |
Ich muß das noch einmal aufwärmen.
Also, die eindeutige Lösbarkeit ist ja gerade ein Merkmal der Sudokus, denn in ein leeres oder nur unzureichend gefülltes Sudoku lassen sich alle mögliche Lösungen eintragen, doch so etwas zu finden, ist nach meinem Wissen nimmer das Ziel. Sudokus haben so gesehen als Lösungsmenge nur eine Einermenge, aber keine Lösungsmenge i.S.v. mehreren (natürlich endlich vielen) Lösungen.
Soweit ich mich entsinne, war das Sudoku, das ich erwähnte, eben doch eindeutig lösbar, d.h., es hat nur eine Lösung. Je mehr Startzahlen man wegläßt, umso mehr Lösung(en) gibt es tendenziell, irgendwann wächst die Anzahl der Lösungen an und wird größer als 1. 17 Vorgabesymbole sind, so gesehen, wahrscheinlich wirklich die äußerste Schmerzgrenze.
LINUS19 - Mi 10.01.18 23:44
Ich komme jetzt auch auf 9734 Lösungen. Mein Programm hat dafür 34sec. gebraucht.
LG
LINUS19
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!