Guten Abend zusammen
Nachdem ich eine ehwigkeit an diesem Algorithmus gesessen habe, den ich für Informatik schreiben soll, bringe ich ihn einfach nicht das zu tun, was ich will.
Um es kurz zusammen zu fassen.
Ich soll unter Vorgabe der Main Methode, sowie der Methodennamen aller weiteren Methoden, sowie einer vorgefertigten Eingabemethode ein Java-Programm schreiben, das über eine Textxkonsole, von einem Unix-basiertem Uni-rechner aus, ein Sudoku-Rätzel entgegen nimmt.
(0-Stellen sind dabei die leeren Felder).
Das Programm soll via Backtracking die Lösung ermitteln und dann einfach wieder ausgeben.
Ich habe einige Zeit daran gearbeited ein Program zu schreiben, das in der Theorie auch genau das können soll.
Jetzt hab ich bereits mehrere Stunden über den Textzeilen gebrüted, bin aber immernoch dahinter gekommen, wo mein Fehler liegt, denn zwar kompiliert der Rechner den Code, bringt aber keine Lösung zustande, sondern gibt stets aus, das das Sudoku garnicht gelöst werden kann.
Hier ist der Algorithmus:
[Java]
import AlgoTools.IO;
/**
* SudokuSolver, der die Loesung eines Sudokus mittels Backtracking ermittelt.
*
* @author Nicolas Neubauer (nineubau@uos.de)
* @author Sebastian Buescher (sbuesche@uos.de)
* @author Jana Lehnfeld (jlehnfel@uos.de)
* @author Nils Haldenwang (nhaldenw@uos.de)
*
*/
public class Sudoku {
/**
* rekursive Methode, die das naechste freie Kaestchen im Sudoku-Feld sucht
* und dort alle erlaubten Zahlen einsetzt und sich dann selbst aufruft.
*
* @param sudoku
* Feld welches , gefuellt werden soll
* @param spalte
* Spaltennumer im Array
* @param zeile
* Zeilennummer im Array
* @return ob Loesung gefunden oder nicht
*/
private static boolean fuelleFeld(int[][] sudoku, int spalte, int zeile) {
if(spalte == 9) {
zeile++;
spalte = 0;
if (zeile > 8) return true;
}
if (sudoku[spalte][zeile] != 0){
return fuelleFeld(sudoku,spalte+1,zeile);
}
for (int zahl = 1; zahl <= 9; zahl++) {
if (gueltigeZahl(sudoku, zahl, spalte, zeile)){
sudoku[spalte][zeile] = zahl;
if (fuelleFeld(sudoku, spalte+1, zeile)) {
return true;
}
}
}
sudoku[spalte][zeile] = 0;
return false;
}
/**
* Testet, ob zahl noch in Zeile, Spalte und Kaestchen reinpasst
*
* @param sudoku
* 2D Array in dem getestet wird
* @param zahl
* zu testende Zahl
* @param spalte
* Spaltennumer im Array
* @param zei8e
* Zeilennummer im Array
* @return true, falls Zahl unterzubringen ist
* @param zei8e
* Zeilennummer im Array
* @return true, falls Zahl unterzubringen ist
*/
private static boolean gueltigeZahl(int[][] sudoku, int zahl, int spalte,
int zeile) {
for(int i = 0; i < 9; i++) {
if (zahl == sudoku[zeile]) return false;
if (zahl == sudoku[spalte]) return false;
}
int boxSpalte = (spalte/3)*3;
int boxZeile =(spalte/3)*3;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++) {
if (zahl == sudoku[boxSpalte+i][boxZeile+j]) return false;
}
}
return true;
}
/**
* Gibt das Sudoku-Feld ordentlich formatiert aus
*
* @param field
* Feld das ausgegeben werden soll
*/
private static void druckeSudoku(int[][] field) {
for (int yPos = 0; yPos < 9; yPos++) {
if (yPos != 0 && yPos % 3 == 0)
IO.println("------+-------+------ ");
for (int xPos = 0; xPos < 9; xPos++) {
if (xPos != 0 && xPos % 3 == 0)
IO.print("| ");
IO.print(field[yPos][xPos] + " ");
}
IO.println();
}
}
public static void main(String[] argv) {
// Sudoku-Feld als
// zweidimensionales Array
int[][] sudoku;
sudoku = new int[9][];
IO.println("Bitte geben Sie die Zeilen des zu loesenden Sudokus ein");
int[] eingabe;
// Einlesen des Sudokus
for (int i = 1; i < 10; i++) {
do {
eingabe = IO.readInts("Zeile " + i + ": ");
} while (eingabe.length != 9);
sudoku[i - 1] = eingabe;
}
// Feld einmal ausgeben
druckeSudoku(sudoku);
//Loesung ermitteln, oben links anfangen
if(fuelleFeld(sudoku, 0, 0)){
IO.println("Die Loesung: ");
druckeSudoku(sudoku);
} else { IO.println("Error");
}
}
}
[/code]
Noch ein paar Anmerkungen:
1. Die IO.print oder IO.read(); befehle basieren auf den algotool meiner Universität und dienen für ein und Ausgabe auf einer Konsole.
2. Die Main, drucken und eingabemethode sind vorgegeben, folglich sind diese also korrekt, der Fehler müsste in den anderen Methoden, warscheinlich fuelleFeld, liegen.
3. Kurze Erklärung zu den Methoden:
fuelle Feld, soll von oben links, bis unten rechts durchgehen und das Sudoku verfollständigen, wobei es von Feld zu Feld, nach einem "Trial and Error" Prinzip, die Zahlen einfach bei jedem Feld durchgeht.
gueltigeZahl hat wiederum die Aufgabe, die Zahl, die von der fuelleFeld-Methode eingebaut wurde, auf ihre richtigkeit zu überprüfen.
Ich hoffe ihr könnt mir helfen
mit freundlichen grüßen
Vangrand
PS: Hoffe es ist der richtige Bereich in diesem Forum
Nachdem ich eine ehwigkeit an diesem Algorithmus gesessen habe, den ich für Informatik schreiben soll, bringe ich ihn einfach nicht das zu tun, was ich will.
Um es kurz zusammen zu fassen.
Ich soll unter Vorgabe der Main Methode, sowie der Methodennamen aller weiteren Methoden, sowie einer vorgefertigten Eingabemethode ein Java-Programm schreiben, das über eine Textxkonsole, von einem Unix-basiertem Uni-rechner aus, ein Sudoku-Rätzel entgegen nimmt.
(0-Stellen sind dabei die leeren Felder).
Das Programm soll via Backtracking die Lösung ermitteln und dann einfach wieder ausgeben.
Ich habe einige Zeit daran gearbeited ein Program zu schreiben, das in der Theorie auch genau das können soll.
Jetzt hab ich bereits mehrere Stunden über den Textzeilen gebrüted, bin aber immernoch dahinter gekommen, wo mein Fehler liegt, denn zwar kompiliert der Rechner den Code, bringt aber keine Lösung zustande, sondern gibt stets aus, das das Sudoku garnicht gelöst werden kann.
Hier ist der Algorithmus:
[Java]
import AlgoTools.IO;
/**
* SudokuSolver, der die Loesung eines Sudokus mittels Backtracking ermittelt.
*
* @author Nicolas Neubauer (nineubau@uos.de)
* @author Sebastian Buescher (sbuesche@uos.de)
* @author Jana Lehnfeld (jlehnfel@uos.de)
* @author Nils Haldenwang (nhaldenw@uos.de)
*
*/
public class Sudoku {
/**
* rekursive Methode, die das naechste freie Kaestchen im Sudoku-Feld sucht
* und dort alle erlaubten Zahlen einsetzt und sich dann selbst aufruft.
*
* @param sudoku
* Feld welches , gefuellt werden soll
* @param spalte
* Spaltennumer im Array
* @param zeile
* Zeilennummer im Array
* @return ob Loesung gefunden oder nicht
*/
private static boolean fuelleFeld(int[][] sudoku, int spalte, int zeile) {
if(spalte == 9) {
zeile++;
spalte = 0;
if (zeile > 8) return true;
}
if (sudoku[spalte][zeile] != 0){
return fuelleFeld(sudoku,spalte+1,zeile);
}
for (int zahl = 1; zahl <= 9; zahl++) {
if (gueltigeZahl(sudoku, zahl, spalte, zeile)){
sudoku[spalte][zeile] = zahl;
if (fuelleFeld(sudoku, spalte+1, zeile)) {
return true;
}
}
}
sudoku[spalte][zeile] = 0;
return false;
}
/**
* Testet, ob zahl noch in Zeile, Spalte und Kaestchen reinpasst
*
* @param sudoku
* 2D Array in dem getestet wird
* @param zahl
* zu testende Zahl
* @param spalte
* Spaltennumer im Array
* @param zei8e
* Zeilennummer im Array
* @return true, falls Zahl unterzubringen ist
* @param zei8e
* Zeilennummer im Array
* @return true, falls Zahl unterzubringen ist
*/
private static boolean gueltigeZahl(int[][] sudoku, int zahl, int spalte,
int zeile) {
for(int i = 0; i < 9; i++) {
if (zahl == sudoku[zeile]) return false;
if (zahl == sudoku[spalte]) return false;
}
int boxSpalte = (spalte/3)*3;
int boxZeile =(spalte/3)*3;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++) {
if (zahl == sudoku[boxSpalte+i][boxZeile+j]) return false;
}
}
return true;
}
/**
* Gibt das Sudoku-Feld ordentlich formatiert aus
*
* @param field
* Feld das ausgegeben werden soll
*/
private static void druckeSudoku(int[][] field) {
for (int yPos = 0; yPos < 9; yPos++) {
if (yPos != 0 && yPos % 3 == 0)
IO.println("------+-------+------ ");
for (int xPos = 0; xPos < 9; xPos++) {
if (xPos != 0 && xPos % 3 == 0)
IO.print("| ");
IO.print(field[yPos][xPos] + " ");
}
IO.println();
}
}
public static void main(String[] argv) {
// Sudoku-Feld als
// zweidimensionales Array
int[][] sudoku;
sudoku = new int[9][];
IO.println("Bitte geben Sie die Zeilen des zu loesenden Sudokus ein");
int[] eingabe;
// Einlesen des Sudokus
for (int i = 1; i < 10; i++) {
do {
eingabe = IO.readInts("Zeile " + i + ": ");
} while (eingabe.length != 9);
sudoku[i - 1] = eingabe;
}
// Feld einmal ausgeben
druckeSudoku(sudoku);
//Loesung ermitteln, oben links anfangen
if(fuelleFeld(sudoku, 0, 0)){
IO.println("Die Loesung: ");
druckeSudoku(sudoku);
} else { IO.println("Error");
}
}
}
[/code]
Noch ein paar Anmerkungen:
1. Die IO.print oder IO.read(); befehle basieren auf den algotool meiner Universität und dienen für ein und Ausgabe auf einer Konsole.
2. Die Main, drucken und eingabemethode sind vorgegeben, folglich sind diese also korrekt, der Fehler müsste in den anderen Methoden, warscheinlich fuelleFeld, liegen.
3. Kurze Erklärung zu den Methoden:
fuelle Feld, soll von oben links, bis unten rechts durchgehen und das Sudoku verfollständigen, wobei es von Feld zu Feld, nach einem "Trial and Error" Prinzip, die Zahlen einfach bei jedem Feld durchgeht.
gueltigeZahl hat wiederum die Aufgabe, die Zahl, die von der fuelleFeld-Methode eingebaut wurde, auf ihre richtigkeit zu überprüfen.
Ich hoffe ihr könnt mir helfen
mit freundlichen grüßen
Vangrand
PS: Hoffe es ist der richtige Bereich in diesem Forum
