# Springerproblem



## pilx (12. Dez 2010)

Bin im Moment dabei das Springerproblem zu programmieren. Ich denke, dass der Quelltext eigentlich ganz gut aussieht, leider bekomme ich aber immer nur lauter nullen ausgegeben.

```
package Springer;

import AlgoTools.IO;

public class Springer {
	
	public static int[] moegzeile = {1,-1,1,-1,2,2,-2,-2};
	public static int[] moegspalte = {2,-2,-2,2,-1,1,-1,1};
	
	private static boolean springe(int[][] a, int n, int zeile, int spalte) {
		
		//Rekursionsbremse
		if(n == (a.length)*(a.length)) return true;
		
		for(int i=0; i<8; i++) {
			int z = zeile+moegzeile[i];
			int s = spalte+moegspalte[i];
			if(pruefe(a,z,s)) {
				if(springe(a,n+1,z,s)) {
					return true;
				}
				else return false;
			}
		}
		return false;
	}

	private static boolean pruefe(int[][] a, int zeile, int spalte) {
		
		if(zeile >= a.length || zeile <= 0) return false;
		
		if(spalte >= a[0].length || spalte <= 0) return false;
		
		if(a[zeile][spalte] != 0) return false;
		
		return true;
	}
	
	public static void ausgabe(int[][] a) {
		
		for(int i=0; i < a.length; i++) {
			for(int j=0; j < a[0].length; j++) {
				IO.print(a[i][j],3);
			}
			IO.println();
		}
		
	}
	public static void main(String argv[]) {
		
		int groesse;
		int startZ, startS;
		int[][] brett;
		
		do {
			groesse = IO.readInt("Bitte Kantenlaenge: ");
		}
		while(groesse < 5);
		
		do {
			startZ = IO.readInt("Bitte Zeile: ");
		}
		while(startZ < 0 || startZ > groesse);

		do {
			startS = IO.readInt("Bitte Spalte: ");
		}
		while(startS < 0 || startS > groesse);
		
		brett = new int[groesse][groesse];
		
		springe(brett,1,startZ,startS);
		
		ausgabe(brett);
		
	}
}
```


----------



## pilx (12. Dez 2010)

OK ist natürlich nicht so gut, wenn man vergisst den Wert in das Array zu schreiben.
Jetzt komme ich auch schon etwas weiter aber das Programm macht immer nur zwischen 6 und 10 Schritte...


----------



## Marco13 (12. Dez 2010)

Dass du, wenn der erste Versuch nicht zum Erfolg führt, gleich "aufgibst", und in einem Forum nachfragst, manifestiert sich im Code in der Zeile
else return false;


Nicht vergessen, die Gesetzen Zahlen auch wieder wegzunehmen, wenn keine Lösung gefunden wird.

BTW: [c]zeile <= 0) [/c] (und so) muss <0 sein. 0 ist ja noch OK.


----------



## pilx (12. Dez 2010)

Da muss dann vermutlich eine Backtracking Anweisung rein, richtig?


----------



## Marco13 (12. Dez 2010)

Das Backtracking an sich passiert "automatisch", durch die Rekursion... wenn man *nicht* vorzeitig die Schleife beendet... *zaunpfahl wieder einpack*


----------



## pilx (13. Dez 2010)

Hab's mit einigem Herumprobieren doch schlussendlich noch gelöst.


----------



## Marco13 (13. Dez 2010)

Und wie lange dauert es bei 8x8 ohne Warnsdorf-Heuristik?


----------



## pilx (14. Dez 2010)

Läuft noch 
wie realistisch ist es, dass ich morgen Früh ein Ergebnis habe?


----------



## Marco13 (14. Dez 2010)

Du solltest dir nicht zu viele Hoffnungen machen  Selbst wenn es mit 8x8 nach ein, zwei Tagen fertig _wäre _ (was ich nicht glaube), würde es bei 10x10 schon deutlich länger dauern. Und "deutlich länger" bedeutet bei einem Algorithmus mit exponentieller Laufzeit eben "sehr sehr sehr viel länger". Genaugenommen kann es gut sein, dass schon für die Lösung des 8x8-Brettes ein paar Milliarden Jahre benötigen würde. (Klingt komisch. Is aber so  ).

Die Warnsdorf-Regel ist relativ leicht zu implementieren, und damit sollte er problemlos ein 8x8-Brett innerhalb kürzester Zeit lösen, und selbst deutlich größere Bretter noch in vertretbarer Zeit lösbar sein.


----------



## Sonecc (14. Dez 2010)

Wenn er denn eine wirkliche Lösung findet. 100% sicher ist das ja nicht bei der Warnsdorf Regel.


----------

