Rekursion - mal wieder... [editiert]

O

Ook!

0
Hallo!

Ich versuche gerad das Springerproblem zu lösen. Die Rekursion an sich steht, jedoch ist irgendwo der Wurm versteckt, den ich nicht finden kann.
Das Problem ist nun, dass die Methode durchläuft, aber Ich keine Ergebnisse in meine results ArrayList bekomme.

Die Anwendung schaut so aus:
Code: 
import java.util.ArrayList;
import java.util.List;

public class Knightproblem {

	public static void main(String[] args) {
		Solver solver = new Knightproblem().new Solver();
		System.out.println("Anzahl Lösungen: "+ solver.getResultCount());
		System.out.println("\n"+ solver.getResultFields());
	}

	class Solver {

		private List<int[][]> results = null;
		private final int size = 6;
		private int[][] jumps = { {-1,2}, {-2,1}, {1,-2}, {2,1}, {-1,-2}, {-2,-1}, {1,2}, {2,-1} };

		public Solver() {
			this.results = new ArrayList<int[][]>();
			this.doIt(0, 0, new int[size][size], 1);
		}

		private void doIt(int x, int y, int[][] visited, int jump) {
			if(jump > (visited.length*visited.length)) {
				results.add(cloneField(visited));
				return;
			}

			for(int i=0; i<8; i++) {
				if((x+jumps[i][0]) > -1 && (y+jumps[i][1]) > -1 && (x+jumps[i][0]) < visited.length && (y+jumps[i][1]) < visited.length) {
					if(visited[x+jumps[i][0]][y+jumps[i][1]] == 0) {
						visited[x][y] = jump;
						doIt((x+jumps[i][0]), (y+jumps[i][1]), visited, jump+1);
						visited[x][y] = 0;
					}
				}
			}
		}

		private int[][] cloneField(int[][] visited){
			int[][] clone = new int[size][size];
			for(int i=0; i<size; i++){
				clone[i] = visited[i].clone();
			}
			return clone;
		}

		public String getResultFields(){
			String returnString = "";
			for(int[][] field : results) {
				for(int[] row : field) {
					for(int col : row) {
						returnString += (col +"\t");
					}
					returnString += "\n";
				}
				returnString += "\n";
			}
			return returnString;
		}

		public int getResultCount() {
			return results.size();
		}

	}

}

Vielleicht sieht ja jemand von euch den Fehler!

Grüße
Felix
 
Ganz ehrlich - ich blicke im Code nicht durch ;).
Versuche es mal zu kommentieren (und zwar nach dem Prinzip "Warum wird dies und jenes gemacht". Dann siehst Du vielleicht auch schon den Fehler.
 
Joar, das habe ich auch schon einmal gemacht... hat leider nichts gebracht.
Ich habe es nun nochmal kommentiert und hoffe, dass du mein gewusel nun verstehst.

Code: 
	class Solver {

		private List<int[][]> results = null;
		private final int size = 6;
		// alle möglichen sprungvarianten für den springer ( gespeichert als: { x, y })
		private int[][] jumps = { {-1,2}, {-2,1}, {1,-2}, {2,1}, {-1,-2}, {-2,-1}, {1,2}, {2,-1} };

		public Solver() {
			this.results = new ArrayList<int[][]>();
			// aufruf der methode mit den koordinaten x 0 / y 0, einem neuen array mit der größe size*size, und 1 (dem ersten sprung)
			this.doIt(0, 0, new int[size][size], 1);
		}

		// methode, die die lösungen finden soll... tut sie aber nicht :D
		// x und y sind die koordinaten für das visited array, jump der aktuelle sprung
		private void doIt(int x, int y, int[][] visited, int jump) {
			// abbruchbedingung, wenn er beim 37. sprung angekommen ist, soll er die lösung klonen und zu results hinzufügen
			if(jump > (visited.length*visited.length)) {
				results.add(cloneField(visited));
				return;
			}

			// für jeden möglichen sprung im array jumps
			for(int i=0; i<8; i++) {
				// prüfe ob das feld existiert
				if((x+jumps[i][0]) > -1 && (y+jumps[i][1]) > -1 && (x+jumps[i][0]) < visited.length && (y+jumps[i][1]) < visited.length) {
					// prüfe, ob das feld noch frei ist (also noch nicht besucht)
					if(visited[x+jumps[i][0]][y+jumps[i][1]] == 0) {
						// besuche das feld
						visited[x][y] = jump;
						// springe zum nächsten feld x+jumps[i][0] / y+jumps[i][1]
						doIt((x+jumps[i][0]), (y+jumps[i][1]), visited, jump+1);
						// setze das feld wieder auf 0
						visited[x][y] = 0;
					}
				}
			}
		}

		// das aktuelle visited feld wird geklont
		private int[][] cloneField(int[][] visited){
			int[][] clone = new int[size][size];
			for(int i=0; i<size; i++){
				clone[i] = visited[i].clone();
			}
			return clone;
		}

		// nur für die ausgabe der liste
		public String getResultFields(){
			String returnString = "";
			for(int[][] field : results) {
				for(int[] row : field) {
					for(int col : row) {
						returnString += (col +"\t");
					}
					returnString += "\n";
				}
				returnString += "\n";
			}
			return returnString;
		}

		// gibt die anzahl der lösungen (größe von results) zurück
		public int getResultCount() {
			return results.size();
		}

	}

Ich hoffe, dass meine gedankengänge nun verständlicher sind :]
 
Naja, du hast nach dem Prinzip "Wie" kommentiert und nicht "Warum" ;)
Denn wie du es machst, steht ja schon im Code. Die Frage ist immer "Warum macht man es ?"
Nicht destotrotz:
habe mal eine PrettyPrinter Funktion eingefügt:
Code: 
InputStream ins=System.in;
...
	private void doIt(int x, int y, int[][] visited, int jump) {
			if (jump==visited.length*visited.length) 
				prettyPrinter(visited);
			if(jump > (visited.length*visited.length)) {
				results.add(cloneField(visited));
				return;
			}
....

public void prettyPrinter(int[][]board)
		{
			for (int i=0;i<board.length;i++)
				{
				   for(int j=0;j<board[0].length;j++)
					System.out.print(board[i][j]+" ");
				   System.out.println();
				}
			System.out.println("\n");
			
			try
			{
			   if (ins.read()=='e')System.exit(0);
			}catch (IOException ioex)
			{
				ioex.printStackTrace();
			}
bei der Ausgabe sieht man dann, dass es bei dem letzen Schritt Probleme gibt. Und zwar wird dieser irgendwie "nicht gemacht"
Code: 
1 16 13 8 21 
12 7 20 3 14 
17 2 15 22 9 
6 11 24 19 4 
0 18 5 10 23
nun, wenn man es etwas genauer anschaut:
du machst hier einen Schritt:
Code: 
doIt((x+jumps[i][0]), (y+jumps[i][1]), visited, jump+1);
und versuchst dann wieder den Springer zu bewegen (schaust nach dem freien Feld).
Wenn du aber den letzen Schritt machst, kannst du bei der nachfolgenden Prüfung (ob der Springer bewegt werden kann) gar keinen Erfolg haben - sprich, auch wenn der letze Schritt richtig war, ist das Ergebnis trotzdem negativ, es wird dann nicht mehr versucht den 37 Schritt zu machen, da ja kein Feld mehr frei ist. Ein Teufelskreis ;)
ich schlage vor, das so abzuändern:
Code: 
if (jump>=visited.length*visited.length) 
			 {
				visited[x][y]=jump;
				results.add(cloneField(visited));
				return;
			}
so, nun bleibt ein weiteres Problem: du variirst deinen Startpunkt nicht. Könnte ja sein, dass bei bestimmten Brettern bei 0,0 Starpunkt vielleicht gar keine Lösung gibt - aber aufjedenfall bekommt man nicht alle Lösungen heraus.
Wenn man den Startwert auf 0,4 ändert und jede Lösung sofort ausgibt (bin zu faul bei 6x6 auf das Ergebnis zu warten ;) )
Code: 
7 14 17 28 9 4 
16 29 8 5 18 27 
13 6 15 26 3 10 
30 23 2 11 34 19 
1 12 21 32 25 36 
22 31 24 35 20 33
 
Tatsache... da lag der Hund begraben, es sind eben meist die Grenzwerte, die die Problem bereiten!
So simpel der Fehler und so schwer zu finden :)

Werde die Lösung dann die kommenden Tage im Programmieraufgaben-Forum posten. :)

Danke dir... mal wieder ein Problem gelöst dank deiner Hilfe!

Ciao bis bald
Gruß
Felix
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben