J
JavaAPP
Gast
Habe mich mal an ein Spiel (Zahlen-Springen) herangewagt, bei dem ich ein Problem habe.
Zum Spiel: Auf einem sechseckigen Spielbrett (Werte,siehe Quellcode) soll ein Spielstein so viele Felder in gerader Linie weiterspringen, wie die Zahl auf dem Feld, auf dem er steht, angibt. Begonnen wird auf dem Feld in der Mitte (3). Der Anfangszug darf in eine beliebige der sechs möglichen Richtungen erfolgen. Bei jedem weiteren Zug darf jeweils nur in derselben Richtung weitergehüpft werden - oder in eine rechts oder links benachbarte Richtung. Die Hüpferei ist erfolgreich zu Ende, wenn das Ausgangsfeld wieder erreicht wird.
Richtungen: NW,NO,W,O,SW;SO
Aufgabe: Schreibe ein ´Programm, welches einen erfolgreichen Hüpfweg sucht und ein Protokoll des Weges ausgibt.
Zum Finden eines Weges wird das Speilbrett systematisch durchsucht, und zwar rekursiv. Dabei wird jedoch eine Einschränkung beachtet: Ein Feld darf in einem Hüpfweg nicht zweimal von der gleichen Richtung kommend betreten werden. Damit werden möglicherweise endlose Rundläufe vermieden.
Zum Spiel: Auf einem sechseckigen Spielbrett (Werte,siehe Quellcode) soll ein Spielstein so viele Felder in gerader Linie weiterspringen, wie die Zahl auf dem Feld, auf dem er steht, angibt. Begonnen wird auf dem Feld in der Mitte (3). Der Anfangszug darf in eine beliebige der sechs möglichen Richtungen erfolgen. Bei jedem weiteren Zug darf jeweils nur in derselben Richtung weitergehüpft werden - oder in eine rechts oder links benachbarte Richtung. Die Hüpferei ist erfolgreich zu Ende, wenn das Ausgangsfeld wieder erreicht wird.
Richtungen: NW,NO,W,O,SW;SO
Aufgabe: Schreibe ein ´Programm, welches einen erfolgreichen Hüpfweg sucht und ein Protokoll des Weges ausgibt.
Zum Finden eines Weges wird das Speilbrett systematisch durchsucht, und zwar rekursiv. Dabei wird jedoch eine Einschränkung beachtet: Ein Feld darf in einem Hüpfweg nicht zweimal von der gleichen Richtung kommend betreten werden. Damit werden möglicherweise endlose Rundläufe vermieden.
Code:
public class Matr {
static int Brett [][] = {{2,4,1,5,4,0,0,0,0}, //Werte des Spielbretts
{1,4,5,2,3,2,0,0,0},
{2,1,3,3,2,5,2,0,0},
{2,1,3,2,1,2,2,4,0},
{4,3,4,3,3,4,2,3,2},
{0,2,2,1,3,2,2,1,2},
{0,0,2,2,2,3,4,3,2},
{0,0,0,1,3,1,2,1,4},
{0,0,0,0,2,1,6,3,2}
};
public static abstract class Directions
{
public static final int O = 0;
public static final int SO = 1;
public static final int SW = 2;
public static final int W = 3;
public static final int NW = 4;
public static final int NO = 5;
}
public static final String O = "O";
public static final String SO = "SO";
public static final String SW = "SW";
public static final String W = "W";
public static final String NW = "NW";
public static final String NO = "NO";
public static final String bezeichner[] = {O, SO,SW,W,NW,NO};
int []B = new int [100];
static int bewegung [][] = {{1,0},{1,1},{0,1},{-1,0},{-1,-1},{0,-1}}; // dx und dy der sechs Bewegungsrichtungen
static int weg [][] = new int [100][2]; // speichert den gegangenen Weg
static int besucht [][] = new int [9][9]; // benötigt zur Markierung besuchter Felder
public static void suche (int x, int y , int ausrichtung, int tiefe)
{
int z =0;
int newx=0;
int newy=0;
if (x==4 && y==4 && tiefe!=0)
{
for (z=0; z < tiefe; z++)
{
System.out.println (weg[z][1]);
System.out.println ( bezeichner [weg[z][0]] );
System.out.println (z < tiefe -1 ?" ," :"\n");
}
}
// Fortsetzung der Suche in alle drei möglichen Richtungen
for (z= (ausrichtung + 5)%6;
z!=(ausrichtung +2)%6;
z= (z + 1)%6) ;
{
weg [tiefe][0]=z; // Speichern von Ausrichtung und
weg [tiefe][1]= Brett [y][x]; // Sprungweite für spätere Ausgabe
newx = x + Brett [y][x]*bewegung[z][0]; //neue x-Koordinate
newy = y + Brett [y][x]*bewegung[z][1]; //neue y-Koordinate
//Prüfung, ob die neue Position innerhalb des Bretts leigt
// unf noch nicht in gleiche Richtung gegangen worden ist:
if ( newx >=0 && newy >=0 && newx<=8 && newy <=8 )
{
if (Brett [newy] [newx] != (besucht [newy] [newx]) )
{
if (Brett [newy] [newx] != 1<<z)
{
besucht [newy][newx] ^=1<<z; //Markierung setzen
suche (newx, newy,z,tiefe+1); //rekursiver Aufruf
besucht [newy][newx] ^=1<<z; //Markierung entfernen
}
}
}
}
}
public static void main(String[] args) {
suche (4,4,Directions.O,0); //Aufruf für die Startrichtung NO,O,SO
suche (4,4,Directions.W,0); //und zweiter Aufruf für NW,W,SW
}
}