# SpringerProblem: Rekursion ist endlos



## G@st (12. Mrz 2012)

Hi, 

ich hab folgendes Problem. Ich baue gerade an einer Klasse, die für mich das bekannte Springerproblem aus der Mathematik lösen soll. Den Code an sich bitte nicht so sehr auf seine Effizienz bemängeln, ich weiß, dass er eine Katastrophe ist. Mir geht es mehr darum, herauszufinden, warum mein Programm niemals aus der Rekursion zurückkehrt xO

[
	
	
	
	





```
package springerproblem;
import java.awt.Point;
import java.util.*;

public class SpringerProblem {
	
	int [][] aktuellesFeld = new int [5][5];
	
	int [][] speicherFeld = new int [5][5];
	
	static int x, y; 
	
	static double zahl = 0; 
	
	int[] initFeld = new int [2];
	
	static boolean check1 = true;
	static boolean check2 = true;
	static boolean check3 = true;
	static boolean check4 = true;
	static boolean check5 = true;
	static boolean check6 = true;
	static boolean check7 = true;
	static boolean check8 = true;
	
	static Stack<Point> stack = new Stack<Point>();
	
	public static void main (String [] args ){
		
		SpringerProblem sp = new SpringerProblem(); 
		
		sp.initialise();
		
		berechne();
		
		
	}

	private static void berechne() {

		zahl++;
		//SpringerProblem intern_sp = new SpringerProblem();
		
		//Pseudocode: Setze aktuelle Werte von x und y auf Stack.length - 1
		x = stack.peek().x;
		y = stack.peek().y;
		
		checkNext();
		
		choseNext();
		
	}

	private void initialise() {

		Scanner sc = new Scanner(System.in); 
		
		System.out.println("Geben sie das Startfeld ein: ");
		System.out.println("Koordinate x: ");
		x = sc.nextInt();
		System.out.println("Koordinate y: ");
		y = sc.nextInt(); 
		Point p = new Point(x,y); 

		stack.add(p);

	}

	// Prüft ob die 8 theoret. mögl. Felder in diesem Durchgang erreichbar sind
	private static void checkNext() {
		
		if (((x+2) > 0 && (x+2) <= 5) && ((y+1) > 0 && (y+1) <= 5)){
			check1 = true;
		}
			else {
				check1 = false; 
		}
		
		if (((x+1) > 0 && (x+1) <= 5) && ((y+2) > 0 && (y+2) <= 5)){
			check2 = true;
			}
			else {
				check2 = false; 
			}
		
		if (((x-1) > 0 && (x-1) <= 5) && ((y+2) > 0 && (y+2) <= 5)){
			check3 = true;
			}
			else {
				check3 = false; 
			}
		
		if (((x-2) > 0 && (x-2) <= 5) && ((y+1) > 0 && (y+1) <= 5)){
			check4 = true;
			}
			else {
				check4 = false; 
			}
		
		if (((x-2) > 0 && (x-2) <= 5) && ((y-1) > 0 && (y-1) <= 5)){
			check5 = true;
			}
			else {
				check5 = false; 
			}
		
		if (((x-1) > 0 && (x-1) <= 5) && ((y-2) > 0 && (y-2) <= 5)){
			check6 = true;
			}
			else {
				check6 = false; 
			}
		
		if (((x+1) > 0 && (x+1) <= 5) && ((y-2) > 0 && (y-2) <= 5)){
			check7 = true;
			}
			else {
				check7 = false; 
			}
		
		if (((x+2) > 0 && (x+2) <= 5) && ((y-1) > 0 && (y-1) <= 5)){
			check8 = true;
			}
			else {
				check8 = false; 
			}
		
	}
	
	private static void choseNext() {
		try {
			System.out.println(x +  " " + y);
		if (check1) {
			System.out.println("Check1");
			stack.add(new Point(x,y));
			
			x = x + 2;
			y = y + 1;
			berechne(); 
		} else if (check2) {
			System.out.println("Check2");
			stack.add(new Point(x,y));
			
			x = x + 1;
			y = y + 2;
			berechne();
		} else if (check3) {
			System.out.println("Check3");
			stack.add(new Point(x,y));
			
			x = x - 1;
			y = y + 2;
			berechne();
		} else if (check4) {
			System.out.println("Check4");
			stack.add(new Point(x,y));
			
			x = x - 2;
			y = y + 1;
			berechne();
		} else if (check5) {
			System.out.println("Check5");
			stack.add(new Point(x,y));
			
			x = x - 2;
			y = y - 1;
			berechne();
		} else if (check6) {
			System.out.println("Check6");
			stack.add(new Point(x,y));
			
			x = x - 1;
			y = y - 2;
			berechne();
		} else if (check7) {
			System.out.println("Check7");
			stack.add(new Point(x,y));
			
			x = x + 1;
			y = y - 2;
			berechne();
		} else if (check8) {
			System.out.println("Check8");
			stack.add(new Point(x,y));
			
			x = x + 2;
			y = y - 1;
			berechne();
		} else {
			stack.pop();
		}
		
		} catch (Exception e){
			e.printStackTrace();
		}
		
		
	}
```

Fällt euch da auf die Schnelle was auf?


----------



## truesoul (12. Mrz 2012)

Hallo,

ich werde jetzt nichts am code bemängeln, obwohl es sicherlich ein paar Sachen gibt 
Naja die Methode berechne() ruft die Methode choseNext() auf die wiederrum berechne() aufruft und nur wenn keiner der check's true ist ( werden auch noch mit true initialisiert ) wird nicht mehr berechne() aufgerufen  

Ganz ehrlich, habe mir jetzt die if Bedingungen nicht angeschaut, dafür fehlt mir die Zeit und der nerv.

*Edit:* 
Im 

```
if(check5) {
   ... 

   x = x - 2;
   y = y - 1;
}
```
und

```
if(check1) {
   ... 

   x = x + 2;
   y = y + 1;
}
```
ist auch schon nicht korrekt. 
Und dein stack.add(new Point(x,y)) ist auch noch falsch platziert.
Weil du dann ja schon in berechne x und y auf 0 setzt. 
Das kann ja nur dazu führen das du eine "Endlosschleife" hast.

Ein Beispiel für eine Rekursion ist: 

```
public static void main ( String[] args ) {
		MeinProgramm meinProgramm = new MeinProgramm();
		meinProgramm.startRekursion(0, 20);
	}
	
	private void startRekursion(int x, int size) {   
        if(x < size){
        	x++;
        	System.out.println(x + " : "+size);
        	startRekursion(x, size);
        }
    }
```


----------



## G@st (12. Mrz 2012)

Klar der Code ist an sich sicherlich ne Performancekatastrophe und an die Richtlinien möchte ich gar nicht erst denken^^

Okay heißt er hängt unten irgendwann fest und kommt nicht mehr raus? Wie kann ich das denn auffangen, stehe gerade auf nem ziemlich störrischen Schlauch 

Danke, dass du dir die if-Bedingungen dann doch noch angesehen hast. Ich verstehe nicht ganz, was an check1 und check5 falsch sein soll. Kannst du das bitte noch einmal erläutern? 

Den stack.add() hab ich jetzt umgesetzt, aber ich glaub, das macht auch nicht viel mehr Sinn oder? Wo kommt er denn eigentlich im Programm hin? 


```
private static void choseNext() {
		try {
		if (check1) {
			System.out.println("Check1");
			
			x = x + 2;
			y = y + 1;
			
			stack.add(new Point(x,y));
			berechne(); 
		} else
```

Danke für die Hilfe, Rekursion liegt mir nicht sonderlich wie man sieht.


----------



## truesoul (12. Mrz 2012)

Naja wenn du in 

```
if (check1){
x = x+2;
y = y+2;
}
```
und in

```
if (check5){
x = x-2;
y = y-2;
}
```
werden die Bedingungen sich abwechselnd "anspringen". Also wird check1, dann check5 dann check1 usw.
Warum? Naja x+2 und dann x-2? Schaue mal dann in checkNext() welche Bedingungen ausgeführt werden. 



> Wie kann ich das denn auffangen?


Naja, sowas macht man mit korrekten if Bedingungen. Würde an deiner Stelle klein Anfangen mit der Rekursion.


> Den stack.add() hab ich jetzt umgesetzt, aber ich glaub, das macht auch nicht viel mehr Sinn oder?


Jep. Wenn du alle stack.add()  so umsetzt, kommt es zu den von mir beschriebenen Verhalten. 
Schau dir erstmal ein paar Beispiele an:
rekursives programmieren beispiele

Mfg


----------



## G@st (13. Mrz 2012)

Stimmt jetzt hab ich es auch gesehen, da war ich grad ein bisschen blind^^
Ich werd mir jetzt mal das gesamte Programm vornehmen und es nochmal gründlich überarbeiten. Wenn der Code dann eine neue Version erreicht hat, die man hier posten kann, melde ich mich nochmal xD

Das checkNext() wird mit Sicherheit dann auch ein bisschen anders aussehen. 

Ja ich weiß, das ist nicht gerade das beste Beispiel um mit Rekursion anzufangen. Die kleineren Rekursionsmethoden, die ich geschrieben habe, sind mir soweit auch klar, nur der hier haut mich vollends aus der Bahn =_=

Der Fehler trat genauso auf, wie du es gesagt hast, daran muss ich auch noch arbeiten.

Danke für deine Hilfe, ich melde mich auf jeden Fall, sobald das Programm langsam bessere Resultate wirft


----------



## G@st (13. Mrz 2012)

Ich habe eine neue Version der Software erstellt. Die beiden Funktionen wurden in einer zusammengefasst und vereinfacht. Die bool'schen Werte sind weggefallen und ich habe den Code von ungenutzten Variablen befreit. Nun läuft er eine ganze Zeit lang auch in die richtige Richtung. Dann verhakt sich das Programm aber auf halber Strecke und beginnt aus den Regeln auszubrechen >.<

Wo ist denn da noch ein Bug versteckt? 


```
package springerproblem;
import java.awt.Point;
import java.util.*;
	
public class KnightProblem{
	
	static int x, y; 
	
	static Stack<Point> stack = new Stack<Point>();
	
	public static void main (String [] args ){
		
		KnightProblem sp = new KnightProblem(); 
		
		sp.initialise();
		
		berechne();
		
	}
	
	private void initialise() {

		Scanner sc = new Scanner(System.in); 
		
		System.out.println("Geben sie das Startfeld ein: ");
		System.out.println("Koordinate x: ");
		x = sc.nextInt();
		System.out.println("Koordinate y: ");
		y = sc.nextInt(); 
		Point p = new Point(x,y); 

		stack.add(p);

	}


	private static void berechne() {

		//x = stack.peek().x;
		//y = stack.peek().y;

		System.out.println(x +  " " + y);
		
		//Früheres checkNext() und choseNext() zusammengeführt
		//stack.contains prüft, ob der Punkt schonmal besucht wurde. 
		if (((x+2) > 0 && (x+2) <= 5) && ((y+1) > 0 && (y+1) <= 5)){

			x = x + 2;
			y = y + 1;
			
			if (stack.contains(new Point(x,y))){

				x = x - 2;
				y = y - 1;
				
			} else {
				
				stack.add(new Point(x,y));
				berechne();
			}
		}
		
		if (((x+1) > 0 && (x+1) <= 5) && ((y+2) > 0 && (y+2) <= 5)){

			x = x + 1;
			y = y + 2;
			
			if (stack.contains(new Point(x,y))){

				x = x - 1;
				y = y - 2;
				
			} else {
				
				stack.add(new Point(x,y));
				berechne();
			}
		}
		
		if (((x-1) > 0 && (x-1) <= 5) && ((y+2) > 0 && (y+2) <= 5)){

			x = x - 1;
			y = y + 2;
			if (stack.contains(new Point(x,y))){

				x = x + 1;
				y = y - 2;
				
			} else {
			
				stack.add(new Point(x,y));
				berechne();
			}
		}
		
		if (((x-2) > 0 && (x-2) <= 5) && ((y+1) > 0 && (y+1) <= 5)){
			
			x = x - 2;
			y = y + 1;
			if (stack.contains(new Point(x,y))){
				x = x + 2;
				y = y - 1;
			} else {
				
				stack.add(new Point(x,y));
				berechne();
			}
		}
		
		if (((x-2) > 0 && (x-2) <= 5) && ((y-1) > 0 && (y-1) <= 5)){
			x = x - 2;
			y = y - 1;
			
			if (stack.contains(new Point(x,y))){
				x = x + 2;
				y = y + 1;
			} else {
				
				stack.add(new Point(x,y));
				berechne();
			}
		}
		
		if (((x-1) > 0 && (x-1) <= 5) && ((y-2) > 0 && (y-2) <= 5)){

			x = x - 1;
			y = y - 2;
			
			if (stack.contains(new Point(x,y))){
				x = x + 1;
				y = y + 2;
			} else {
					
				stack.add(new Point(x,y));
				berechne();
			}
		}
			
		if (((x+1) > 0 && (x+1) <= 5) && ((y-2) > 0 && (y-2) <= 5)){

			x = x + 1;
			y = y - 2;
			
			if (stack.contains(new Point(x,y))){

				x = x - 1;
				y = y + 2;
			} else {
			
				stack.add(new Point(x,y));
				berechne();
			}
		}
		
		if (((x+2) > 0 && (x+2) <= 5) && ((y-1) > 0 && (y-1) <= 5)){
			
			x = x + 2;
			y = y - 1;
			
			if (stack.contains(new Point(x,y))){
				x = x - 2;
				y = y + 1;
			} else {
			
				stack.add(new Point(x,y));
				berechne();
			}
		}
		
		else {
				stack.pop();
		}
		
		
	}
}
```


----------



## truesoul (13. Mrz 2012)

Versuche doch mal ohne statische Variablen, sondern mit übergabeparametern x und y. 
Zudem versuche doch erstmal nur mit zwei Bedingungen zu arbeiten und verwende Stift und Zettel um nachzuvollziehen was dort geschieht. 
Oder Debugge dein Projekt. 

Mfg


----------



## G@st (13. Mrz 2012)

Ich bin jetzt am debuggen hab aber noch keine Auffälligkeiten gehabt. Ist eine umfangreiche Ausgabe, da werd ich eine Weile dran sitzen. 
Ich hab die statischen Variablen verändert und übergebe nun x und y immer pro Methodenaufruf^^ Hat auch eine Veränderung hervorgerufen. Er beginnt jetzt zu rechnen und hört so schnell auch nicht mehr auf. Vorher hatte er einen fehlerhaften Weg ausgegeben und dann aufgehört. 

Ein Fehler ist beim debuggen aufgefallen: 

Er springt gerne mal so, wie es die Regeln eigentlich nicht erlauben: 

Von (2,2) auf (5,5) oder von (1 ,1) auf (1,3) >.< Sieht da jemand was im Code, was das hervorruft?


----------



## langhaar! (13. Mrz 2012)

G@st hat gesagt.:


> Ein Fehler ist beim debuggen aufgefallen:
> 
> Er springt gerne mal so, wie es die Regeln eigentlich nicht erlauben:
> 
> Von (2,2) auf (5,5) oder von (1 ,1) auf (1,3) >.< Sieht da jemand was im Code, was das hervorruft?



Verstehst du unter Debuggen das gleiche wie alle anderen?
Im Debug Modus werden alle Schritte einzeln und somit nachvollziehbar ausgeführt.
Da können keine Variablen plötzlich springen, da du jede Zuweisung siehst.
Ansonsten gib doch mal die Zeile an, in der sich der Variableninhalt wie oben dargestellt verändert.

Ich habe mir deinen Code nur überflogen, aber ich denke, du hast ein grundsätzliches Verständnisproblem mit Rekursion. Wenn du etwas rekursiv aufrufst, benötigst du keinen Stack mehr, auf dem du Daten ablegst. Dies wird implizit von der Rekursion geleistet. Jeder Rekusionsaufruf speichert seine lokalen Variablen. Wird ein Aufruf innerhalb einer Rekursion beendet, werden die Variablen auf den gleichen Wert gesetzt, den sie vor dem Aufruf hatten.

(Das ist auch mein Verdacht für deine springenden Werte)

EDIT

Ok, wenn du mit contains arbeitest, ist dein Stack vermutlich nicht überflüssig. Allerdings ist contains keine Stack-Operation (In Java mag das gehen, da ein Stack von Vector erbt, aber abstrakt gesehen kann ein Stack so etwas nicht und dann sollte man meines Erachtens eine andere Datenstruktur nehmen).


----------



## G@st (13. Mrz 2012)

Ja klar, was sollte Debuggen sonst bedeuten? Die Fehler des Programms treten nicht immer auf, daher hat es gedauert, bis ich eine fehlerhafte Stelle gefunden hatte. 

Mittlerweile hab ich truesoul's Rat zu Herzen genommen und nur mit einem Teil der if-Bedingungen gedebuggt. Dabei ist aufgefallen, dass die Werte x und y offenbar nicht richtig resetet werden, wenn eine Sackgasse erreicht wird. Sie werden dann in der Rekursion eins nach oben geworfen und dort völlig legitim weiter verarbeitet. Dadurch erhält man dann aber Wertänderungen wie (1,1) und (1,3). Der Wert wurde einfach zweimal umgerechnet^^
Wie kann ich das Problem denn lösen? xO


```
import java.awt.Point;
import java.util.*;
	
public class KnightProblem{
	
	int x, y; 
	static int x2, y2;
	
	static Stack<Point> stack = new Stack<Point>();
	
	public static void main (String [] args ){
		
		KnightProblem sp = new KnightProblem(); 
		
		sp.initialise();
		
		
	}
	
	private void initialise() {

		Scanner sc = new Scanner(System.in); 
		
		System.out.println("Geben sie das Startfeld ein: ");
		System.out.println("Koordinate x: ");
		x = sc.nextInt();
		System.out.println("Koordinate y: ");
		y = sc.nextInt(); 
		Point p = new Point(x,y); 

		stack.add(p);
		
		berechne(x, y);

	}

	private static void berechne(int x, int y) {
//
//		System.out.println(x +  " " + y);
//		
		System.out.println(stack.toString());
		
		//Früheres checkNext() und choseNext() zusammengeführt
		//stack.contains prüft, ob der Punkt schonmal besucht wurde. 
		if (((x+2) > 0 && (x+2) <= 5) && ((y+1) > 0 && (y+1) <= 5)){

			x = x + 2;
			y = y + 1;
			
			if (stack.contains(new Point(x,y))){

				x = x - 2;
				y = y - 1;
				
			} else {
				
				stack.add(new Point(x,y));
				x2 = x;
				y2 = y;
				berechne(x2,y2);
			}
		}
		
		if (((x+1) > 0 && (x+1) <= 5) && ((y+2) > 0 && (y+2) <= 5)){

			x = x + 1;
			y = y + 2;
			
			if (stack.contains(new Point(x,y))){

				x = x - 1;
				y = y - 2;
				
			} else {
				
				stack.add(new Point(x,y));
				x2 = x;
				y2 = y;
				berechne(x2,y2);
			}
		}
		
		if (((x-1) > 0 && (x-1) <= 5) && ((y+2) > 0 && (y+2) <= 5)){

			x = x - 1;
			y = y + 2;
			if (stack.contains(new Point(x,y))){

				x = x + 1;
				y = y - 2;
				
			} else {
			
				stack.add(new Point(x,y));
				x2 = x;
				y2 = y;
				berechne(x2,y2);
			}
		}
		
		if (((x-2) > 0 && (x-2) <= 5) && ((y+1) > 0 && (y+1) <= 5)){
			
			x = x - 2;
			y = y + 1;
			if (stack.contains(new Point(x,y))){
				x = x + 2;
				y = y - 1;
			} else {
				
				stack.add(new Point(x,y));
				x2 = x;
				y2 = y;
				berechne(x2,y2);
			}
		}
//		
//		if (((x-2) > 0 && (x-2) <= 5) && ((y-1) > 0 && (y-1) <= 5)){
//			x = x - 2;
//			y = y - 1;
//			
//			if (stack.contains(new Point(x,y))){
//				x = x + 2;
//				y = y + 1;
//			} else {
//				
//				stack.add(new Point(x,y));
//				x2 = x;
//				y2 = y;
//				berechne(x2,y2);
//			}
//		}
//		
//		if (((x-1) > 0 && (x-1) <= 5) && ((y-2) > 0 && (y-2) <= 5)){
//
//			x = x - 1;
//			y = y - 2;
//			
//			if (stack.contains(new Point(x,y))){
//				x = x + 1;
//				y = y + 2;
//			} else {
//					
//				stack.add(new Point(x,y));
//				x2 = x;
//				y2 = y;
//				berechne(x2,y2);
//			}
//		}
//			
//		if (((x+1) > 0 && (x+1) <= 5) && ((y-2) > 0 && (y-2) <= 5)){
//
//			x = x + 1;
//			y = y - 2;
//			
//			if (stack.contains(new Point(x,y))){
//
//				x = x - 1;
//				y = y + 2;
//			} else {
//			
//				stack.add(new Point(x,y));
//				x2 = x;
//				y2 = y;
//				berechne(x2,y2);
//			}
//		}
//		
//		if (((x+2) > 0 && (x+2) <= 5) && ((y-1) > 0 && (y-1) <= 5)){
//			
//			x = x + 2;
//			y = y - 1;
//			
//			if (stack.contains(new Point(x,y))){
//				x = x - 2;
//				y = y + 1;
//			} else {
//			
//				stack.add(new Point(x,y));
//				x2 = x;
//				y2 = y;
//				berechne(x2,y2);
//			}
//		}
		
		stack.pop();
		
	}
}
```

Zur Rekursion: 
Ein schwieriges Thema für mich ja, aber ich hab das soweit verstanden. Die Werte reseteten sich ja auch so wie sie sollen. Der Stack soll mir später die richtige Kombination ausgeben, bringt mir wenig wenn der all seine Werte wieder zurücksetzt, wenn er aus der Rekursion zurückkehrt. 
Und was genau ist daran schlecht einen Stack zu nutzen? Das hab ich nicht ganz verstanden


----------



## G@st (13. Mrz 2012)

Mit dieser Konfiguration bekomme ich übrigens für ein Beispiel diese Ausgabe:

Koordinate x: 
1
Koordinate y: 
3
[java.awt.Point[x=1,y=3]]
[java.awt.Point[x=1,y=3], java.awt.Point[x=3,y=4]]
[java.awt.Point[x=1,y=3], java.awt.Point[x=3,y=4], java.awt.Point[x=5,y=5]]
[java.awt.Point[x=1,y=3], java.awt.Point[x=1,y=5]]


----------



## langhaar! (13. Mrz 2012)

G@st hat gesagt.:


> Der Stack soll mir später die richtige Kombination ausgeben, bringt mir wenig wenn der all seine Werte wieder zurücksetzt, wenn er aus der Rekursion zurückkehrt.



In so einem Fall benutzt man Übergabeparameter oder (ausnahmsweise) eine globale Variable.


----------



## G@st (13. Mrz 2012)

Bin immer noch an dem Problem dran, es geht nicht mehr wirklich vorwärts. 

Hast du vielleicht eher einen Tipp, wie ich es schaffe, dass hier die richtigen Werte übergeben werden? Besser machen kann ich mein Programm immer noch, solange es erst einmal funktioniert...


----------



## langhaar! (13. Mrz 2012)

Ich habe mir gerade mal den Spass gemacht, dein Programm zu debuggen.
Du hast dich anscheinend nur auf die System.out.print verlassen, statt dir die Variablen anzusehen.
So sieht dein Stack in Wirklichkeit aus:


[java.awt.Point[x=1,y=3]]
[java.awt.Point[x=1,y=3], java.awt.Point[x=3,y=4]]
[java.awt.Point[x=1,y=3], java.awt.Point[x=3,y=4], java.awt.Point[x=5,y=5]]
[java.awt.Point[x=1,y=3], java.awt.Point[x=3,y=4]]
[java.awt.Point[x=1,y=3]]
[java.awt.Point[x=1,y=3], java.awt.Point[x=1,y=5]]

Du hast eine Inkonsistenz zwischen deinem Stack und den Variablen, die in der Rekursion gespeichert wurden. Deshalb sieht es aus, als spring es. Wenn du dir aber die Varibalen X und Y ansiehst (nicht den Stack!) wirst du merken, dass es richtig ist.


----------



## G@st (14. Mrz 2012)

Stimmt, das hatte ich gestern abend dann auch noch gemerkt, als ich es zuhause nochmal gedebuggt hatte, nachdem ich deine Nachricht gelesen habe. Offenbar speichert sich das Programm die Variablenwerte auch noch, wenn es einen Schritt aus der Rekursion heraustritt und prüft diesen Wert dann auch in diesem Durchgang ab, statt sich sein eigenes Original wieder zurückzuholen xO 

Jetzt versuche ich mal eine Lösung ohne Stack hinzubekommen. Ein zweidimensionales Array könnte die Aufgabe ja genauso übernehmen^^ Bin mal gespannt, ob das dann bessere Resultate wirft. Gibt's da noch was zu beachten, wenn ich so ein Array jetzt in die Rekursion einbaue? 
Ich programmiere normalerweise viel mit BaaN SQL, ein Warenwirtschaftssystem, da funktioniert das alles ein bisschen anders, deswegen verwirren mich mehrdimensionale Arrays in Java immer etwas.


----------



## G@st (14. Mrz 2012)

Sooo ich hab das ganze Mal von grundauf überarbeitet. Die Bedingungen sind kaum wieder zu erkennen und aus dem Stack wurde ein eindimensionales Point Array^^ Sieht das jetzt so besser aus? Funzt das besser als der stack?


```
private static void berechne(int xCor, int yCor) {
		zaehler++;
		x = xCor;
		y = yCor;
//		System.out.println(x +  " " + y);
//		
//		System.out.println(stack.toString());
		
		//Früheres checkNext() und choseNext() zusammengeführt
		//stack.contains prüft, ob der Punkt schonmal besucht wurde. 
		//Sollte dies der Fall sein, werden x und y zurückgesetzt.
		if (((x+2) > 0 && (x+2) <= 5) && ((y+1) > 0 && (y+1) <= 5)){
			
			x = x + 2; 
			y = y + 1; 

			int i = 0;
			
			while ((gefunden == false) && (i < stack.length)){
				
				if (stack[i] == (new Point(x,y)) ){
					
					x = x - 2;
					y = y - 1;
					gefunden = true; 
					
				} 
				i++;
			}
			
			if ((gefunden == false) && (stack.length < 25)){
					stack[stack.length + 1] = new Point (x,y);
					
					nextX = stack[stack.length].x;
					nextY = stack[stack.length].y;
					berechne(nextX, nextY);
				}
				
			}
```

*Edit:* Ich arbeite momentan noch mit einem 5x5-Brett, daher stack.length <25


----------



## G@st (14. Mrz 2012)

Hab jetzt auch den Rest angepasst und wegen der Arraydimension (leider unterschiedlich zu BaaN >.<) noch ein bisschen rumgewerkelt. Noch krieg ich aber Exceptions aufgrund der Dimensionierung. Wo liegt denn da mein Fehler? 


```
package springerproblem;
import java.awt.Point;
import java.util.*;
	
public class KnightProblem{

	static int zaehler = 0; 
	static int x, y = 0; 
	static int nextX, nextY = 0 ;
	int startx, starty = 0;
	
//	static Stack<Point> stack = new Stack<Point>();
	
	static Point [] stack = new Point [25];
	
	static String ergebnis; 
	
	static boolean gefunden = false; 

	Scanner sc = new Scanner(System.in); 
	
	public static void main (String [] args ){
		
		KnightProblem kp = new KnightProblem(); 
		
		kp.initialise();
		
		System.out.println("Das Ergebnis liegt vor: " + "\n\n");
		System.out.println(ergebnis);
		
	}

	private void initialise() {

		for (int u = 0; u < stack.length; u++){
			
			stack [u] = new Point (0,0);
			
		}
		
		System.out.println("Geben sie das Startfeld ein: ");
		System.out.println("Koordinate x: ");
		startx = sc.nextInt();
		System.out.println("Koordinate y: ");
		starty = sc.nextInt(); 
		Point p = new Point(startx,starty); 

		stack[0] = p;
		
		berechne(startx, starty);

	}

	private static void berechne(int xCor, int yCor) {
                      zaehler++;

		x = xCor;
		y = yCor;
//		System.out.println(x +  " " + y);
//		
//		System.out.println(stack.toString());
		
		//Früheres checkNext() und choseNext() zusammengeführt
		//stack.contains prüft, ob der Punkt schonmal besucht wurde. 
		//Sollte dies der Fall sein, werden x und y zurückgesetzt.
		if (((x+2) > 0 && (x+2) <= 5) && ((y+1) > 0 && (y+1) <= 5)){
			
			x = x + 2; 
			y = y + 1; 

			int i = 0;
			
			while ((gefunden == false) && (i < stack.length)){
				
				if (stack[i] == (new Point(x,y)) ){
					
					x = x - 2;
					y = y - 1;
					gefunden = true; 
					
				} 
				i++;
			}
			
			if ((gefunden == false) && (stack.length <= 25)){

				zaehler++;	
				stack[zaehler] = new Point (x,y);
					
				nextX = stack[zaehler].x;
				nextY = stack[zaehler].y;
				berechne(nextX, nextY);
				}
				
			} 

		if (((x+1) > 0 && (x+1) <= 5) && ((y+2) > 0 && (y+2) <= 5)){
			
			x = x + 1; 
			y = y + 2; 

			int i = 0;
			
			while ((gefunden == false) && (i < stack.length)){
				
				if (stack[i] == (new Point(x,y)) ){
					
					x = x - 1;
					y = y - 2;
					gefunden = true; 
					
				} 
				i++;
			}
			
			if ((gefunden == false) && (stack.length <= 25)){
				zaehler++;	
				stack[zaehler] = new Point (x,y);
					
				nextX = stack[zaehler].x;
				nextY = stack[zaehler].y;
				berechne(nextX, nextY);
				}
				
		} 
		
		if (((x-1) > 0 && (x-1) <= 5) && ((y+2) > 0 && (y+2) <= 5)){
			
			x = x - 1; 
			y = y + 2; 

			int i = 0;
			
			while ((gefunden == false) && (i < stack.length)){
				
				if (stack[i] == (new Point(x,y)) ){
					
					x = x + 1;
					y = y - 2;
					gefunden = true; 
					
				} 
				i++;
			}
			
			if ((gefunden == false) && (stack.length <= 25)){
					stack[zaehler] = new Point (x,y);
					
					nextX = stack[zaehler].x;
					nextY = stack[zaehler].y;
					berechne(nextX, nextY);
				}
		} 
		
		if (((x-2) > 0 && (x-2) <= 5) && ((y+1) > 0 && (y+1) <= 5)){
			
			x = x - 2; 
			y = y + 1; 

			int i = 0;
			
			while ((gefunden == false) && (i < stack.length)){
				
				if (stack[i] == (new Point(x,y)) ){
					
					x = x + 2;
					y = y - 1;
					gefunden = true; 
					
				} 
				i++;
			}
			
			if ((gefunden == false) && (stack.length <= 25)){
					stack[zaehler] = new Point (x,y);
					
					nextX = stack[zaehler].x;
					nextY = stack[zaehler].y;
					berechne(nextX, nextY);
				}
				
		} 
	
		if (((x-2) > 0 && (x-2) <= 5) && ((y-1) > 0 && (y-1) <= 5)){
			
			x = x - 2; 
			y = y - 1; 

			int i = 0;
			
			while ((gefunden == false) && (i < stack.length)){
				
				if (stack[i] == (new Point(x,y)) ){
					
					x = x + 2;
					y = y + 1;
					gefunden = true; 
					
				} 
				i++;
			}
			
			if ((gefunden == false) && (stack.length <= 25)){
					stack[zaehler] = new Point (x,y);
					
					nextX = stack[zaehler].x;
					nextY = stack[zaehler].y;
					berechne(nextX, nextY);
				}
				
		} 
		
		if (((x-1) > 0 && (x-1) <= 5) && ((y-2) > 0 && (y-2) <= 5)){
			
			x = x - 1; 
			y = y - 2; 

			int i = 0;
			
			while ((gefunden == false) && (i < stack.length)){
				
				if (stack[i] == (new Point(x,y)) ){
					
					x = x + 1;
					y = y + 2;
					gefunden = true; 
					
				} 
				i++;
			}
			
			if ((gefunden == false) && (stack.length <= 25)){
					stack[zaehler] = new Point (x,y);
					
					nextX = stack[zaehler].x;
					nextY = stack[zaehler].y;
					berechne(nextX, nextY);
				}
				
		} 
		
		if (((x+1) > 0 && (x+1) <= 5) && ((y-2) > 0 && (y-2) <= 5)){
			
			x = x + 1; 
			y = y - 2; 

			int i = 0;
			
			while ((gefunden == false) && (i < stack.length)){
				
				if (stack[i] == (new Point(x,y)) ){
					
					x = x - 1;
					y = y + 2;
					gefunden = true; 
					
				} 
				i++;
			}
			
			if ((gefunden == false) && (stack.length <= 25)){
					stack[zaehler] = new Point (x,y);
					
					nextX = stack[zaehler].x;
					nextY = stack[zaehler].y;
					berechne(nextX, nextY);
				}
				
		} 
		
		if (((x+2) > 0 && (x+2) <= 5) && ((y-1) > 0 && (y-1) <= 5)){
			
			x = x + 2; 
			y = y - 1; 

			int i = 0;
			
			while ((gefunden == false) && (i < stack.length)){
				
				if (stack[i] == (new Point(x,y)) ){
					
					x = x - 2;
					y = y + 1;
					gefunden = true; 
					
				} 
				i++;
			}
			
			if ((gefunden == false) && (stack.length <= 25)){
					stack[zaehler] = new Point (x,y);
					
					nextX = stack[zaehler].x;
					nextY = stack[zaehler].y;
					berechne(nextX, nextY);
				}
				
		} 
		
//		System.out.println(stack.toString());
		
//		System.out.println(zaehler);
		
		if (zaehler >= 24){
			System.out.println("Gefunden");
			ergebnis = stack.toString();
			System.out.println(ergebnis.toString());
		} else {
			
			stack[zaehler] = new Point(0,0);
			zaehler--;
			
		}
	}
}
```


----------



## langhaar! (14. Mrz 2012)

Ich habe über das Problem noch mal nachgedacht.

Entgegen meiner obigen Aussage halte ich einen Stack (oder eine Liste) inzwischen doch für sinnvoll.
Ich habe dein Programm mal strukturell umgestellt  läuft jetzt.


```
private void berechne(int x, int y) {
    	
       System.out.println(stack.toString()); 
       if (x > 0 && x <= 4 && y > 0 && y <= 4) {
    	   if (!stack.contains(new Point(x,y))) {
	    	   stack.push(new Point(x,y));
	    	   berechne (x+2,y+1);
	    	   berechne (x+2,y-1);
	    	   berechne (x-2,y+1);
	    	   berechne (x-2,y-1);
	    	   berechne (x+1,y+2);
	    	   berechne (x+1,y-2);
	    	   berechne (x-1,y+2);
	    	   berechne (x-1,y-2);
	    	   if (!stack.isEmpty())
	        	   stack.pop();
	           }
    	  }
    }
```

P.S.: sieht trivial aus, hat mich trotzdem knapp 2 Stunden gekostet.
P.S.S.: dein Problem war, dass du die Variablen bei einem erfolglosen Zweig nicht wieder zurückgerechnet hast.
P.S.S.S.: aus Laufzeit und Validierungsgründen habe ich nur 4x4 Felder betrachtet.


----------



## G@st (14. Mrz 2012)

Wow, danke dass du dir nochmal so viel Arbeit damit gemacht hast^^ Das Programm sieht in deiner Version dann natürlich etwas trivialer aus, aber solange es läuft ist das super, vielen vielen Dank. Ich werde das gleich mal übernehmen und dann durchtesten xD

Noch einmal zum Abschluss, bevor wir das Thema dann als [Erledigt] abhaken können: Siehst du (brauchst jetzt nicht hingehen und wieder ewig dran rumschrauben, nur falls dus direkt siehst), wo ich meine Dimensionierung der Arrays verhauen hab?


----------



## langhaar! (14. Mrz 2012)

Um noch mal auf dein ursprüngliches Programm einzugehen:


```
if (((x+2) > 0 && (x+2) <= 5) && ((y+1) > 0 && (y+1) <= 5)){
 
            x = x + 2;
            y = y + 1;
            
            if (stack.contains(new Point(x,y))){
 
                x = x - 2;
                y = y - 1;
                
            } else {
                
                stack.add(new Point(x,y));
                x2 = x;
                y2 = y;
                berechne(x2,y2);
            }
        }
```
Wenn der rekursive Aufruf von berechne zu Ende ist, hast du trotzdem x und y erhöht.
Du hättest direkt nach dem berechne ein x = x -2 und y = y -1 einfügen müssen, um mit den ursprünglichen Werten weiterzurechnen, und nicht mit denen, die sich als erfolgos erwiesen haben.


----------



## G@st (14. Mrz 2012)

Entschuldige, vielleicht lieg ich auch völlig falsch, aber kann es sein, dass da noch ein kleiner Fehler in deinem Programm ist? Und zwar hier: 


```
if (x > 0 && x <= 4 && y > 0 && y <= 4) {
	           if (!stack.contains(new Point(x,y))) {
	               stack.push(new Point(x,y));
```

x und y werden zuvor nicht von ihrem eingegebenen Wert verändert, dass heißt, dieser Wert existiert dann schon im Stack und er beendet das Programm auf der Stelle, oder?

Das tut er zumindest bei mir^^ Könntest du mal den gesamten veränderten Quellcode posten?


----------



## langhaar! (14. Mrz 2012)

Du musst das stack.push() im Aufruf rausnehmen.

Ich habe mit folgendem Aufruf getestet:

```
private void initialise() {
 
        berechne(1, 3);
}
```


----------



## G@st (14. Mrz 2012)

Aber wenn ich das stack.push herausnehme hat er doch gar keine Einträge mehr im Stack oO Dann liefert er mir ne Exception 

Die Dimensionierung bei dir war noch auf 4x4 Bretter ausgelegt, da konnte er keine Lösung finden^^


----------



## langhaar! (14. Mrz 2012)

Wo soll denn da eine Exception kommen? Bei mir läuft es. Das es bei 4x4 keine Lösung gibt, habe ich gemerkt. Ich habe einen kompletten 15 zügigen Pfad mit Zettel und Stift nachvollzogen 


```
import java.awt.Point;
import java.util.*;
    
public class Test{
    
    int x, y; 
    
    static Stack<Point> stack = new Stack<Point>();
    
    public static void main (String [] args ){
        
        Test sp = new Test(); 
        
        sp.initialise();
        
        
    }
    
    private void initialise() {
 
        berechne(1, 3);
    }
 
    private void berechne(int x, int y) {
//      
    		System.out.println(stack.toString());
        
       if (x > 0 && x <= 4 && y > 0 && y <= 4) {
    	
    	   if (!stack.contains(new Point(x,y))) {
	    	   stack.push(new Point(x,y));
	    	   berechne (x+2,y+1);
	    	   berechne (x+2,y-1);
	    	   berechne (x-2,y+1);
	    	   berechne (x-2,y-1);
	    	   berechne (x+1,y+2);
	    	   berechne (x+1,y-2);
	    	   berechne (x-1,y+2);
	    	   berechne (x-1,y-2);
	    	   if (!stack.isEmpty())
	        	   stack.pop();
	           }
    	  }
    } 
}
```


----------



## G@st (14. Mrz 2012)

Achso du meinst des stack.push im initialise() nicht das in berechne(). Dann versteh ich natürlich was du gemeint hast^^ 
Wenn man es in berechne() weglässt bekommt man überhaupt keine Ergebnisse, gibt immer wieder den stack aus, der in dem Fall so aussieht: 

[]

Und dann rennt er damit irgendwann gegen ne Wand xD 

Klar, das mit dem 4x4-Brett dachte ich mir, dass das Absicht war  Habs jetzt auf 5x5 umgestellt, da rennt er aber ne ganze Zeit lang (wohl vor allem wegen dem print). Gibts ne Möglichkeit in diese Version eine Variable einzubauen, die mir den gefundenen Weg zurückgibt und sonst nichts?


----------



## langhaar! (14. Mrz 2012)

Krass! Ein 5x5 Feld hat 11631913 betrachtete Züge. Ein 6x6 Feld legt meinen Rechner lahm.

Ist hier zufällig ein Mathematiker, der mir die Anzahl Züge für 8x8 berechenen kann?



G@st hat gesagt.:


> Gibts ne Möglichkeit in diese Version eine Variable einzubauen, die mir den gefundenen Weg zurückgibt und sonst nichts?



Das ist dermassen einfach, dass lass ich dich selbst probieren 
Wenn's partout nicht klappt, meld dich noch mal.

Hinweis: Woran erkennt man, dass eine Lösung vorliegt?


----------



## G@st (14. Mrz 2012)

Hahaha, ja das ist relativ nervig an der Rekursion dann xD Das heisst auch bei dem 8x8-Feld kommt er irgendwann zurück nur würde das ewig dauern? xD

Er durchläuft dann meines Wissens nach 8! * 64 Möglichkeiten xO

Das wäre dann also ausgerechnet 2 580 480, wieviele Züge das sind, keine Ahnung xD

Wie siehts denn mit ner Speichervariablen aus? Ich wollte die Züge dann nummeriert auf der Console in einem 5x5 geordneten Feld ausgeben?


*Edit:* Sorry hab deine Nachricht erst gesehen, ich setz  mich an die Programmierung der Variablen dran ;D


----------



## Landei (14. Mrz 2012)

langhaar! hat gesagt.:


> Ich habe über das Problem noch mal nachgedacht.
> 
> Entgegen meiner obigen Aussage halte ich einen Stack (oder eine Liste) inzwischen doch für sinnvoll.
> Ich habe dein Programm mal strukturell umgestellt  läuft jetzt.
> ...



Die einzelnen Aufrufe kann man auch mit Schleifen erledigen:


```
for(int dx = -2; dx <= 2; dx++) {
   for(int dy = -2; dy <= 2; dy++) {
       if(dx*dx + dy*dy == 5) {
           berechne (x+dx,y+dy);
       } 
   }
}
```


----------



## langhaar! (14. Mrz 2012)

Kann man. Hätte ich vor 25 Jahren auch gemacht. Da war noch jede gesparte Zeile eine gute Zeile


----------



## G@st (14. Mrz 2012)

Und ich werd das in 5 Jahren vielleicht mal so machen. Im Moment gehts mir noch eher darum den Algorithmus zu verstehen und ihn möglichst leicht schreibbar zu machen^^ Später kommen dann solche Extras hinzu, da lass ich mir noch ein bissl Zeit.

Eine Frage hätte ich noch, dann können wir endlich aufhören  Ich will diesen gefundenen Weg nun in solcher Form ausgeben: 


| 1 | 15 | 14 | 2 | 5 | 
| 3 | 8 | 7 | 10 | 4 |

usw. (Zahlen in dem Fall sinnlos gewählt)

Kann mir da noch jemand helfen? So sieht der Code momentan aus:

```
package springerproblem;
import java.awt.Point;
import java.util.*;

public class DummyKnightProblem{

	static int zaehler = 0; 
	static int x, y = 0; 
	static int nextX, nextY = 0 ;
	int startX, startY = 0;
	
	static Stack<Point> stack = new Stack<Point>();
	static Stack<Point> endStack = new Stack<Point>(); 
	
	static String ergebnis; 

	Scanner sc = new Scanner(System.in); 
	
	public static void main (String [] args ){
		
		DummyKnightProblem kp = new DummyKnightProblem(); 
		
		kp.initialise();
		
		String string = endStack.toString();
		
		System.out.println(string);
		
		System.out.println("Ende");
	}

	private void initialise() {

		System.out.println("Geben sie das Startfeld ein: ");
		System.out.println("Koordinate x: ");
		startX = sc.nextInt();
		System.out.println("Koordinate y: ");
		startY = sc.nextInt(); 

		berechne(startX, startY);

	}

	
	private void berechne(int x, int y) {
	        zaehler++;
	        //Die Überprüfung geht über die Grenzwerte 0 und 5, nicht mehr über die Zahlen selbst. Sind die Zahlen innerhalb der 
	        //zulässigen Begrenzung, so wird eine weitere Berechnung angeordnet. 
	        //Nacheinander durchläuft das Programm somit alle gegebenen Möglichkeiten und gibt die Ergebnisse aus.
	       if (x > 0 && x <= 5 && y > 0 && y <= 5) {
	           if (!stack.contains(new Point(x,y))) {
	               stack.push(new Point(x,y));
	               berechne (x+2,y+1);
	               berechne (x+2,y-1);
	               berechne (x-2,y+1);
	               berechne (x-2,y-1);
	               berechne (x+1,y+2);
	               berechne (x+1,y-2);
	               berechne (x-1,y+2);
	               berechne (x-1,y-2);
	               if (stack.size() >= 25){
	            	   //Sobald ein Ergebnis erreicht wurde, wird der sich verändernde stack-Wert geklont und mit endStack aus der Schleife
	            	   //heraus transportiert.
	            	   endStack = ((Stack<Point>) stack.clone());
	               }
	               
	               if (!stack.isEmpty())
	                   stack.pop();
	               }
	          }
	    }
}
```

endStack exportiert den gefundenen Lösungspfad und bringt ihn damit in Sicherheit vor dem stack.pop(). Wie kann ich diese Daten, die im Array als Point vorliegen, jetzt extrahieren?


----------



## langhaar! (14. Mrz 2012)

Wenn du nur ein Ergebnis willst, solltest du die Verarbeitung nach dem ersten Treffer abbrechen. Dazu kannst eine boolean setzen.

Extraktion des Stacks:

```
for (Point p: endStack) {
       System.out.println(p);
 }
```


----------



## G@st (14. Mrz 2012)

Du verstehst mich falsch^^ Ich muss die Reihenfolge der Züge auf einem Schachbrettähnlichen Format ausgeben.

Also mit Trennzeichen und statt den Koordinaten, soll an der Stelle der Koordinaten stehen, welcher Zug das in der gesamten Reihenfolge war^^ Das funzt im Moment allerdings noch nicht so gut. Da hab ich irgendwo noch einen Fehler drin  Kannst du dich noch einmal erbarmen und dir die Ausgabe anschauen. 

Der Debugger hat ergeben, dass extract[e] vollständig richtig beladen ist, nur das zweidimensionale ausgabe - Array will nicht >.<


```
package springerproblem;
import java.awt.Point;
import java.util.*;

public class DummyKnightProblem{

	static int zaehler = 0; 
	static int x, y = 0; 
	static int nextX, nextY = 0 ;
	int startX, startY = 0;
	static int e = 0; 
	int counter = 0; 
	
	static int ausgabe [][] = new int [5][5]; 
	
	static Point [] extract = new Point[25];
	
	static Stack<Point> stack = new Stack<Point>();
	static Stack<Point> endStack = new Stack<Point>(); 
	
	static String ergebnis; 

	Scanner sc = new Scanner(System.in); 
	
	public static void main (String [] args ){
		
		DummyKnightProblem kp = new DummyKnightProblem(); 
		
		kp.initialise();
		
		String string = endStack.toString();

		System.out.println(string);
		
		kp.ausgabe();
	
		System.out.println("Ende");
	}



	private void initialise() {

		System.out.println("Geben sie das Startfeld ein: ");
		System.out.println("Koordinate x: ");
		startX = sc.nextInt();
		System.out.println("Koordinate y: ");
		startY = sc.nextInt(); 

		berechne(startX, startY);

	}
	
	private void berechne(int x, int y) {
	        zaehler++;
	        //Die Überprüfung geht über die Grenzwerte 0 und 5, nicht mehr über die Zahlen selbst. Sind die Zahlen innerhalb der 
	        //zulässigen Begrenzung, so wird eine weitere Berechnung angeordnet. 
	        //Nacheinander durchläuft das Programm somit alle gegebenen Möglichkeiten und gibt die Ergebnisse aus.
	       if (x > 0 && x <= 5 && y > 0 && y <= 5) {
	           if (!stack.contains(new Point(x,y))) {
	               stack.push(new Point(x,y));
	               berechne (x+2,y+1);
	               berechne (x+2,y-1);
	               berechne (x-2,y+1);
	               berechne (x-2,y-1);
	               berechne (x+1,y+2);
	               berechne (x+1,y-2);
	               berechne (x-1,y+2);
	               berechne (x-1,y-2);
	               if (stack.size() >= 25){
	            	   //Sobald ein Ergebnis erreicht wurde, wird der sich verändernde stack-Wert geklont und mit endStack aus der Schleife
	            	   //heraus transportiert.
	            	   endStack = ((Stack<Point>) stack.clone());
	               }
	               
	               if (!stack.isEmpty())
	                   stack.pop();
	               }
	          }
	    }
	
	private void ausgabe() throws ArrayIndexOutOfBoundsException{

		//Die forschleife durchläuft den endStack von oben nach unten. Dadurch liefer die Schleife
		//die einzelnen Schritte des Programms ins Array extract, mit dem Schlusswert startend.
		//In extract[0] liegt also der Schlusswert. In extract[24] liegt der erste, also der Startwert.
		
		try {
			for (e = 0; e <= 24; e++ ){
		
				extract[e] = endStack.get(((endStack.size())-e)-1);
			}
			
			for (e = 24; e >= 0; e--){
				
				int xp = extract[e].x;
				int yp = extract[e].y;
				
				ausgabe[(extract[e].x)-1][(extract[e].y)-1] = e; 
				
			}
			
			for (int yFor = 0; yFor < 5; yFor++){
				
				for (int xFor = 0; xFor < 5; xFor++){
					counter++;
					System.out.print(" | ");
					System.out.print((ausgabe[xFor][yFor])+1);
					
					if (counter == 5){
						System.out.println("\n");
						counter = 0;
					}
				}
				
			}
		} catch (ArrayIndexOutOfBoundsException exAioob){
			
			System.out.println("Der Anfangswert liefert keine mögliche Lösung");
			
		}
		
		
	}
}
```


----------



## G@st (15. Mrz 2012)

Das Problem ist beseitigt. Ich hab alle Fehler ausgemerzt, einen Abfangmechanismus für unpassende Koordinaten eingebaut und dafür gesorgt, dass mir das Programm auf der Konsole den entsprechenden Weg anzeigt. Damit ist dieses Thema abgehakt denke ich^^ Hier noch einmal der abgeschlossenen Code: 


```
package springerproblem;
import java.awt.Point;
import java.util.*;

public class DummyKnightProblem{

	static int zaehler = 0; 
	static int x, y = 0; 
	static int nextX, nextY = 0 ;
	static int e = 0; 
	int counter = 0; 
	int startX, startY = 0;

	static Point [] extract = new Point[25];
	static int ausgabe [][] = new int [5][5]; 
	
	static Stack<Point> stack = new Stack<Point>();
	static Stack<Point> endStack = new Stack<Point>(); 

	Scanner sc = new Scanner(System.in); 
	
	public static void main (String [] args ){
		
		DummyKnightProblem kp = new DummyKnightProblem(); 
		
		kp.initialise();
		
		String string = endStack.toString();

		System.out.println(string);
		
		kp.ausgabe();
	
		System.out.println("Ende");
	}

	private void initialise() {

		System.out.println("Geben sie das Startfeld ein: ");
		System.out.println("Koordinate x: ");
		startX = sc.nextInt();
		System.out.println("Koordinate y: ");
		startY = sc.nextInt(); 

		berechne(startX, startY);

	}
	
	private void berechne(int x, int y) {
	        zaehler++;
	        //Die Überprüfung geht über die Grenzwerte 0 und 5, nicht mehr über die Zahlen selbst. Sind die Zahlen innerhalb der 
	        //zulässigen Begrenzung, so wird eine weitere Berechnung angeordnet. 
	        //Nacheinander durchläuft das Programm somit alle gegebenen Möglichkeiten und gibt die Ergebnisse aus.
	       if (x > 0 && x <= 5 && y > 0 && y <= 5) {
	           if (!stack.contains(new Point(x,y))) {
	               stack.push(new Point(x,y));
	               berechne (x+2,y+1);
	               berechne (x+2,y-1);
	               berechne (x-2,y+1);
	               berechne (x-2,y-1);
	               berechne (x+1,y+2);
	               berechne (x+1,y-2);
	               berechne (x-1,y+2);
	               berechne (x-1,y-2);
	               if (stack.size() >= 25){
	            	   //Sobald ein Ergebnis erreicht wurde, wird der sich verändernde stack-Wert geklont und mit endStack aus der Schleife
	            	   //heraus transportiert.
	            	   endStack = ((Stack<Point>) stack.clone());
	               }
	               
	               if (!stack.isEmpty())
	                   stack.pop();
	               }
	          }
	    }
	
	private void ausgabe() throws ArrayIndexOutOfBoundsException{

		//Die forschleife durchläuft den endStack von oben nach unten. Dadurch liefer die Schleife
		//die einzelnen Schritte des Programms ins Array extract, mit dem Schlusswert startend.
		//In extract[0] liegt also der Schlusswert. In extract[24] liegt der erste, also der Startwert.
		
		try {
			for (e = 0; e <= 24; e++ ){
		
				extract[e] = endStack.get(((endStack.size())-e)-1);
			}
			// 0 steht für 25, 25 für 0
			for (e = 24; e >= 0; e--){
				
				int xp = extract[e].x;
				int yp = extract[e].y;
				
				ausgabe[(extract[e].x)-1][(extract[e].y)-1] = 25 - e; 
				
			}
			//Unbekannter Fehler
			for (int xFor = 0; xFor <= 4; xFor++){
				
				for (int yFor = 0; yFor <= 4; yFor++){
					counter++;
					System.out.print(" | ");
					System.out.print((ausgabe[xFor][yFor]));
					
					if (counter == 5){
						System.out.println("\n");
						counter = 0;
					}
				}
				
			}
		} catch (ArrayIndexOutOfBoundsException exAioob){
			
			System.out.println("Der Anfangswert liefert keine mögliche Lösung\n");
			
			if (startX < 0 || startX > 5 || startY < 0 || startY > 5){
				System.out.println("Sie haben einen ungültigen Wert eingegeben!\n");
			}
			
		}
		
		
	}
}
```


----------

