Springer auf Schachbrett

[isoMike09]

Hi @ all,
hab folgendes Problem.
Ich hab eine Aufgabe gefunden, bei der ich ein Schachbrett programmieren soll und die Züge eines Springers. Ich muss auf dem Brett (2D-Array) alle Züge abbilden.
Ich geb als Startwert die Stelle des Springers auf dem Schachbrett an
Z.B.: 3 / 5 (also die Koordinaten)
Die Ausgabe soll für dieses Beispiel dann so aussehen:

2 3 4 1 2 1 4 3
3 2 1 2 3 2 1 2
2 3 2 3 0 3 2 3
3 2 1 2 3 2 1 2
2 3 4 1 2 1 4 3
3 2 3 2 3 2 3 2
4 3 2 3 2 3 2 3
3 4 3 4 3 4 3 4

Bei 0 befindet sich momentan der Springer. Die Felder mit 1 zeigen an, auf welche Felder ich mit einem Zug hinkomme, Felder mit 2 mit zwei Zügen usw...

Mein code sieht soweit so aus:

public class Matrix {

	//private int x,y;
	private int a,b;
	private int springer[][];
	
	public Matrix(int z, int s)
	{
		springer = new int[z][s];
		a = z;
		b = s;
	}
	
	
	public void springer(int x,int y)
	{	y += 1;
		x += 1;
		
		springer[x][y]=3; //anstatt 3 eig. 0, aber lässt sich sonst nicht differenzieren
		
		springer[x+1][y+2]=1;
		springer[x+1][y-2]=1;
		springer[x-2][y+1]=1;
		springer[x-2][y-1]=1;
		springer[x+2][y-1]=1;
		springer[x+2][y+1]=1;
		springer[x-1][y+2]=1;
		springer[x-1][y-2]=1;
	
	}

Den Rumpf der Methode Spirnger muss ich irgendwie in eine Schleife packen, da diese 8 Anweisungen nur für ein Startwert gelten. Nur ich komm nicht drauf.

Ausgabe wäre dann:

0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0
0 1 0 0 0 1 0 0
0 0 0 3 0 0 0 0
0 1 0 0 0 1 0 0
0 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Ausgabemethode:

public void ausgeben()
	{
		
		for(int i=2; i<a-2;i++)
		{	System.out.println();
			for(int j=2; j<b-2;j++)
			{	
				System.out.print(springer[i][j]+" ");
			}
		}	
	}

Und Main:

public class Main {


	public static void main(String[] args) {
	
		Matrix m1 = new Matrix(12,12);
		
		m1.springer(3,5);
		m1.ausgeben();
	}

}

12*12 deshalb ja, da ich es ja auch sein kann, dass der Spirger auserhalb des 8*8 Feldes liegen kann. Nur wird das nicht ausgegeben (s. ausgabe()).
Vielen Dank im Voraus.

 

[Marco13]

EDIT2: Häm - kann sein dass das so nicht ganz stimmt. Aber vielleicht findest du ja den Fehler, und kannst ihn selbst beheben

Das schreit ja förmlich nach Rekursion

Pseudocode

setzeNummern(int x, int y, int feld[][], int aktuelleNummer)
{
    feld[x][y] = aktuelleNummer;
    erreichbareFelder = berechneErreichbareFelderVon(x,y);
    Wenn erreichbareFelder leer ist, return;
    andernfalls
    {
        for (alle erreichbarenFelder nx, ny)
        {
            setzeNummern(nx,ny,feld,aktuelleNummer+1);
        }
    }
}

Aufruf mit
setzeNummern(3,5,feld,0);


EDIT: So als nachtrag: Den Rumpf einfach in eine Schleife packen würde so nicht funktionieren - du musst noch die ganzen Array-Indizes abfragen (um eine ArrayIndexOutOfBoundsException zu vermeiden). Bei der rekursiven Lösung steckt das implizit in der Berechnung der Liste der erreichbarenFelder.

 

[isoMike09]

super...vielen Dank.
Komisch ist nur, dass erst nach der Aufgabenstellung (im weiteren Verlauf des Kapitels) die Rekursion besprochen wird..

 

[Marco13]

Das EDIT2 hattest du gesehen? Also, wenn man den Pseudocode 1:1 hinschreibt, kommt, wenn ich mich nicht täusche, u.U. nicht das richtige Ergebnis raus...

 

[isoMike09]

hab ich gesehen...bin am probieren..vielen Dank.

 

[isoMike09]

erreichbareFelder

...ist dann eine Liste? Bzw. welcher Datentyp?

 

[Marco13]

Ja, ein Array oder eine Liste, z.B. eine List<Point> oder so...

 

[isoMike09]

Bei einem Array bräuchte ich dann ein 3Dimensionales oder? da ich ja die Koordinaten speichern muss, die die erreichbaren Stellen zeigen.?

 

[Marco13]

Man braucht nie mehr als ein 1D-Array. Man könnte einen 2D-Array zurückgeben

int positions[][] = new int[2][];
positions[0] = new int[]{3,5};
positions[1] = new int[]{4,6};
return positions;

oder einen 1D array

int positions[] = new int[2*2];
positions[0*2+0] = 3; positions[0*2+1] = 5;
positions[1*2+0] = 4; positions[1*2+1] = 6;

oder (was eigentlich am "Schönsten" wäre) eine Liste von Objekten einer Klasse "Position", die das x und y speichert und über get-Methoden anbietet...

 

[isoMike09]

okay...also dann sowas in der Art?:

Feld f1 = new Feld(x+1,y+2);
Feld f2 = new Feld(x+1,y-2)
Feld f3 = new Feld(x+2,y-1);
Feld f4 = new Feld(x+2,y+1);
Feld f5 = new Feld(x-2,y-1);
Feld f6 = new Feld(x-2,y+1);
Feld f7 = new Feld(x-1,y+2);
Feld f8 = new Feld(x-1,y-2);
felder.add(f1);
felder.add(f2);
felder.add(f3);
felder.add(f4);
felder.add(f5);
felder.add(f6);
felder.add(f7);
felder.add(f8);

Dann hätt ich doch eine Liste die mir die Felder zeigt, auf denen der Springer mit einem Zug hinkommt...diese Bau ich dann in die rekursive Methode später ein?

 

[Marco13]

Ja genau. Nur sollten in diese Liste halt nur die Felder, die er wirklich erreichen kann, d.h. die die wirklich im 8x8-Feld liegen, und noch nicht besucht wurden.

Aber zu der rekursiven Methode sorry, bevor du da jetzt dran verzweifelst, nochmal: Ich hatte die Aufgabenstellung ("Wunschdenken") falsch interpretiert. Dieses Problem ist mit der rekursiven Methode nicht so gut zu lösen. Die Methode für das Berechnen der erreichbaren Felder brauchst du in jedem Fall, aber da hier (um's mal so zu sagen) keine Tiefen- sondern eine Breitensuche gemacht werden soll, verwendet man keinen Stack sondern eine Queue - oder als Pseudocode

    public void springer(int x,int y)
    {
        springer[x][y] = 0;
        int aktuelleNummer = 1;
        erreichbareFelder = berechneErreichbareFelderVon(x,y);
        Solange es erreichbare Felder gibt
        {
            Setze auf alle erreichbaren Felder die aktuelle nummer

            Berechne die Menge aller Felder, die von den aktuell erreichbaren
                Feldern aus erreichbar sind, und speichere diese als die neuen
                erreichbaren Felder
            
            aktuelleNummer++
        }
    }

 

[isoMike09]

Ja genau. Nur sollten in diese Liste halt nur die Felder, die er wirklich erreichen kann, d.h. die die wirklich im 8x8-Feld liegen, und noch nicht besucht wurden.
[/code]

-> meine 8 add's sind ja die Felder die bei einem Feld von einem Springer erreicht werden können, oder?

 

[Marco13]

Hmja, aber wenn er z.B. bei (x,y) = (6,7) loshüpft, dann wäre
Feld f1 = new Feld(x+1,y+2);
ja bei (7,9), und das liegt außerhalb des Spielfeldes. Man müßte bei jedem Feld prüfen, ob x und y jeweils >= 0 und <8 sind. Außerdem muss man überprüfen, ob das Feld schon besucht wurde, sonst setzt man z.B. bei (3,5) eine 1, hüpft dann nach (5,6) und setzt dort eine 2, hüpft dann wieder nach (3,5) und setzt eine 3 ....

 

[isoMike09]

Und was ist wenn ich das 8*8 Feld zu einem 12*12 Feld mache und nur 8*8 ausgebe?

 

[Marco13]

Dann hüpft er von (7,7) nach (9,8) und ist noch nicht außerhalb des Feldes, aber wenn er dann von (9,8) nach (11,9) hüpft, ist er DOCH wieder draußen - das verschiebt das Problem nur. Es sollen ja alle Züge ausgeführt werden - und die sind nur durch den Rand des Spielfeldes begrenzt.

 

[isoMike09]

HI,

also hab deinen Pseudocode so gut ich konnte mal befolgt.
Hab folgenden Code generiert, der aber noch nicht passt.

public void berErFelder(int h,int g)
	{	
		
		position[0]=new int[]{h+1,g+2};
		position[1]=new int[]{h+1,g-2};
		position[2]=new int[]{h+2,g-1};
		position[3]=new int[]{h+2,g+1};
		position[4]=new int[]{h-2,g-1};
		position[5]=new int[]{h-2,g+1};
		position[6]=new int[]{h-1,g+2};
		position[7]=new int[]{h-1,g-2};
		
		for(int t=0;t<8;t++)
		{	
			springer[position[t][0]][position[t][1]]=lfd;
		}
	}

public void springer(int x, int y)
	{	
		berErFelder(x+1,y+1); 
		
		for(int i=2; i<a-2;i++)
			for(int j=2; j<b-2;j++)
			{
				if(springer[i][j]==lfd)
				{
					berErFelder(i,j); // hier steckt der Fehler lfd ist meine aktuelle Nummer
				}
			}
		
	}

public void ausgeben()
	{
		for(int i=2; i<a-2;i++)
		{	System.out.println();
			for(int j=2; j<b-2;j++)
			{	
				System.out.print(springer[i][j]+" ");
			}
		}		
	}

public class Main {


	public static void main(String[] args) {
	
		Matrix m1 = new Matrix(12,12);
		// 12*12 mach ich deshalb, da ich immer alle
               // erreichbaren Felder von jedem Feld errechne aber nur das 8*8 Feld         ausgebe 
		m1.springer(3,5);
	
		m1.ausgeben();
		
	}
}

 

[isoMike09]

So hab ich sogar schon Felder mit einem und zwei Zügen:

	public void springer(int x, int y)
	{	
		berErFelder(x+1,y+1); 
		lfd++;
		for(int i=2; i<a-2;i++)
			for(int j=2; j<b-2;j++)
			{
				if(springer[i][j]==lfd-1)
				{	
					berErFelder(i,j); 
				}
			}
		springer[x+1][y+1]=0;
	}

Ausgabe:
2 0 0 1 2 1 0 0
0 2 1 2 0 2 1 2
2 0 2 0 0 0 2 0
0 2 1 2 0 2 1 2
2 0 0 1 2 1 0 0
0 2 0 2 0 2 0 2
0 0 2 0 2 0 2 0
0 0 0 0 0 0 0 0

 

[isoMike09]

Soooo hab nun endlich nach tüfteln und gutem Überlegen die Lösung:
Hab eine Prüfung vergessen beim Errechnen der erreichbaren Felder:

public void berErFelder(int h,int g)
	{	
		
		position[0]=new int[]{h+1,g+2};
		position[1]=new int[]{h+1,g-2};
		position[2]=new int[]{h+2,g-1};
		position[3]=new int[]{h+2,g+1};
		position[4]=new int[]{h-2,g-1};
		position[5]=new int[]{h-2,g+1};
		position[6]=new int[]{h-1,g+2};
		position[7]=new int[]{h-1,g-2};
		
		for(int t=0;t<8;t++)
		{	
			if(springer[position[t][0]][position[t][1]] == 0) // die Prüfung
			springer[position[t][0]][position[t][1]]=lfd;
		}
		
	}

sonst überschreibt er mir ja die vorherigen Züge...
meine springer-Methode sieht so aus (auch wenn sie vielleicht ziemlich umständlich ist):

public void springer(int x, int y)
	{	
		berErFelder(x+1,y+1); 
		for(int t=0;t<8;t++){
		lfd++;
		for(int i=2; i<a-2;i++)
			for(int j=2; j<b-2;j++)
			{
				if(springer[i][j]==lfd-1)
				{	
					berErFelder(i,j); 
				}
			}}
		springer[x+1][y+1]=0;	
	}

Meine Ausgabe passt dann endlich:
2 3 4 1 2 1 4 3
3 2 1 2 3 2 1 2
2 3 2 3 0 3 2 3
3 2 1 2 3 2 1 2
2 3 4 1 2 1 4 3
3 2 3 2 3 2 3 2
4 3 2 3 2 3 2 3
3 4 3 4 3 4 3 4

 

[Landei]

in berErFelder:

int i = 0
for(int x = -2; x <= 2; x++) {
  for(int y = -2; y <= 2; y++) {
     if(x*x+y*y == 5) {
       position[i++]=new int[]{h+x, g+y};
     }
  }
}

Übrigens: Warum nimmst du für die Position nicht einfach java.awt.Point oder so? Dann werden die ganzen Arrays eindimensional.