# "Springerproblem"



## JosephineX (15. Mai 2008)

Hallo
Ich soll als Übungsaufgabe ein Programm zum Springerproblem implementieren, also ein Schachfeld mit n Feldern und es soll ein Pfad gefunden werden, so das der Springer auf jedem Feld genau einmal landet.
Dummerweise tut das Programm nicht was es soll bis jetzt und jetzt gibts auch noch eine Fehlermeldung:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
	at SpringerRek.NochFrei(SpringerRek.java:86)
	at SpringerRek.position(SpringerRek.java:19)
	at SpringerRek.main(SpringerRek.java:107)

Ich hab mich bisl schlau gemacht, und gefunden das wohl die ArrayGrenzen überschritten werden. Irgendwie versteh ich aber nicht wieso.
Kann mir irgendwer helfen das Programm zum laufen zu bringen?

Hier mal mein Code:

```
public class SpringerRek 
{
	static int n = 8;	//Feldgroesse
	static int x =0, y=0;	//Startwerte
	static int[][] Jumper = new int[n*n][2];	//Springer
	static boolean[][] Frei = new boolean[n][n];	//Feldbelegung
	
	public static int[][] position(/*int[][] akt,*/int x,int y,int zug)
	{
		if ((NochFrei(x+2,y+1) == true) && (AufmFeld(x+2,y+1) == true))		//Sprungmöglichkeiten
		{
			x = x+2;
			y = y+1;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((NochFrei(x+2,y-1) == true) && (AufmFeld(x+2,y-1) == true))
		{
			x = x+2;
			y = y-1;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((NochFrei(x+1,y+2) == true) && (AufmFeld(x+1,y+2) == true))
		{
			x = x+1;
			y = y+2;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((NochFrei(x+1,y-2) == true) && (AufmFeld(x+1,y-2) == true))
		{
			x = x+1;
			y = y-2;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((NochFrei(x-1,y+2) == true) && (AufmFeld(x-1,y+2) == true))
		{
			x = x-1;
			y = y+2;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((NochFrei(x-1,y-2) == true) && (AufmFeld(x-1,y-2) == true))
		{
			x = x-1;
			y = y-2;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((NochFrei(x-2,y+1) == true) && (AufmFeld(x-2,y+1) == true))
		{
			x = x-2;
			y = y+1;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((NochFrei(x-2,y-1) == true) && (AufmFeld(x-2,y-1) == true))
		{
			x = x-2;
			y = y-1;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else 
		{
			x=99; y= 99;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
	}
	
	public static boolean NochFrei(int aktX, int aktY)	//Testet ob das Feld noch frei ist
	{
		if (Frei[aktX][aktY] == true)
		{
			Frei[aktX][aktY] = false;
			return true;
		}
		else return false;
	}
	
	public static boolean AufmFeld(int x,int y)	//Testet ob der Springer sich noch aufm Feld befindet
	{
		if(x >= n) {return false;}	//Das Feld ist n*n gros, da Zählung bei 0 beginnt, mus x <= n-1 bleiben!
		if(x < 0) {return false;}
		if(y >= n) {return false;}
		if(y < n) {return false;}
		else {return true;}	//Alles ok!
	}
	
	public static void main(String[] args)
	{
		for (int znum = 0; znum <= (n*n)-1; znum++)
		{
			SpringerRek.position(/*Jumper,*/x,y,znum);
			System.out.println ("Sprung Nr " + znum + " x: " + Jumper[znum][0] + " y: " + Jumper[znum][1]);
		}
	}
}
```


----------



## JosephineX (15. Mai 2008)

Sorry das ich jetz n Doppelpost mache aber ich weis nicht wie ich meinen Eintrag editieren kann  
Also ich hab die Fehlermeldung wegbekommen indem ich in den if-Bedingungen die beiden Bedingungen getauscht hab, dummerweise macht das Programm trotzdem nicht was es soll und gibt nur "99" aus, also dh es hat keinen Pfad gefunden und das gleich beim ersten Sprung... Das kann eigentlich nicht sein :wink: 
Kann mir wer helfen?


----------



## Leroy42 (15. Mai 2008)

Das kann doch gar nicht funktionieren!  :shock: 

Du hast weder eine Rekursion darin, noch eine Möglichkeit bei
nicht erfolgreichen Ansätzen den bisher gefundenen Weg wieder
rückgängig zu machen.


----------



## JosephineX (15. Mai 2008)

hmm sorry ich bin noch ziemlicher Anfänger
Also ich hab in der Zwischenzeit noch bisl dran rumgebastelt, da ist jetz auch ne Rekursion drin aber irgendwie kommt bei der Ausgabe ne Fehlermeldung:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
	at SpringerRek.position(SpringerRek.java:78)

Hier mal mein verbesserter (oder verschlechterter? :shock: ) Code


```
public class SpringerRek 
{
	static int n = 8;	//Feldgroesse
	static int x0 =0, y0=0;	//Startwerte
	static int[][] Jumper = new int[n*n][2];	//Springer
	static boolean[][] Frei = new boolean[n][n];//Feldbelegung
	
	
	public static int[][] position(/*int[][] akt,*/int x,int y,int zug)
	{
		if ((AufmFeld(x+2,y+1) == true) && (NochFrei(x+2,y+1) == true))		//Sprungmöglichkeiten
		{
			x = x+2;
			y = y+1;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((AufmFeld(x+2,y-1) == true) && (NochFrei(x+2,y-1) == true))
		{
			x = x+2;
			y = y-1;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((AufmFeld(x+1,y+2) == true) && (NochFrei(x+1,y+2) == true))
		{
			x = x+1;
			y = y+2;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((AufmFeld(x+1,y-2) == true) && (NochFrei(x+1,y-2) == true))
		{
			x = x+1;
			y = y-2;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((AufmFeld(x-1,y+2) == true) && (NochFrei(x-1,y+2) == true))
		{
			x = x-1;
			y = y+2;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((AufmFeld(x-1,y-2) == true) && (NochFrei(x-1,y-2) == true))
		{
			x = x-1;
			y = y-2;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((AufmFeld(x-2,y+1) == true) && (NochFrei(x-2,y+1) == true))
		{
			x = x-2;
			y = y+1;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else if ((AufmFeld(x-2,y-1) == true) && (NochFrei(x-2,y-1) == true))
		{
			x = x-2;
			y = y-1;
			Jumper[zug][0] = x;
			Jumper[zug][1] = y;
			return Jumper;
		}
		else 
		{
			SpringerRek.position(Jumper[zug-1][0],Jumper[zug-1][1],zug-1);
			return Jumper;
		}
	}
	
	public static boolean NochFrei(int aktX, int aktY)	//Testet ob das Feld noch frei ist
	{
		if (Frei[aktX][aktY] == true)
		{
			Frei[aktX][aktY] = false;
			return true;
		}
		else return false;
	}
	
	public static boolean AufmFeld(int x,int y)	//Testet ob der Springer sich noch aufm Feld befindet
	{
		if(x >= n) {return false;}	//Das Feld ist n*n gros, da Zählung bei 0 beginnt, mus x <= n-1 bleiben!
		if(x < 0) {return false;}
		if(y >= n) {return false;}
		if(y < 0) {return false;}
		else {return true;}	//Alles ok!
	}
	
	public static void main(String[] args)
	{
		for (int i = 0; i <= n-1; i++)		//erstmal alle Felder auf true setzen, dh hier war der Springer noch nit
		{
			for (int j = 0; j <= n-1; j++)
			{
				Frei[i][j] = true;
			}
		}
		SpringerRek.position(Jumper[0][0],Jumper[0][1],0);	//erster Sprung
		for (int znum = 1; znum <= (n*n)-1; znum++)
		{
			SpringerRek.position(/*Jumper,*/Jumper[znum-1][0],Jumper[znum-1][1],znum);
			System.out.println ("Sprung Nr " + znum + " x: " + Jumper[znum][0] + " y: " + Jumper[znum][1]);
		}
	}
}
```

Also jetz kommt ein Ergebnis aber dazu diese Meldung.. Irgendwie hab ich nicht so das Gefühl das ich richtig vorangekommen bin
Wie kann ich das berichtigen? Oder mus ich jetz n ganz neues Programm schreiben?


----------



## Marco13 (15. Mai 2008)

Methoden- und Variablennamen schreibt man klein (und das Ding heißt auf Englisch "Knight" :roll: )

Du musst dir bei jedem Zugriff auf einen Array überlegen, ob der index wirklich gültig ist (d.h. ob 0 <= index < array.length gilt). Insbesondere scheinst(!) du bei diesem Aufruf
SpringerRek.position(Jumper[zug-1][0],Jumper[zug-1][1],zug-1); 
eben man zug==0 zu haben, und geifst damit auf einen ungültigen index zu. Eigentlich wundert es mich aber schon fast, dass er nicht früher wegkachelt, weil die Abfragen wie "NochFrei(-1,-2)" zum gleichen Fehler führen sollten.


----------



## JosephineX (16. Mai 2008)

Also ich habs jetz nochmal bisl umgeschrieben, aber jetz kommt es ständig zum StackOverFlowError :shock: 

Dabei hab ich das doch mit den Abfragen ob der Springer sich nu noch aufm Feld befindet oder nicht eigentlich eingegrenzt, also ich bin mittlerweile verzweifelt

Hier mal mein neuer Code:


> import java.util.*;
> 
> public class SpringerRek
> {
> ...


----------



## Marco13 (16. Mai 2008)

Ich kapier' nicht, wie man (wenn man nicht schon "weiß, wie es geht") so ein Programm schreiben kann oder will oder können will, ohne sich debug-Ausgaben zu bauen...

```
private static String indent(int n)
    {
        String result = "";
        for (int i=0; i<n; i++)
        {
            result += "    ";
        }
        return result;
    }


    public static int[][] position(int x, int y, int zug)
    {
        System.out.println(indent(zug)+"position("+x+", "+y+", "+zug+")");

        while(zug <= (n * n) - 1)
        {
            ....
```


----------



## Marco13 (16. Mai 2008)

Noch so als Ergänzung: Ich hab' mir die "position"-Methode jetzt mal angeschaut, kann aber beim besten Willen nicht nachvollziehen, was dort gemacht werden soll. Was auch immer es ist: Man muss schon irgendwas zurückgeben, und irgendwann aufhören, und darf sie auch nicht bedingungslos aufrufen. Versuch' dir vielleicht mal GROB zu überlegen, wie die ablaufen muss:

```
boolean löse(int x, int y, int zugnummer)
{
    if (keine freien Zielfelder mehr) 
    {
        if (zugnummer == 64)
        {
            //hey, ich muss fertig sein! :-)
            return true;
        }
        // Hier geht's nicht weiter :-(
       return false;
    }
    else
    {
        // Probiere systematisch(!) alle möglichen Zielfelder durch
        for (alle Zielfelder)
        {
            setzeSpringerAuf(zielfeld);
            boolean fertig = löse(zielfeld.x, zielfeld.y, zugnummer+1);
            if (fertig)
            {
                // Ah, mit diesem Zielfeld bin ich irgendwie
                // zu einer Lösung gekommen!
                return true;
            }
            // Mit dem akutellen zielfeld hat's nicht geklappt. 
            // Better luck next time 
            nimmSpriegerWiederRunterVon(zielfeld);
        }
    }
    return false;
}
```

EDIT: Abbruchbedingung anders geschrieben.


----------



## Guest (16. Mai 2008)

Ich hab halt noch nicht viel programmiert, deshalb frag ich ja auch!
Trotzdem erstmal danke für die Antwort.

So ich hab das mal eingebaut, aber da liefert er mir irgendwelche Werte für x und y, zB position(6894, -3447, 0)
Also wenn ich das jetz richtig versteh ist das Problem das er nicht die richtigen x und y Werte bekommt und das er (warum auch immer) die zugnummer nicht erhöht und deshalb das Programm nicht beendet. Oder lieg ich da falsch?

Aber woran könnt das liegen? ich hab doch andere Startwerte in der Mainmethode vorgegeben?! :?


----------



## Marco13 (16. Mai 2008)

(Siehe Ergänzung oben)


----------



## JosephineX (16. Mai 2008)

Ah sorry den zweiten Post hab ich noch nicht gesehn gehabt


----------



## Guest (16. Mai 2008)

Das hat mir jetz schon sehr geholfen, vielen Dank an der Stelle!
Ich habs nach der Vorlage umgesetzt allerdings hab ich noch ein kleines Problem: Wie krieg ich die Ausgabe vernünftig hin? Er gibt mir für alle Sprünge nur
"Sprung Nr 3 x: 0 y: 0"
an. Weis da jemand noch weiter? 

Hier nochmal der Code:


```
import java.util.*;

public class SpringerRek 
{
	static int n = 8;	//Feldgroesse
	static int x0 =0, y0=0;	//Startwerte
	static int[][] Jumper = new int[n*n][2];	//Springer
	static boolean[][] Frei = new boolean[n][n];//Feldbelegung
	static int zufall =new Random().nextInt(80);
	static boolean done;
	
	
/*		private static String indent(int n)
	    {
	        String result = "";
	        for (int i=0; i<n; i++)
	        {
	            result += "    ";
	        }
	        return result;
	    }*/

		static boolean löse(int x, int y, int zug)
		{
		    if (zug == 65)	//Geschafft
		    {
		        return true;
		    }
		    if ((NochFrei(x+2,y+1) == false) && (NochFrei(x+2,y-1) == false) && (NochFrei(x+1,y+2) == false) && (NochFrei(x+1,y-2) == false) && (NochFrei(x-1,y+2) == false) && (NochFrei(x-1,y-2) == false) && (NochFrei(x-2,y+1) == false) && (NochFrei(x-2,y-1) == false))
		    {
		        // Hier geht's nicht weiter
			     return false;
		    }
		   
		    else
		    {
		    
		        // Probiere systematisch(!) alle möglichen Zielfelder durch
		    	done = false;
		        for (int i = 0; i == 7; i++)
		        {
		        	if (i == 0 && done == false)	//Falls Sprung noch nicht ausgeführt
		        	{
		        		if ((AufmFeld(x+2,y+1) == true) && (NochFrei(x+2,y+1) == true))      //Sprungmöglichkeiten
				        {
				           x = x+2;
				           y = y+1;
				           done = true;
				        }
		        	}
		        	if (i == 1 && done == false)	//Falls Sprung noch nicht ausgeführt
		        	{
		        		if ((AufmFeld(x+2,y-1) == true) && (NochFrei(x+2,y-1) == true))      //Sprungmöglichkeiten
				        {
				           x = x+2;
				           y = y-1;
				           done = true;
				        }
		        	}
		        	if (i == 2 && done == false)	//Falls Sprung noch nicht ausgeführt
		        	{
		        		if ((AufmFeld(x+1,y+2) == true) && (NochFrei(x+1,y+2) == true))      //Sprungmöglichkeiten
				        {
				           x = x+1;
				           y = y+2;
				           done = true;
				        }
		        	}
		        	if (i == 3 && done == false)	//Falls Sprung noch nicht ausgeführt
		        	{
		        		if ((AufmFeld(x+1,y-2) == true) && (NochFrei(x+1,y-2) == true))      //Sprungmöglichkeiten
				        {
				           x = x+1;
				           y = y-2;
				           done = true;
				        }
		        	}
		        	if (i == 4 && done == false)	//Falls Sprung noch nicht ausgeführt
		        	{
		        		if ((AufmFeld(x-1,y+2) == true) && (NochFrei(x-1,y+2) == true))      //Sprungmöglichkeiten
				        {
				           x = x-1;
				           y = y+2;
				           done = true;
				        }
		        	}
		        	if (i == 5 && done == false)	//Falls Sprung noch nicht ausgeführt
		        	{
		        		if ((AufmFeld(x-1,y-2) == true) && (NochFrei(x-1,y-2) == true))      //Sprungmöglichkeiten
				        {
				           x = x-1;
				           y = y-2;
				           done = true;
				        }
		        	}
		        	if (i == 6 && done == false)	//Falls Sprung noch nicht ausgeführt
		        	{
		        		if ((AufmFeld(x-2,y+1) == true) && (NochFrei(x-2,y+1) == true))      //Sprungmöglichkeiten
				        {
				           x = x-2;
				           y = y+1;
				           done = true;
				        }
		        	}
		        	if (i == 7 && done == false)	//Falls Sprung noch nicht ausgeführt
		        	{
		        		if ((AufmFeld(x-2,y-1) == true) && (NochFrei(x-2,y-1) == true))      //Sprungmöglichkeiten
				        {
				           x = x-2;
				           y = y-1;
				           done = true;
				        }
		        	}
		        	Jumper[zug][0] = x;	//Setze Springer auf Zielfeld
			        Jumper[zug][1] = y;
		            boolean fertig = löse(Jumper[zug][0], Jumper[zug][1] = y, zug+1);
		            if (fertig)
		            {
		                
		            	return true;
		            }
		            
		          //  nimmSpriegerWiederRunterVon(zielfeld);
		        }
		    }
		    return false;
		}
		

	
	
	public static boolean NochFrei(int aktX, int aktY)	//Testet ob das Feld noch frei ist
	{
		if (Frei[aktX][aktY] == true)
		{
			Frei[aktX][aktY] = false;
			return true;
		}
		else return false;
	}
	
	public static boolean AufmFeld(int x,int y)	//Testet ob der Springer sich noch aufm Feld befindet
	{
		if(x >= n) {return false;}	//Das Feld ist n*n gros, da Zählung bei 0 beginnt, mus x <= n-1 bleiben!
		if(x < 0) {return false;}
		if(y >= n) {return false;}
		if(y < 0) {return false;}
		else {return true;}	//Alles ok!
	}
	
	public static void main(String[] args)
	{
		
		for (int i = 0; i <= n-1; i++)		//erstmal alle Felder auf true setzen, dh hier war der Springer noch nit
		{
			for (int j = 0; j <= n-1; j++)
			{
				Frei[i][j] = true;
			}
		}
		SpringerRek.löse(Jumper[0][0],Jumper[0][1],0);	//erster Sprung
		for (int znum = 1; znum <= (n*n)-1; znum++)
		{
			//SpringerRek.position(Jumper[znum-1][0],Jumper[znum-1][1],znum);
			System.out.println ("Sprung Nr " + znum + " x: " + Jumper[znum][0] + " y: " + Jumper[znum][1]);
		}
	}
}
```


----------



## Marco13 (17. Mai 2008)

OK, ich habe ja gesagt, du solltest dir _überlegen_, wie der Ablauf sein sollte. Ganz grob, damit du SELBST weißt, was dort gemacht werden soll. (Die Alternative wäre ja, nach sowas wie "Java Knight OR Springer problem Lösung OR Solution" zu googlen.... :roll: ). Das sollte also insbesndere heißen, dass du das NICHT 1:1 abtippen solltest (obwohl das "fast" möglich sein sollte). Der Pseudocode sollte nur das Konzept verdeutlichen, und enthielt noch (mindestens :wink: ) einen kleinen Fehler, den ich aber kurz nach dem Post noch korrigiert hatte: Er versucht nie, einen 65. Zug zu machen, weil er dafür ja kein freies Zielfeld mehr finden kann. Die letzte Zugnummer (ist im editierten Post immernoch falsch und) müßte wohl 63 sein. (Das sind aber Details, die DU dir überlegen solltest).

Nochmal allgemein: Es gibt immer (unendlich) viele verschiedene Möglichkeiten, WIE genau man ein Programm implementieren kann. Insbesondere kann man unterschiedliche Schwerpunkte setzen (Eleganz, Allgemeinheit, Verständlichkeit, Kompaktheit ... etc). Man könnte das ganze vmtl. auch sehr elegant und kompakt schreiben, aber dann wäre es eher unverständlich. Ich hoffe, dass sowohl der schon gepostete Pseudocode, als auch alle übrigen Hinweise eher verständlich waren ... oder noch werden :wink:

Die Berechnung der Zielfelder (die ganzen "NochFrei"'s) machst du ja im Moment doppelt, und noch dazu ziemlich unelegant  :? Du könntest(!!!) eine Klasse "Position" machen, die x/y enthält, oder die Klasse java.awt.Point verwenden (oder notfalls einen 2-elementigen Array, was aber u.U. ein bißchen unübscher ist). Dann wäre eine Methode wie

```
List<Point> berechneDieListeDerFreienFelderDieErreichtWerdenKönnenVonPosition(int x, int y);
```
vielleicht hilfreich. Wenn du die dann am Anfang der "löse"-Methode aufrufst, beschränkt sich deine erste (laaaaaaange) if-Abfrage auf sowas wie

```
List<Point> zielfelder = berechneDieListeDerFreienFelderDieErreichtWerdenKönnenVonPosition(x,y);
if (zielfelder.size() == 0)
{
    ....
    // Hier geht's nicht weiter 
}
```
Und das anschließende Durchprobieren aller Zielfelder würde zu so einer einfachen Schleife wie

```
// Probiere systematisch(!) alle möglichen Zielfelder durch 
for (Point zielfeld : zielfelder)
{ 
    ....
}
```

Aber ob du so eine Methode schreibst, oder es "irgendwie anders" implementierst, ist deine Entscheidung!!!


Unabhängig davon: Irgendwo in deinem Code könnte(!!!) auch ein (oder mehrere) Arrays vorkommen wie

```
int offsets = new int[]{ -2, -1, 1, 2 };
```
mit deren Hilfe man dann ganz geschickt in 1 oder 2 kurzen Schleifen alle Zielfeld-Positionen berechnen kann. Aber das wäre dann "advanced", das müßte ich mir auch erst zusammenklamüsern .... du kannst auch erstmal alle Zielfelder "per Hand" hinschreiben (den Code dafür hast du ja im Prinzip schon). Insbesondere weil es offenbar noch an Basics hakt:

```
for (int i = 0; i == 7; i++)
```
Diese Abbruchbedingung solltest du dir nochmal genau ansehen - und nochmal überlegen/nachlesen/nachvollziehen, WAS eine for-Schleife macht, und WIE genau sie funktioniert.


----------



## JosephineX (17. Mai 2008)

Puh also ich hab jetz alles nochmal kräftig den Code überarbeitet, und es funktioniert jetzt!  
Also ich hatte auf jeden Fall noch einige üble Fehler drin, vor allem in der for-Schleife, also danke Marco13 für deinen Hinweis!  
Ich werd jetz mal das häkchen setzen das das hier erledigt ist, wenn ich rausfinde wie das geht^^
Soll ich den korrekten Code nochmal posten für evtl andere Leute mit ähnlichem Problem? 

Also wie gesagt danke für die Hilfe, wenn ich mal wieder ein Problem hab werd ich mich melden :wink:


----------



## voidee (20. Mai 2008)

da sind viel zu viele if-Bedingungen in dem Code

Stell die Kombinationen mal in int-Arrays ein und durchlaufe das ganze in einer Schleife....


----------



## Marco13 (20. Mai 2008)

Vielleicht hat er das nach den letzten Hinweisen ja noch verbessert. (Zumindest zielten die Hinweise unter anderem (!) genau darauf ab...). @JosephineX: Kannst ja mal den "finalen" Code posten, dann bekommst du noch gesagt, wie man es mit 100 Zeilen weniger und doppelt so schnell hätte machen können. Und mit 10 Zeilen mehr dann wieder 10 Millionen mal so schnell :wink: ich kann mir nämlich kaum vorstellen, dass das Brute-Force-Backtracking OHNE sowas wie die "Warnsdorf-Heuristik" _überhaupt_ in vertretbarer Zeit eine Lösung liefert.... ???:L


----------

