Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Ich habe Guice mit einem Beispielprojekt testen wollen. Viele Hinweise aus diesem Forum sind dabei eingeflossen ... danke
Ich habe nun eine Frage zu meiner Methode [c]solveSudoku()[/c] ... ich bekomme sie nicht rekursiv gelöst ... die Anwendung beendet sich normal, ohne Exception, aber das Sudoku ist nicht gelöst.
wenn das jar hoffentlich Quellcode und eine main-Methode mit fertigen Test-Feld enthält ist das sicher eine schöne kleine Suchaufgabe,
ich habe noch nicht reingeschaut und frage vorher nach: ist das noch aktuell?
morgen dann vielleicht, falls es nicht gar zwischendurch wer anders macht, ob durch mein Erinnerungs-Posting oder Antwort darauf 😉
Ja, ist es. Ich bin am WE nicht untätig gewesen und habe schon mal 2 Dinge raus gefunden: Kann das nächste Feld nicht gelöst werden, muss ich das aktuelle Feld wieder leeren, da sonst falsche Nummern stehen bleiben. Und es ist glaube ich eine gute Idee zuerst abzufragen, ob es das letzte Feld ist und diesen Fall gesondert abzuarbeiten. Dann sieht man eher, ob sich im letzten Feld noch ein weiteres
Code:
solveNextField()
versehentlich eingeschlichen hat ... beim letzten Feld darf das nicht passieren.
Danke für den Hinweis ... super Tutorial ... habe im Netz nach sowas gesucht und bin eher auf unpassende Seiten getroffen. Naja.
zu deinem Tipp: Dein Vorschlag geht einen etwas anderen Weg, als ich es mir das gedacht habe. Ich wollte im Feld 9/9 das erfolgreich gelöste Soduku erkennen und durch alle rekursiven Aufrufe den Erfolg zurück geben (durch den Rückgabewert). Sollte es nämlich an irgendeiner Stelle keine Lösung geben, wird ein false zurück gegeben, und das Feld davor versucht dann die restlichen Nummern.
Das aktuelle Feld soll somit anhand der eigenen Versuche eine Nummer zu setzen und des Erfolgs / Misserfolg des nächsten Feldes einen Erfolg erkennen. Somit weiß der erste Aufruf der Methode, ob das komplette Sudoku gelöst wurde, oder nicht.
das mit Guice ist doch nicht dein Ernst, oder?
für so ein Miniprogramm so kompliziert auf Libraries setzen?
auch Interface/ Impl mag ja an sich ne tolle Sache sein, hier für ein Miniprogramm ist das aber unnötig störend,
ich habe deinen Programmcode etwas zusammengefasst unten gepostet,
falls immer noch aktuell und ich da weitermachen soll, bitte vorher noch bisschen aktiv werden:
- ich habe alles guicige herausgenommen, wenn ein Field erzeugt werden soll passiert das jetzt 'normal' mit new Field(),
nicht so komisch newInstance von wer weißt wo,
allerdings läuft jetzt nicht mehr so viel, vielleicht meine Schuld beim Kürzen,
in der main-Methode von SpielfeldImpl steht nicht viel mehr als das Befüllen eines Feldes, wo wird denn solveSudoku() usw. aufgerufen?
selbst der Anfang läuft bei mir nicht besonders, egal ob ich die Füll-Schleife aus der main-Methode verwende
oder SpielConsole.generateFields() (doppelter Code?), immer kommt es zur NullPointerException,
das Hauptarray fields in Spielfeld ist null, wann soll das wer setzen?
- bisher wird mit Random gefüllt, die Wahl des Sodukos ist von 1x1 bis 9x9 variabel,
hast du nicht ein konkretes Beispiel mit ganz konkreter Problemsituation?
mit new Random(zahl als seed) kann man übrigens einen reproduzierbaren Zufallsverlauf erschaffen,
ansonsten vielleicht auch manuell ein Feld befüllen, so viele Werte sind es am Anfang ja nicht, oder?
edit: Code mit weiteren Änderungen von Folgeposts:
Java:
public class Test
{
public static void main(String... args)
throws NumberNotAllowedException
{
SpielConsole c = new SpielConsole();
c.generateFields(30);
c.showSpielfeld();
c.solveSudoku();
c.showSpielfeld();
}
}
class Field
{
int number;
public int getNumber()
{
return number;
}
public void setNumber(int number)
throws NumberNotAllowedException
{
if (number < 1 || number > 9) throw new NumberNotAllowedException("Nur Zahlen von 1-9 erlaubt (Wert:" + number + ")");
this.number = number;
}
}
class Spielfeld
{
Field[][] fields = new Field[9][9];
public Field getField(int row, int col)
throws NumberNotAllowedException
{
if (row < 1 || row > 9) throw new NumberNotAllowedException("row ist Ausserhalb Bereich von 1-9 (Wert:" + row + ")");
if (col < 1 || col > 9) throw new NumberNotAllowedException("column ist Ausserhalb Bereich von 1-9 (Wert:" + col + ")");
return fields[row - 1][col - 1];
}
public Field[][] getSquare(int rowSqare, int colSquare)
throws NumberNotAllowedException
{
if (rowSqare < 1 || rowSqare > 3)
throw new NumberNotAllowedException("row ist Ausserhalb Bereich von 1-3 (Wert:" + rowSqare + ")");
if (colSquare < 1 || colSquare > 3)
throw new NumberNotAllowedException("column ist Ausserhalb Bereich von 1-3 (Wert:" + colSquare + ")");
Field[][] square = new Field[3][3];
for (int i = 0; i < square.length; i++)
{
int rowFromField = rowSqare * 3 - 3 + i;
for (int j = 0; j < square[i].length; j++)
{
int colFromField = colSquare * 3 - 3 + j;
square[i][j] = fields[rowFromField][colFromField];
}
}
return square;
}
public void setField(int number, int row, int col)
throws NumberNotAllowedException
{
if (row < 1 || row > 9) throw new NumberNotAllowedException("row ist Ausserhalb Bereich von 1-9 (Wert:" + row + ")");
if (col < 1 || col > 9) throw new NumberNotAllowedException("column ist Ausserhalb Bereich von 1-9 (Wert:" + col + ")");
if (number < 1 || number > 9)
throw new NumberNotAllowedException("number ist Ausserhalb Bereich von 1-9 (Wert:" + number + ")");
if (fields[row - 1][col - 1] != null)
throw new NumberNotAllowedException("Feld bereits belegt (" + col + "/" + row + ") Wert:"
+ fields[row - 1][col - 1].getNumber());
Field field = new Field();
field.setNumber(number);
fields[row - 1][col - 1] = field;
}
public boolean checkNumberAllowed(int number, int row, int col)
throws NumberNotAllowedException
{
if (row < 1 || row > 9) throw new NumberNotAllowedException("row ist Ausserhalb Bereich von 1-9 (Wert:" + row + ")");
if (col < 1 || col > 9) throw new NumberNotAllowedException("column ist Ausserhalb Bereich von 1-9 (Wert:" + col + ")");
if (number < 1 || number > 9)
throw new NumberNotAllowedException("number ist Ausserhalb Bereich von 1-9 (Wert:" + number + ")");
if (fields[row - 1][col - 1] != null)
throw new NumberNotAllowedException("Feld bereits belegt (" + col + "/" + row + ") Wert:"
+ fields[row - 1][col - 1].getNumber());
// Horizontale und vertikale prüfen
for (int i = 0; i < 9; i++)
{
// horizontale (Zeile) prüfen
if (fields[row - 1][i] != null) if (fields[row - 1][i].getNumber() == number) return false;
// vertikale (Spalte) prüfen
if (fields[i][col - 1] != null) if (fields[i][col - 1].getNumber() == number) return false;
}
// Das Quadrat prüfen
Field[][] square = this.getSquare((row - 1) / 3 + 1, (col - 1) / 3 + 1);
for (int i = 0; i < square.length; i++)
for (int j = 0; j < square[i].length; j++)
if (square[i][j] != null) if (square[i][j].getNumber() == number) return false;
// Alles Klar, ist erlaubt
return true;
}
}
class SpielConsole
{
Spielfeld spielfeld = new Spielfeld();
public void showSquare(int rowsquare, int colsquare)
throws NumberNotAllowedException
{
Field[][] square = spielfeld.getSquare(rowsquare, colsquare);
for (int i = 0; i < square.length; i++)
{
System.out.println();
for (int j = 0; j < square[i].length; j++)
System.out.print(square[i][j].getNumber() + "\t");
}
}
public Spielfeld getSpielfeld()
{
return spielfeld;
}
public void showSpielfeld()
{
try
{
for (int i = 1; i <= 9; i++)
{
System.out.println();
if (i % 3 == 1)
System.out.println("-------------------------");
System.out.print("|");
for (int j = 1; j <= 9; j++)
{
String trenner;
if (j % 3 == 0)
trenner = " |";
else
trenner = "";
Field field = spielfeld.getField(i, j);
if (field == null)
System.out.print(" " + trenner);
else
System.out.print(" " + field.getNumber() + trenner);
}
}
System.out.println();
System.out.println("-------------------------");
}
catch (NumberNotAllowedException e)
{
e.printStackTrace();
}
}
public Field getField(int row, int col)
throws NumberNotAllowedException
{
return spielfeld.getField(row, col);
}
public void generateFields(int count)
throws NumberNotAllowedException
{
if (count > (9 * 9)) throw new NumberNotAllowedException("count muss zwischen 1 und 81 liegen: count=" + count);
Random rand = new Random();
for (int i = 0; i < count; i++)
{
boolean success = false;
int row = 0;
int col = 0;
int number = 0;
while (!success)
{
row = rand.nextInt(8) + 1;
col = rand.nextInt(8) + 1;
number = rand.nextInt(8) + 1;
try
{
success = spielfeld.checkNumberAllowed(number, row, col);
}
catch (NumberNotAllowedException e)
{
success = false;
}
}
spielfeld.setField(number, row, col);
}
}
public void solveSudoku()
{
try
{
if (!solveNextField(1, 1)) System.out.println("konnte Spielfeld nicht lösen.");
}
catch (NumberNotAllowedException e)
{
e.printStackTrace();
}
}
private boolean solveNextField(int row, int col)
throws NumberNotAllowedException
{
System.out.println("solve row: " + row + "; col: " + col);
if (spielfeld.getField(row, col) != null)
{
if (row == 9 && col == 9) return true;
int newcol = 0;
int newrow = 0;
if (col == 9)
{
newcol = 1;
newrow = row + 1;
}
else
{
newcol = col + 1;
newrow = row;
}
return solveNextField(newcol, newrow);
}
for (int i = 1; i <= 9; i++)
{
System.out.println("versuche: " + i);
boolean goOn;
try
{
goOn = spielfeld.checkNumberAllowed(i, row, col);
if (goOn)
System.out.println("Nummer erlaubt: " + goOn);
else
System.out.println("Nummer NICHT erlaubt (try)");
}
catch (Exception e)
{
goOn = false;
System.out.println("Nummer NICHT erlaubt (catch)");
}
if (goOn)
{
System.out.println("weiterschalten, da Nummer erlaubt ist");
if (row == 9 && col == 9)
{
spielfeld.setField(i, row, col);
return true;
}
spielfeld.setField(i, row, col);
int newcol = 0;
int newrow = 0;
if (col == 9)
{
newcol = 1;
newrow = row + 1;
}
else
{
newcol = col + 1;
newrow = row;
}
return solveNextField(newcol, newrow);
}
}
return false;
}
}
class NumberNotAllowedException
extends Exception
{
/**
*
*/
private static final long serialVersionUID = 3186762137729838344L;
public NumberNotAllowedException()
{
}
public NumberNotAllowedException(String arg0)
{
super(arg0);
}
public NumberNotAllowedException(Throwable arg0)
{
super(arg0);
}
public NumberNotAllowedException(String arg0, Throwable arg1)
{
super(arg0, arg1);
}
}
Und ob das mein Ernst ist! Das ist doch der ganze Sinn der Übung. Ich habe eine Programmieraufgabe gesucht um mich Guice zu nähern. Hier im Forum habe ich bereits viele Hinweise bekommen und irgendwie muss man doch die ganzen Hinweise zu Guice in der Praxis mal umsetzen. Von daher wäre es nicht ganz so schlimm, wenn die Methode nicht funktioniert ... den Erfolg habe ich bereits dadurch, dass ich dieses Beispiel bis jetzt gut mit Guice umgesetzt habe. Aber mich wurmt es, dass ich den rekursiven Aufruf nicht hinbekommen habe.
Siehe auch http://www.java-forum.org/allgemeine-java-themen/122290-guice-singleton.html
in der main-Methode von SpielfeldImpl steht nicht viel mehr als das Befüllen eines Feldes, wo wird denn solveSudoku() usw. aufgerufen?
selbst der Anfang läuft bei mir nicht besonders, egal ob ich die Füll-Schleife aus der main-Methode verwende
oder SpielConsole.generateFields() (doppelter Code?), immer kommt es zur NullPointerException,
das Hauptarray fields in Spielfeld ist null, wann soll das wer setzen?
bisher wird mit Random gefüllt, die Wahl des Sodukos ist von 1x1 bis 9x9 variabel,
hast du nicht ein konkretes Beispiel mit ganz konkreter Problemsituation?
Nein, das Sudoku ist fix auf 9x9. Es können mit generateFields per Zufallsgenerator eine vorgegebene Anzahl von Felder befüllt werden. Die restlichen Felder sollen per Backtracking gelöst werden.
Das Problem tritt bei jedem zufällig generierten Sudoku auf (keine Exceptions, keine Lösung).
da habe ich zuviel gelöscht, stimmt, wobei ich mich noch weiter frage, wie da automatisch ein 9x9er Array erzeugt wird?
egal, wenn es bei dir geht, mag es sein,
ich bekomme nun (mit optimierter Feld-Ausgabe 😉 ) ein Log wie
Code:
-------------------------
| | 2 | 5 4 |
| 1 3 | 6 | |
| 5 8 2 | 3 | 6 |
-------------------------
| 1 | 2 8 7 | 3 |
| 3 | 4 | 6 |
| 4 | 3 | 2 5 |
-------------------------
| 8 6 | 4 | 7 2 |
| | 5 | 4 |
| | | |
-------------------------
solve row: 1; col: 1
versuche: 1
Nummer NICHT erlaubt (try)
versuche: 2
Nummer NICHT erlaubt (try)
versuche: 3
Nummer NICHT erlaubt (try)
versuche: 4
Nummer NICHT erlaubt (try)
versuche: 5
Nummer NICHT erlaubt (try)
versuche: 6
Nummer erlaubt: true
weiterschalten, da Nummer erlaubt ist
solve row: 2; col: 1
versuche: 1
Nummer NICHT erlaubt (try)
versuche: 2
Nummer NICHT erlaubt (try)
versuche: 3
Nummer NICHT erlaubt (try)
versuche: 4
Nummer erlaubt: true
weiterschalten, da Nummer erlaubt ist
solve row: 2; col: 2
solve row: 3; col: 2
solve row: 3; col: 3
solve row: 4; col: 3
....
wie soll ich mir sicher sein ob die Ausgangssituation überhaupt lösbar ist?
kannst du nicht ein bestimmtes Feld vorgeben, die Schritte, die zur Lösung nötig sind usw.
oder anders gefragt: woran exakt erkennst du selber dass dein Programm einen Fehler macht,
kann nicht einfach das Random-Sudoku unlösbar sein? oder muss es immer lösbar sein?
oder anders gefragt: woran exakt erkennst du selber dass dein Programm einen Fehler macht, kann nicht einfach das Random-Sudoku unlösbar sein? oder muss es immer lösbar sein?
Hm, das ist ein interessanter Einwand. An sowas habe ich nun gar nicht gedacht. Ich bin/war der Meinung, dass man jedes sauber vorbefüllte Sudoku lösen kann ... allerdings weiß ich nicht, wie ich darauf komme.
Aber anders gesagt, müsste ein leeres Sudoku (generateFields(0)) auf jeden Fall lösbar sein ... oder? Sobald ich daheim bin, werde ich das noch mal prüfen und ggfs. ein gelöstes Sudoku als Grundlage nehmen und mal 60 Felder löschen ... dass muss dann aber lösbar sein. Ich habe mir auch schon Ideen von euch mitgenommen und werde die Methode heute Abend noch mal angehen. Je nachdem bekommt ihr heute abend eine Lösung, oder weitere Probleme zu hören 😉
Hm, das ist ein interessanter Einwand. An sowas habe ich nun gar nicht gedacht. Ich bin/war der Meinung, dass man jedes sauber vorbefüllte Sudoku lösen kann ... allerdings weiß ich nicht, wie ich darauf komme.
Es ist eigentlich klar, dass dem nicht so ist: Nimm ein Sudoku aus der Zeitung und löse es. Die Lösung ist eindeutig. Wenn du das Ausgangssudoku nimmst und irgendwo eine Zahl hinzufügst, die zwar den Regeln nach "erlaubt" ist, aber nicht mit derjenigen in der korrekten Lösung übereinstimmt, hast du ein unlösbares Sudoku.
Wenn du das Ausgangssudoku nimmst und irgendwo eine Zahl hinzufügst, die zwar den Regeln nach "erlaubt" ist, aber nicht mit derjenigen in der korrekten Lösung übereinstimmt, hast du ein unlösbares Sudoku.
Aber es stimmt schon, dass du nicht auf gut Glück Zahlen ins Sudoku setzen kannst. Da müsstest du dir einen Sudokuersteller basteln. Kannst ja auch vollständige Sudokus erschaffen und da Zahlen rauslöschen.
Edith: Mein 1. Sudoku-Solver, leider QuellCode verloren, da nur schlecht zum nachschauen, aber vielleicht hat ja jmd. einen guten Decompiler 😉
So, habe nun nach euren Tipps eine Lösung.
1. das letzte Feld gesondert behandeln ... dort darf kein weiterer rekursiver Aufruf stattfinden.
2. wenn ein Feld ein false vom nächsten Feld bekommt, dann muss das Feld geleert und die restlichen Nummern geprüft werden
3. bei mehr wie 25 zufällig vorbelegten Feldern wird die Chance deutlich geringer, dass es eine Lösung gibt ... um ein sauberes Sudoku zu generieren würde sich anbieten z.B. 10 Felder vorzugeben, eine Lösung per Backtracking zu finden und dann so viele Felder zu löschen, damit die gewünschte Anzahl übrig bleibt.
so, hier die Methode:
Java:
private boolean solveNextField(int row, int col) throws NumberNotAllowedException {
NextField nextField = new NextField(row, col);
// System.out.println("Versuche row="+row+"; col="+col);
if(row == 9 && col == 9){
// Behandle letztes Feld
if(!spielfeld.fieldEmpty(row, col))
return true;
else{
for(int number = 1; number <= 9; number++){
if(spielfeld.checkNumberAllowed(number, row, col)){
spielfeld.setField(number, row, col);
return true;
}
}
return false;
}
}else{
// Behandle beliebiges Feld
if(!spielfeld.fieldEmpty(row, col)){
// Feld bereits vorbelegt ... nächstes Feld probieren
boolean retVal = solveNextField(nextField.getNewRow(), nextField.getNewCol());
return retVal;
} else{
// jede Nummer durchprobieren
for(int number = 1; number <= 9; number++){
if(spielfeld.checkNumberAllowed(number, row, col)){
// Wenn Nummer gesetzt werden darf, dann Nummer setzen und nächstes Feld probieren
spielfeld.setField(number, row, col);
boolean retVal = solveNextField(nextField.getNewRow(), nextField.getNewCol());
// Wenn nächstes Feld nicht gesetzt werden konnte, dann Feld entfernen und nächste Nummer probieren
// ... sonst true zurück geben
if(retVal == false)
spielfeld.removeField(row, col);
else
return true;
}
}
// Keine Nummer konnte gesetzt werden ... false zurück geben
// System.out.println("Fehlschlag: row="+row+"; col="+col);
return false;
}
}
}
private class NextField{
int newRow = 0;
int newCol = 0;
public int getNewRow() {
return newRow;
}
public int getNewCol() {
return newCol;
}
public NextField(int currentRow, int currentCol){
if(currentCol == 9){
newCol = 1;
newRow = currentRow+1;
} else {
newCol = currentCol+1;
newRow = currentRow;
}
}
}
Also nochmal kurz zu der ganzen Sache mit dem "lösbaren Sudoku". Auch wenn du das Feld ganz befüllst und sagen wir mal nur 12 Zahlen stehen lässt, heißt es nicht, dass es für ein Mensch "lösbar" sein wird. Wenn du ein Sudoku löst, musst du dir (also solltest zumindest, wenn du es richtig löst) 100% sicher sein, dass die Zahl dahin kommt, bevor du die reinschreibst, sonnst gehst du nach dem Prinzip "naja, vielleicht wird es ja passen". Sobald du feststellst, dass in das Feld >1 Zahl passt, sollst du an einer anderen Stelle nach der "sicheren Zahl" suchen. Und jetzt noch kurz ein Beispiel:
123 --- ---
456 --- ---
789 --- 123
--- --- ---
--- --- ---
--- --- ---
--- --- ---
--- --- ---
--- --- ---
Hier hast du auch 12 Zahlen vorgegeben, und auch wenn das generierte Feld zu lösen ist, ist es für den Menschen nicht zu lösen ohne einfach mal Blind welche Zahlen eingeben die passen könnten, und dann hoffen dass es die richtige war. Ich weiß, dass das Beispiel ein wenig überzogen ist, und dass du die Zahlen nicht so stehen lassen würdest, ich wollte es aber so deutlich machen.
Also nochmal: Nur weil es möglich ist, das Feld zu lösen, heißt es nicht, dass es für den Menschen "zu lösen" ist. Es sei dem als Schwierigkeitsgrad "Try Your Luck" oder "Impossible Hard OMG What Is That".
Ja, das ist mir durchaus bewusst. Ich löse gern Sudokus. Es gibt die Easy Variante, wo es immer genau einen Weg zum Ziel gibt. Es gibt aber auch die schwierigeren, wo es doch mal passieren kann, dass man an einer Stelle raten und sich die möglichen Zahlen für ein Feld merken/aufschreiben muss. Erst im späteren Verlauf ist es dann möglich zu entscheiden, welche Zahl es sein muss. Das geht natürlich nur bis zu einer bestimmten Komplexität, weil es dann, wie du schon sagtest für einen Menschen unlösbar ist.
Hm, da fällt mir was auf ... so könnte doch auch ein Computer das Sudoku lösen, oder? Gibt es dafür bereits einen Algorithmus?
Gucke vielleicht in den Codeschnipseln/Projekten nach, da sollte sogar auf der ersten Seite ein Sudoku Spiel sein, das auch das schon gelöste Sudoku anzeigt falls der Benutzer es sehen will. Sofern ich mich noch erinnern kann, hat es ganz gut und vor allem schnell geklappt. Die Sourcen dazu wurden da glaube ich auch veröffentlicht, du könntest aber auch vielleicht den Themenstarter mal um Hilfe bitten, was das lösen angeht.
