Sudoku rekursiv lösen

[Gast]

Hi, hatte folgenden Aufgabe:

"Einfach gesagt, lässt sich ein Sudoku folgendermaßen lösen:

- finde das erste freie Feld
- setze die Zahlen 1-9 ein und versuche bei jeder das restliche Sudoku zu lösen
- ist eine Lösung gefunden gib sie aus
- ansonsten sag, dass es nicht möglich ist, das Sudoku zu lösen"

Das Sudoku wird in nem 9x9 Array übergeben.
Meine Methode dazu sieht bisher so aus:
------------------------------------------------------------------------

int[][] loese (int[][] feld){
		int x=0,y=0;
		while (feld[x][y]!=0){     //hier soll das erste leere Feld gefunden werden
			if (x==8 && y==8) return feld;      //Abbruchbedingung: ganzes Feld geloest
			if (x!=8) x++; else {x=0; y++;}   //zu naechstem Feld springen
		}
		for (int a=1; a<=10; a++){  //Zahlen von 1-9 versuchen einzusetzen
			if (a==10) {feld[x][y]=0; return feld;} //zweite Abbruchbedingung: wenn 1-9 nicht geht, Feld freim.
			feld[x][y]=a;
			if (Sudoku.SudokuTest(feld)){ //wenn Zahl zulässig, versuche restliche Felder zu lösen
				feld=loese(feld);
			}
		}
		return feld; //eigentlich unnötig, wird aber für Syntax benötigt
	}

------------------------------------------------------------------------

dürfte alles richtig sein (die Methode SudokuTest funktioniert nachweislich einwandfrei). Ich habe schließlich in ner extra Klasse die Methode mit nem Testsudoku aufgerufen, aber genau dieses wird auch wieder zurückgegeben, obwohl es lösbar ist... Ich glaube das Problem steckt bei "feld= loese(feld);" da ich ja bei arrays nur die referenzen übergebe, könnte mir das Probleme machen oder? Wäre nett, wenn ihr mir helfen könntet

 

[Marco13]

Beim ersten Draufschauen fehlt da Am anfang sowas wie
if (fertig()) return feld;
oder so. Hobbit_Im_Blutrausch hat auch mal einen solchen Löser geschrieben (Forensuche).

 

[Gast]

das wäre ja dann die erste abbruchbedingung, also wenn er kein leeres Feld findet, wird feld returned

 

[Marco13]

Ja, aber irgendwie mußt du unterscheiden, ob gelöst wurde oder nicht. So geht er immer durch die for-Schleife, und landet am Ende bei 10 - und dann löscht er der Reihe nach die zuletzt gesetzten Felder. Eine Möglichkeit wäre vielleicht sowas

boolean loese (int[][] feld)
{
      int x=0,y=0;
      while (feld[x][y]!=0){     //hier soll das erste leere Feld gefunden werden
         if (x==8 && y==8) return true;      //Abbruchbedingung: ganzes Feld geloest
         if (x!=8) x++; else {x=0; y++;}   //zu naechstem Feld springen
      }
      for (int a=1; a<10; a++){  //Zahlen von 1-9 versuchen einzusetzen
         feld[x][y]=a;
         if (Sudoku.SudokuTest(feld)){ //wenn Zahl zulässig, versuche restliche Felder zu lösen
            boolean solved = loese(feld);
            if (solved) return true;
         }
         feld[x][y]=0;
      }
      return false;
   }

 

[Gast]

aber wenn die methode ein boolean zurückbekommt, wird ja im endeffekt nur ausgesagt, ob das Sudoku nun lösbar war oder nicht. Ich brauche doch aber das gelöste Sudoku und das existiert ja nur für die Laufzeit in deiner Version und wird nirgendwo gesichert oder?

 

[mahe]

Na, das Feld wird in der Methode verändert. Da es sich nur um eine Referenz handelt, bleiben diese Änderungen erhalten.


[edit]
Ich hab das auch mal machen müssen und hab das so gelöst gehabt:

	static boolean solveSudoku(int[][] field, int i) {
		if (i == 81)
			return true;
		
		int x1 = (i%9);
		int y1 = (i/9);

		if(isValidValue(field[x1][y1])) {

			return solveSudoku(field, i+1);

		} else {
			int nr = 0;
			
			while(++nr < 10) {
				field[x1][y1] = nr;
				if (checkSudoku(field) && solveSudoku(field, i+1)) {
					return true;
				}
			}
			field[x1][y1] = 0;
			return false;
		}
	}

	static boolean checkSudoku(int[][] field) {

		for(int i = 0; i < 9; ++i) {

			boolean[] c1 = new boolean[10];
			boolean[] c2 = new boolean[10];
			boolean[] c3 = new boolean[10];

			for(int j = 0; j < 9; ++j) {
				if (isValidValue(field[i][j])) {
					if(c1[field[i][j]])
						return false;
					c1[field[i][j]] = true;
				}
				if (isValidValue(field[j][i])) {
					if(c2[field[j][i]])
						return false;
					c2[field[j][i]] = true;
				}
			}
			
			int x1 = (i%3)*3;
			int y1 = (i/3)*3;
			
			for(int x = 0; x < 3; ++x)
			for(int y = 0; y < 3; ++y) {

				if (isValidValue(field[x+x1][y+y1])) {
					if (c3[field[x+x1][y+y1]])
						return false;
					c3[field[x+x1][y+y1]] = true;
				}
			}
		}
		return true;
	}

	static boolean isValidValue(int nr) {
		return (nr > 0 && nr < 10);
	}

Bereits ausgefüllte (Angabe) werden einfach übergangen. Ansonsten immer passende Zahl suchen -> Methodenaufruf machen. So lange bis es irgendwann passt.

Also im Grunde das selbe wie Deins.

Achja, wichtig ist, dass die Kontroll-Methode ungültige Werte (<0 und >9) ignoriert.

Ich hoffe, dass Dir das weiterhilft

 

[The_S]

Hobbit_Im_Blutrausch hat auch mal einen solchen Löser geschrieben (Forensuche).

http://www.java-blog-buch.de/c-sudoku-solver/

 

[Gast]

also ich habe deinen ersten Tipp jetzt gut einbauen können, jetzt hat das Programm auch einmal schon funktioniert, allerdings funktioniert es nicht immer - manchmal werden letztendlich nur einzelne Zahlen eingesetzt (was eig nicht passieren dürfte...) hier der Code:

int[][] loese (int[][] feld){
		int x=0,y=0;
		if (komplett(feld) && Sudoku.SudokuTest(feld)) return feld; //Abbruchbedingung: ganzes Feld geloest
		while (feld[x][y]!=0){ //hier soll das erste leere Feld gefunden werden
			if (x!=8) x++; else {x=0; y++;} //zu naechstem Feld springen
		}
		for (int a=1; a<=9; a++){  //Zahlen von 1-9 versuchen einzusetzen
			feld[x][y]=a;
			if (Sudoku.SudokuTest(feld)){ //wenn Zahl zulässig, versuche restliche Felder zu lösen
				feld=loese(feld);
				if (komplett(feld) && Sudoku.SudokuTest(feld)) return feld; //Abbruchbedingung: ganzes Feld geloest
			} else 
			if (a==9){feld[x][y]=0; return feld;} //zweite Abbruchbedingung: wenn 1-9 nicht geht, Feld freimachen
		}
		return feld; //eigentlich unnötig, wird aber für Syntax benötigt
	}

 

[Marco13]

Hübsch und effizient ist das jetzt zwar nicht, aber ...
manchmal werden letztendlich nur einzelne Zahlen eingesetzt...
"Manchmal" verhalten sich Computer aber deterministisch....

 

[Gast]

ah ok...hab mein problem erkannt, ich darf wirklich nicht das array returnen...mit deiner boolean-variante hat es geklappt ...mich hat nur gewundert, dass wenn ich im hauptprogramm ein array habe, dieses ja nicht verändert wird (klar, dass es in der Methode verändert wird, aber dort "bleibt" es ja auch und wird nicht ausgegeben)..aber es scheint ja zu funktionieren, da mecker ich mal nicht vielen dank für die hilfe

 

[Marco13]

Man übergibt der Methode eine Referenz auf den Array. D.h. der Array, der in der aufrufenden Methode angelegt wird, und der Array IN der Methode sind ein und derSELBE Array.

void foo()
{
    int a[] = new int[1];
    change(a);
    System.out.println(a[0]); // Gibt 123 aus
}
void change(int a[])
{
    a[0] = 123;
}