Hallo,
ich muss ein Programm schreiben, dass ein Sudoku via Backtracking lösen. Soweit verstehe ich das Prinzip, nur funktioniert meine Lösung nicht und ich weiß nicht, woran das liegt:
zunächst habe ich (wie es die Aufgabe verlangt) eine Funktion implementiert, die für eine Stelle mit Zeile y und Spalte x in einem Sudoku die möglichen Zahlen ermittelt und diese in einem Array zurück gibt (muss so sein).
Anschließend die eigentlich Funktion, die prüft, ob das Sudoku lösbar ist oder nicht. Die Funktion isSolvable ruft die Funktion isSolvableHelper auf (das war auch schon so in der Aufgabe)
Ich hoffe ihr könnt mir weiterhelfen
Lg
ich muss ein Programm schreiben, dass ein Sudoku via Backtracking lösen. Soweit verstehe ich das Prinzip, nur funktioniert meine Lösung nicht und ich weiß nicht, woran das liegt:
zunächst habe ich (wie es die Aufgabe verlangt) eine Funktion implementiert, die für eine Stelle mit Zeile y und Spalte x in einem Sudoku die möglichen Zahlen ermittelt und diese in einem Array zurück gibt (muss so sein).
Java:
public static int[] possibleNumbers(int sudoku[][], int x, int y) {
int[] hilfsArray = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; //hilfsArray wird mit den moeglichen Zahlen 1-9 vorbelegt
int zaehler = 0; //eine Zahelvariable wird angelegt
//Zeile pruefen
for (int i=0; i<9; i++) { //die Zeile wird abgesucht
if ( sudoku[y][i] > 0 ) { //Zahl gefunden
for (int k=0; k<9; k++) { //hilfsArray absuchen
if ( sudoku[y][i] == hilfsArray[k] ) { //falls die Zahl in hilfsArray vorhanden ist, wird diese auf 0 gesetzt und somit aus dem hilfsArray gestrichen
hilfsArray[k] = 0;
}
}
}
}
//Spalte pruefen //selbe Vorgehensweise wie beim Zeilen pruefen
for (int i=0; i<9; i++) {
if ( sudoku[i][x] > 0 ) {
for (int k=0; k<9; k++) {
if ( sudoku[i][x] == hilfsArray[k] ) {
hilfsArray[k] = 0;
}
}
}
}
//Box pruefen
int startZ = (y/3)*3; //linke obere Ecke der Box finden
int startS = (y/3)*3;
for (int i=startZ; i<startZ+3; i=i+2) { //Box absuchen
for (int j=startS; j<startS+3; j=j+2) {
if ( sudoku[i][j] > 0 ) { //Zahl gefunden
for (int k=0; k<9; k++) { //hilfsArray absuchen
if ( sudoku[i][j] == hilfsArray[k] ) { //falls Zahl vorhanden, Zahl aus hilfsArray löschen
hilfsArray[k] = 0;
}
}
}
}
}
for (int i=0; i<9; i++) { //jetzt wird geprueft, wie viel gueltige Zahlen im Hilfsarray vorhanden sind
if ( hilfsArray[i] > 0 ) {
zaehler++;
}
}
int[] possibleNumbers = new int[zaehler]; //das Array, das spaeter ausgegeben werden soll wird initialisiert
int index = 0; //Zaehlvariable fuer den Index
for (int i=0; i<9; i++) { //gueltige Zahlen aus dem hilfsArray in possibleNumbers kopieren
if ( hilfsArray[i] > 0 ) {
possibleNumbers[index] = hilfsArray[i];
index++;
}
}
return possibleNumbers; //possibleNumbers zurueck geben
}Anschließend die eigentlich Funktion, die prüft, ob das Sudoku lösbar ist oder nicht. Die Funktion isSolvable ruft die Funktion isSolvableHelper auf (das war auch schon so in der Aufgabe)
Java:
// returns true if given sudoku is solvable
public static boolean isSolvableHelper(int sudoku[][], int x, int y) {
if ( y != 8 && x != 8 ) { //Abbruchbedingung fuer die Rekursion
if ( x >= 8 ) { //falls Zeilenende erreicht ist, springe in naechste Zeile und setze Spalte wieder auf 0
y++;
x = 0;
}
if ( sudoku[y][x] > 0 ) { //falls die Stelle y, x schon belegt ist => rekursiver Aufruf, wobei um eine Position nach rechts gerueckt wird
isSolvableHelper(sudoku, x+1, y);
}
int[] possibleNumbers = possibleNumbers(sudoku, x, y); //wenn die Stell unbesetzt ist, werden zunaechst die moeglichen Zahlen ermittelt, die eingesetzt werden koennen
if ( possibleNumbers.length != 0) { //prueft, ob ueberhaupt Zahlen eingesetzt werden koennen
for (int i=0; i<possibleNumbers.length; i++) { //Schleife ueber moegliche Zahlen
sudoku[y][x] = possibleNumbers[i]; //erst beste Zahl wird in das Sudoku eingesetzt
isSolvableHelper(sudoku, x+1, y); //Funktion ruft sich selber auf, wobei wieder eine Position nach rechts gerueckt wird
}
}
else return false; //keine Zahl kann eingesetzt werden => es wird false zurueck gegeben
}
int belegt = 0; //Zaehlvariable
for (int i=0; i<9; i++) { //Sudoku wird abgesucht
for (int j=0; j<9; j++) {
if ( sudoku[i][j] > 0 ) { //belegte Felder werden mitgezaehlt
belegt++;
}
}
}
if ( belegt == 81 ) { //falls alle Felder belegt sind wird true zurueck gegeben
return true;
}
return false;
}
// returns true if given sudoku is solvable
public static boolean isSolvable(int sudoku[][]) {
return isSolvableHelper(sudoku, 0, 0);
}Ich hoffe ihr könnt mir weiterhelfen
Lg
