# Sudoku lösen mit Backtracking



## Dr.Solace (19. Nov 2011)

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).

```
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)

```
// 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


----------



## nrg (19. Nov 2011)

ohne jetzt alles angeschaut zu haben, brauchst du imho noch eine Member solved o.ä. und musst nach dem rekursiven Aufruf den Schritt immer wieder rückgängig machen (falls 
	
	
	
	





```
!solved
```
)

kuck mal hier

edit: wenn die Zahl bereits gesetzt ist, rufst du zwar gleich wieder rekursiv auf aber probierst danach trotzdem noch alle möglichkeiten. da müsste ein else hin. Außerdem kann es durchaus sein, dass es mal keine Möglichkeiten gibt. Da solltest du nicht sofort false zurückliefern, sondern eben "backtracken".


----------



## emailundlos (19. Nov 2011)

Zumglück ist der verlinkte Quellcode nicht von mir ^^

Es gibt für die Aufgabe eigentlich zwei Herangehensweisen:
du könntest dir überlegen, wie durch das Sudoku beim Einsetzen der Zahlen durchgegangen werden soll und welche Zahlen jeweils zum Einfügen vorhanden sind, weiterhin, wie geprüft wird, ob ein Sudoku richtig/vollständig ausgefüllt ist.
Dann können rekursive Aufrufe vermieden werden, wenn aus bereits eingefügt Zahlen ersichtlich is, welche als nächstes drankommen, oder sich diese gemerkt werden.

Das kurze kompilierbare Beispiel ist aber für mich undurchsichtig, wegen der gewählten Funktionsbezeichnungen.


----------



## Dr.Solace (19. Nov 2011)

Also erst mal danke für die schnellen Antworten. Damit mein Code noch klarer wird, hier mal der "Rohling", wie wir ihn bekommen haben. Logischerweise bin ich gefragt wo "TODO" steht. 

```
public class Sudoku {
	public static final int UNSET = 0;

	public static int[] possibleNumbers(int sudoku[][], int x, int y) {
		// TODO: compute all possible numbers for position x/y
		return null;
	}

	// returns true if given sudoku is solvable
	public static boolean isSolvableHelper(int sudoku[][], int x, int y) {
		// TODO: is given sudoku solvable?
		// sudoku should be filled from upper left to lower right via recursion
		return false; 
	}

	// returns true if given sudoku is solvable
	public static boolean isSolvable(int sudoku[][]) {
		return isSolvableHelper(sudoku, 0, 0);
	}

	public static void printSudoku(int sudoku[][]) {
		for (int i = 0; i < 9; i++) {
			if (i == 3 || i == 6) {
				System.out.println("-----------");
			}
			for (int j = 0; j < 9; j++) {
				if (j == 3 || j == 6) {
					System.out.print("| ");
				}
				System.out.print(sudoku[i][j] + " ");
			}
			System.out.println("");
		}
	}

	public static void main(String args[]) {
		// TODO: test your implementation
		int solvable[][] = new int[][] {
					{5,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}
		};
		
		int unsolvable[][] = new int[][] {
					{5,3,0, 0,7,0, 0,0,4},
					{6,0,0, 1,9,5, 0,0,7},
					{0,9,8, 0,0,0, 0,6,2},

					{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}
		};

		int unsolvable2[][] = new int[][] {
					{5,3,4, 0,0,8, 9,1,0},
					{6,7,2, 1,9,5, 3,4,8},
					{1,9,8, 3,6,0, 5,0,7},

					{8,5,9, 6,0,1, 4,0,3},
					{4,2,6, 8,5,3, 7,9,1},
					{7,1,3, 9,2,4, 8,5,6},

					{9,6,1, 5,3,7, 2,8,4},
					{2,8,7, 4,1,9, 6,3,5},
					{3,4,5, 2,8,6, 1,7,9}
		};
		
		printSudoku(solvable);
		System.out.println(isSolvable(solvable) + " (true)\n");
		
		printSudoku(unsolvable);
		System.out.println(isSolvable(unsolvable) + " (false)");

		printSudoku(unsolvable2);
		System.out.println(isSolvable(unsolvable2) + " (false)");
	}
}
```
Das Prinzip der Rekursion verstehe ich schon, Nur kann ich das irgendwie nicht in Code umsetzen. Eigentlich müsste es ja so gehen:
- Durchlaufe das Feld Sudoku, beginnend links oben bei 0,0
- wenn das Feld besetzt ist (>0) rücke ein Feld nach vorne
- wenn das Feld unbesetzt ist ermittle mögliche Zahlen (possibleNumbers) und setzte die erst beste 
diese Schritte werden solange durchgeführt, bis es zu einem Feld keine Lösungen mehr gibt.
- springe Feld zurück und versuche andere Zahl (wenn alle Zahlen ausprobiert wurden, dann muss man  
  noch ein Feld zurück springen) usw.
Hab ich das soweit richtig verstanden?


----------



## emailundlos (19. Nov 2011)

Sobald irgendwas unstimmig is, letzte Wahl rückgängig machen, Alternative wählen oder sogar letzte Wahl der vorherigen Wahlebene rückgängig machen.

Und bedarf es unbedingt rekursiver Aufrufe? Deine Vorgabe legt dies nahe.


----------



## Dr.Solace (20. Nov 2011)

ja man muss Rekursionen verwenden


----------



## emailundlos (20. Nov 2011)

Wir haben das Thema an der uni nur ganz kurz besprochen und ich kann mich nicht mehr daran erinnern, ob Rekursion unbedingt notwendig is.


----------



## Dr.Solace (20. Nov 2011)

ja wir müssens halt mit Rekursion lösen! Hier noch mal die Vorgehensweise wie man es zu machen hat:
Backtracking (z.B. nötig für das Lösen von Sudoku):
1) Teillösung auswählen und setzen
2) rekursiv absteigen (≙ Problem mit zuvor gesetzter Teillösung lösen)
3) Bei Rückkehr der rekursiv aufgerufenen Funktion: Teillösung wieder entfernen/löschen und ...
• ... wenn das Problem noch nicht gelöst ist und weitere Teillösungen möglich sind: neue Teillösung setzen und erneut rekursiv absteigen
• ... wenn das Problem gelöst ist oder wenn keine weiteren Teillösungen mehr existieren: zurückkehren!

meine Implementierung in Java Code wäre folgende:
1.)

```
if ( sudoku[y][x] == 0 ) {										
			int[] possibleNumbers = possibleNumbers(sudoku, x, y);
			for (int i=0; i<possibleNumbers.length; i++) {
				sudoku[y][x] = possibleNumbers[i];						//1.) Teilloesung setzen
				isSolvableHelper(sudoku, x+1, y);						//2.) rekursiv absteigen
				sudoku[y][x] = 0;										//4.) zuvor gesetzten Eintrag rueckgaengig machen (= auf Null setzen)
																		//    for-Schleife setzt neue Zahl 
			}
			return false;												//3.) keine Loesung gefunden => Abbruch der Rekursion (=eine Stufe zurueck gehen)
		}
```

stimmt das soweit?


----------



## Dr.Solace (20. Nov 2011)

kann mir wirklich niemand weiterhelfen? warum brauche ich eine boolsche Variable? Meine Methode ist gibt ja einen boolschen Wert zurück und ist keine void Funktion ...


----------



## emailundlos (20. Nov 2011)

Ich versuchs mal:

x,y is bekannt.
setzte insgesamt 10 mögliche ziffern bei x,y ein.
is bei einem einsetzen die lösung richtig und vollständig -> lösung gefunden,
sonst, wenn falsch -> schritt zurück,
wenn richtig -> x,y modifizieren.


```
fun(int x) {
 int b = get(x);
 for (int i = 0; i < 10; i++) {
  insert(i, x);
  if (valid()) {
   if (complete()) {
    // ->
   } else {
    fun(x + 1);
   }
  }
 }
 insert(b);
}
```

Mich beschleicht aber das Gefühl, etwas falsch gemacht zu haben. ^^


----------



## tpqme4925 (20. Nov 2011)

Stell dir vor, ich sitz grad an der gleichen Aufgabe:

Mein Problem:

Ich bekomme am Ende ein Sudoku raus, in dem alle felder ausgefüllt sind, und es scheint auch die regeln beim sudoku zu befolgen, aber mein returnwert ist trotzdem False!

Das liegt daran, dass er, wenn das sudoku fertig ausgefüllt ist, trotzdem wieder zurückspringt, an eine stelle, an der er noch andere mögliche zahlen für ein bestimmtes feld hatte. und dann fängt er dort wieder an, und irgendwann klappt es dann eben wieder nicht. (er hatte die richtige zahl ja bereits verwendet, geht aber trotzdem wieder rekursiv einen schritt zurück, um alle verbliebenen möglichen zahlen für ein feld einzusetzen)

wie treibe ich ihm das aus? gibts da nen trick dass er nicht mehr zurückspringt wenn ich eine true bedingung rausbekomme?


----------



## emailundlos (20. Nov 2011)

Mit return kann eine Methode vorzeitig verlassen werden. Das bevorzugen aber viele "echte" Progger nicht, sondern die machen dann da ne zusätzliche Variable rein, die vor jedem Schleifendurchlauf geprüft wird.


----------



## timbeau (21. Nov 2011)

Einfach bei einer gefundenen Lösung, das Programm beenden 

Oder du setzt wie schon beschrieben eine globale boolsche Variable ein und prüfts vor jeder Rekursion ob diese Variable schon auf true gesetzt wurde.


----------



## langhaar! (21. Nov 2011)

Globale Variable ist möglich. Schöner ist es allerdings, mit dem Rückgabewert der Rekursion zu arbeiten.


----------



## timbeau (21. Nov 2011)

Aber schneller. Wenn ich vor jeder Rekursion diese Variable prüfe, muss ich nicht in jeden Zweig hinabsteigen. Der wird ja bei einem Sudoku relativ lang, wenn alle möglichen Kombinationen ausprobiert werden.


----------



## langhaar! (21. Nov 2011)

timbeau hat gesagt.:


> Wenn ich vor jeder Rekursion diese Variable prüfe, muss ich nicht in jeden Zweig hinabsteigen.



Das gilt auch für die Lösung ohne globale Variable.
Hier mal im Vergleich ein kleines rekursives Programm mit und ohne globale Variable zur Gültiogkeitsprüfung.


```
package de.guskoeln.products.inventory;

public class Test {

	boolean solvedGlob = false;
	
	public boolean rekTest1(int i) {
		
		System.out.println(i);
		
		boolean solved = i >= 10;
		if (!solved) {
			solved = rekTest1(++i);
		}
		
		return solved;
	}
	
	public void rekTest2(int i) {
		
		System.out.println(i);
		
		solvedGlob = i >= 10;
		if (!solvedGlob) {
			 rekTest2(++i);
		}
	}
	
	public static void main(String[] args) {
		
		Test test = new Test();
		System.out.println(test.rekTest1(0));
		test.rekTest2(0);
		
	}
}
```


----------



## emailundlos (21. Nov 2011)

Also, wie gesagt, eine Methode Kann verlassen werden, durch ein return, durch die Prüfung einer Variable, die die Schleife abbricht, oder auch das Setzen der Zählervariable auf einen bestimmten Wert.
Oder es gibt auch noch weiter Möglichkeiten?


----------



## nrg (21. Nov 2011)

der boolean war ja auch auf den backtrack bezogen, der natürlich nur gemacht werden soll, wenn das Sudoku ungelöst ist. wenn es nur eine isSolveable Methode wird, kann man das natürlich genauso mit einem return machen. will man sich die Lösung allerdings merken, kann man entweder das Sudoku immer der Rekursion übergeben und bei einer Lösung dieses direkt ausgeben (Vorteil: man bekommt alle Lösungen) oder man macht sich eben einen boolean.


----------



## langhaar! (21. Nov 2011)

emailundlos hat gesagt.:


> Also, wie gesagt, eine Methode Kann verlassen werden, durch ein return, durch die Prüfung einer Variable, die die Schleife abbricht, oder auch das Setzen der Zählervariable auf einen bestimmten Wert.
> Oder es gibt auch noch weiter Möglichkeiten?



In diesem Fall geht es weniger darum, dass eine Methode beendet wird, als dass die Rekursion so aufgebaut wird, dass sie nach einer ermittelten Lösung keine weitere Verarbeitung durchführt. Dann stellt sich die Frage nach dem Beenden einer Methode gar nicht. Ist eher ein Symptom dafür, dass der Algorithmus bzw. die Abarbeitung noch nicht ganz stimmig ist.

Möglichkeiten um eine Methode vor Codeende zu beenden fallen mir zwei ein: return, Exception werfen.
Wobei natürlich Exceptions als Programmsteuerung ein Verbrechen sind :autsch:


----------



## emailundlos (22. Nov 2011)

Geht das auch mit dynamischer Programmierung?


----------



## langhaar! (23. Nov 2011)

wiki hat gesagt.:
			
		

> Dynamische Programmierung kann dann erfolgreich eingesetzt werden, wenn das Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht, und eine optimale Lösung des Problems sich aus optimalen Lösungen der Teilprobleme zusammensetzt



Kann man ein Soduko in Teilprobleme unterteilen, die sich optimal lösen lassen?
Wenn ich richtig verstanden habe, was ein Soduko ist, nicht.


----------

