Hallo Leute,
ich habe hier im Anhang ein kleines Sudoku in Java (mit JDeveloper von Oracle) vor langem mit jemand anders programmiert. Nun lautet die Aufgabenstellung im Informatiklehrer, ob es auch auf andere Art und Weise lösbar wäre. Wichtig ist, dass das Endergebnis in die gleiche Richtung gehen muss. War da total überfragt, denn dieses habe ich mit Mühe und Not grad mal noch so mit jemand anders zusammenbekommen! Kann mir da einer helfen? Wichtig sind auch die Kommentare, damit ich das nachvollziehen und davon lernen kann
Es ist grad mal eine Seite lang. Müsste für euch Profis ein Klacks sein, aber für mich war es ein Produkt aus Nervenarbeit :wink:
ich habe hier im Anhang ein kleines Sudoku in Java (mit JDeveloper von Oracle) vor langem mit jemand anders programmiert. Nun lautet die Aufgabenstellung im Informatiklehrer, ob es auch auf andere Art und Weise lösbar wäre. Wichtig ist, dass das Endergebnis in die gleiche Richtung gehen muss. War da total überfragt, denn dieses habe ich mit Mühe und Not grad mal noch so mit jemand anders zusammenbekommen! Kann mir da einer helfen? Wichtig sind auch die Kommentare, damit ich das nachvollziehen und davon lernen kann
Es ist grad mal eine Seite lang. Müsste für euch Profis ein Klacks sein, aber für mich war es ein Produkt aus Nervenarbeit :wink:
Code:
package sudoku;
public class Sudoku {
private static int feld[][]={{0,3,0,0,7,0,0,0,0},
{6,0,0,1,9,5,0,0,0},
{0,9,8,0,0,0,0,6,0},
{8,0,0,0,6,0,0,0,3},
{4,0,0,8,0,3,0,0,1},
{7,0,0,0,2,0,0,0,6},
{0,6,0,0,0,0,2,8,0},
{0,0,0,4,1,9,0,0,5},
{0,0,0,0,8,0,0,7,9}};
// Sudokufeld wurde mit Werten intialisiert, 0 = frei
public Sudoku() {
}
public static void main(String[] args) {
//Sudoku sudoku = new Sudoku();
ausgabe();
System.out.println("------------------");
System.out.println("Berechnung beginnt");
System.out.println("------------------");
long startzeit = System.currentTimeMillis();
if(loesen(0,0)) {
// Der Algorithmus hat eine Lösung gefunden und gibt das Ergebnis inklusive der Berechnungszeit
// aus.
long dauer = System.currentTimeMillis() - startzeit;
ausgabe();
System.out.println("------------------");
System.out.println("Gelöst in " + dauer + " ms.");
} else {
// Der Algorithmus kann das Sudokurätsel nicht lösen und gibt eine Meldung inklusive der
// Berchnungszeit aus.
long dauer = System.currentTimeMillis() - startzeit;
System.out.println("Nicht gelöst in " + dauer + " ms.");
}
}
public static void ausgabe() {
for(int y=0;y<9;y++) {
for(int x=0;x<9;x++) {
System.out.print(feld[x][y]);
}
System.out.println();
}
}
public static boolean loesen(int y, int x) {
if(x == 9) {
/* Zeilenende wurde erreicht, nun wird überprüft, ob wir mit dem
/ Algorithmus auch schon in der letzten Zeile sind*/
y++;
// Zeilennummer um eins erhöhen
if(y==9) {
return true;
// Ende des Sudokufeldes wurde erreicht, Position rechts unten
// Also ist wohl eine Lösung gefunden
// Hinweis: Zeile 8 ist die letzte Zeile, da y um eins erhöht wurde,
// kann y nur 9 sein, wenn der Algorithmus bereits in der letzten Zeile war.
}
x=0;
// Algorithmus an die erste Spalte setzen, da wir noch nicht in der letzten Zeile waren
}
if(feld[x][y]>0) {// Vorbelegung gefunden, also wird dieses Feld übersprungen.
return loesen(y,x+1);
// Es wird die gleiche Funktion aufgerufen, aber ein Feld weiter
// Diese Instanz der Funktion bleibt durch den return-Befehl nicht erhalten
}
for(int i=1;i<10;i++) {
if(check(y,x,i) == false) { //Funktion zum Prüfen, ob die Zahl i an dieser Stelle möglich wäre wird aufgerufen
feld[x][y] = i; // Zahl wurde auf keinem relevanten Feld gefunden kann also mit an diese Stelle geschrieben werden
if(loesen(y,x+1)) {
return true;
// mit (if(loesen(y,x+1)) wird die gleiche Methode aufgerufen, allerdings bleibt diese Kopie der
// Methode erhalten, gleichzeitig wird überprüft ob die Methode (und alle ihre Nachfahren)
// true zurückgibt, wenn ja dann ist eine Lösung gefunden und es wird true zurückgegeben
// das hat zur Folge, dass alle Methoden mit true zurückspringen. Die erste Entscheidung für true entsteht
// oben, wo der y wert überprüft wird. Also werden solange Kopien der Funktion erstellt, bis entweder die Schleife
// komplett durchlaufen ist und false zurückgegeben wird oder das Ende des Feldes erreicht wird und
// true zurückgegeben wird. D.h. auch das die Kopie, die zuerst erstellt wurde den Algorithmus mit true beendet
}
}
}
feld[x][y]=0; // Keine der Zahlen 1-9 passt, es wird mit false zurück gesprungen
return false; // D.h. dass alle Kopien der Methode an diese Stelle kommen und die Kopie
// die zuerst erstellt wurde, beendet den algorithmus mit false
}
public static boolean check(int y,int x,int i) {
if(checkRow(y,i)==true) {
return true;
// Ruft die Methode checkRow auf, um zu testen, ob in der Zeile der Wert i
// schon vorhanden ist, wenn checkRow true zurückgibt, wird hier true zurückgegeben und die
// Methode check beendet.
}
if(checkColumn(x,i)==true) {
return true;
// Ruft die Methode checkColumn auf, um zu testen, ob in der Spalte der Wert i
// schon vorhanden ist.Wenn checkColumn true zurückgibt, wird auch hier true zurückgegeben
// und die Methode check beendet
}
if(checkBereich(y,x,i)==true) {
return true;
// Ruft die Methode checkBereich auf, um zu testen,ob in dem Bereich, wo überprüft werden soll
// (gemeint ist das 3x3 Feld) schon vorhanden ist. Wenn checkBereich true zurückgibt, Gibt die
// Methode check auch true zurück.
}
// Wenn das Programm hier angekommen ist, heißt das in der Spalte, in der Zeile und in dem Bereich
// ist noch kein Wert i. Also wird false zurückgegeben (für nicht gefunden )
return false;
}
public static boolean checkRow(int y,int i) {
for(int j=0;j<9;j++) {
if(feld[j][y]== i)
return true; // Wert i wurde in der Zeile gefunden, true wird zurückgegeben und Methode beendet
}
return false; // Schleife ist komplett durchlaufen, nicht gefunden, false wird zurückgegeben und Methode beendet
}
public static boolean checkColumn(int x,int i) {
for(int j=0;j<9;j++) {
if(feld[x][j]==i)
return true; // Wert i wurde in der Spalte gefunden, true wird zurückgegeben und Methode beendet
}
return false; // Wert i wurde nicht gefunden, false wird zurückgegeben und Methode beendet
}
public static boolean checkBereich(int y,int x, int i) {
int yStart = (int)(y/3) * 3;
int xStart = (int)(x/3) * 3;
// Es wird die erste Position ermittelt in dessen Bereich sich der Algorithmus befindet.
// z.B. x=4 -> (int)(4/3)*3 = (int)(1,3333)*3 = 1 * 3 = 3
// z.B. y=1 -> (int)(1/3)*3 = (int)(0,3333)*3 = 0 * 3 = 0
// x=3 ist die erste Position im Bereich mitte
// y=0 ist die erste Position im Bereich oben
// bei (int)(double wert) wird einfach alles, was sich nach dem Komma
// befindet abgeschnitten
for(int y1=yStart;y<yStart+3;y++)
for(int x1=xStart;x1<xStart+3;x1++) {
// Diese beiden Schleifen durchlaufen den bezeichneten Bereich
// z.B. x:3-5 , y:0-3
if(feld[x1][y1]==i) {
return true;
// Wert i wurde in dem Bereich gefunden, es wird true zurückgegeben
// und die Methode checkBereich beendet
}
}
// Wert i wurde nicht gefunden false zurückgegeben und Methode beendet
return false;
}
}
