/* Alle Rechte vorbehalten. */
/* (C)opyright 1999 by Mathias Retzlaff, Stefan Roehrich, Daniel Heck, Hendrik Dahlkamp*/
/* Version 2.3.42 -- Release 3 */
class genugLoesungenException extends Exception {
}
/* Def.: Zwei Felder heissen Nachbarn, wenn sie sich roesseln. */
class Springer {
static int temp1=0, temp2=0;
static final boolean O = false;
static final boolean X = true;
// Das Schachbrett: Welches Feld wurde schon besucht ?
static boolean brett[] =
{ X,X, X,X,X,X,X,X,X,X ,X,X,X,X,X,X,
X,X, X,X,X,X,X,X,X,X ,X,X,X,X,X,X,
X,X, X,O,O,O,X,O,X,X ,X,X,X,X,X,X,
X,X, O,O,O,O,O,X,X,O ,X,X,X,X,X,X,
X,X, O,X,O,X,O,X,X,X ,X,X,X,X,X,X,
X,X, O,O,O,O,O,X,O,X ,X,X,X,X,X,X,
X,X, X,O,X,O,O,O,O,O ,X,X,X,X,X,X,
X,X, X,O,X,O,O,O,X,O ,X,X,X,X,X,X,
X,X, O,X,O,O,O,X,O,O ,X,X,X,X,X,X,
X,X, O,X,O,X,O,O,O,X ,X,X,X,X,X,X,
X,X, X,X,X,X,X,X,X,X, X,X,X,X,X,X,
X,X, X,X,X,X,X,X,X,X, X,X,X,X,X,X };
// Die Anzahl der verschiedenen Eimer fuer Bucketsort
static final int maxWert = 11;
// mit Unterstrich fuer den langsamen Algo.
static final int _maxWert = 4;
// Ein Konstanten-Feld zur Speicherung des Abstandes eines Feldes
// zum Rand.
static final byte rand[] =
{ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,
0,0,1,2,4,2,2,2,2,1,0,0,0,0,0,0,
0,0,1,2,3,3,3,3,2,1,0,0,0,0,0,0,
0,0,1,2,3,4,4,3,2,1,0,0,0,0,0,0,
0,0,1,2,3,4,4,3,2,1,0,0,0,0,0,0,
0,0,1,2,3,3,3,3,2,1,0,0,0,0,0,0,
0,0,1,2,2,2,2,2,2,1,0,0,0,0,0,0,
0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
// Ein Feld zur Speicherung der Anzahl der freien Nachbarn
// eines Feldes
static final byte verbindung[] =
{ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,2,3,4,4,4,4,3,2,0,0,0,0,0,0,
0,0,3,4,6,6,6,6,4,3,0,0,0,0,0,0,
0,0,4,6,8,8,8,8,6,4,0,0,0,0,0,0,
0,0,4,6,8,8,8,8,6,4,0,0,0,0,0,0,
0,0,4,6,8,8,8,8,6,4,0,0,0,0,0,0,
0,0,4,6,8,8,8,8,6,4,0,0,0,0,0,0,
0,0,3,4,6,6,6,6,4,3,0,0,0,0,0,0,
0,0,2,3,4,4,4,4,3,2,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
//Die Eimer fuer Bucketsort
static byte eimer [][][];
//Zur Speicherung des Fuellgrades der Eimer
static byte eimerAnzahl [][];
// Die verschiedenen Zuege die ein Springer machen kann in (delta X) und (delta Y)
static final int zuege[][] = { {-2,-1} , {-1,-2} , {+1,-2} , {+2,-1} , {+2,+1} , {+1,+2} , {-1,+2} , {-2,+1} };
// Das gleiche fuer ein 1D Feld berechnet
static final int zuege2 [] = { -2-(1 << 4) , -1-(2 << 4) , +1-(2 << 4) , +2-(1 << 4) , +2+(1<<4) , +1+(2 << 4) ,
-1+(2 << 4) , -2+(1 << 4) };
// Die 3 Moeglichkeiten fuer die ersten 9 Zuege.
static final int anfang1[][][] = { {{2,2}, {3,4}, {2,6}, {4,7}, {3,9}, {2,7}, {4,6}, {3,8}, {5,9}, {7,8}},
{{2,2}, {3,4}, {2,6}, {3,8}, {4,6}, {2,7}, {3,9}, {4,7}, {5,9}, {7,8}},
{{2,2}, {3,4}, {4,6}, {2,7}, {3,9}, {4,7}, {2,6}, {3,8}, {5,9}, {7,8}} };
// Die 6 Moeglichkeiten fuer die folgenden 11 Zuege.
static final int anfang2[][][] = { {{9,9}, {8,7}, {7,5}, {9,4}, {8,2}, {7,4}, {9,5}, {8,3}, {6,2}, {5,4}, {7,3}},
{{9,9}, {8,7}, {9,5}, {8,3}, {7,5}, {9,4}, {8,2}, {7,4}, {6,2}, {5,4}, {7,3}},
{{9,9}, {8,7}, {9,5}, {7,4}, {8,2}, {9,4}, {7,5}, {8,3}, {6,2}, {5,4}, {7,3}},
{{9,9}, {8,7}, {9,5}, {8,3}, {6,2}, {7,4}, {8,2}, {9,4}, {7,5}, {5,4}, {7,3}},
{{9,9}, {8,7}, {7,5}, {5,4}, {6,2}, {8,3}, {9,5}, {7,4}, {8,2}, {9,4}, {7,3}},
{{9,9}, {8,7}, {9,5}, {8,3}, {7,5}, {5,4}, {6,2}, {7,4}, {8,2}, {9,4}, {7,3}} };
// Feld zum Speichern einer gefundenen Loesung
static int loesung[][];
// Wieviele Loesungen wurden schon gefunden ?
static long anzahl=0;
// Wieviele Loesungen sollen gefunden werden ?
// Soll eine Ausgabe erfolgen ?
// Soll nach <max> Loesungen abgebrochen werden ?
static long max = 1000000;
static boolean ausgeben = false;
static boolean abbrechen = false;
// Second: Besteht Zugzwang ?
// zugZwang: Wenn ja: Wohin ?
static boolean second=false;
static int zugZwang=0;
/** Diese Methode markiert die vorbesetzen Zuege in dem Feld
* der freien Nachbarn als belegt.
* @param a xKoordinate des zu ueberspringenden Feldes
* @param b yKoordinate des zu ueberspringenden Feldes
*/
public static void setzeSpringer(int a, int b) {
int k=0;
for(int y=2; y<10; y++)
for(int x=2; x<10; x++)
if((x!=a) || (y!=b)){
k = x+(y << 4);
if(brett[k]) {
for(int i=0; i<8; i++)
verbindung[k+zuege2[i]]--;
}
}
verbindung[4+(3 << 4)]++;
}
/** Diese Methode gibt fuer eine gefundene Loesung alle 288
* aus ihr erzeugbaren aus. (bzw. zaehlt halt nur mit )
*/
public static void gibLoesungAus() throws genugLoesungenException{
if(ausgeben) {
for(int q=0; q<3; q++) {
for(int k=0; k<10; k++) {
loesung[k][0] = anfang1[q][k][0];
loesung[k][1] = anfang1[q][k][1];
}
for(int j=0; j<6; j++) {
for(int k=0; k<11; k++) {
loesung[k+10][0] = anfang2[j][k][0];
loesung[k+10][1] = anfang2[j][k][1];
}
// normal
System.out.print(""+(++anzahl)+": ");
for(int i=0; i<64; i++)
System.out.print( ""+(char)(loesung[i][0]-2+'A')+(loesung[i][1]-1)+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// gespiegelt
System.out.print(""+(++anzahl)+": ");
for(int i=0; i<64; i++)
System.out.print( ""+(char)(loesung[i][1]-2+'A')+(loesung[i][0]-1)+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// rueckwaerts
System.out.print(""+(++anzahl)+": ");
for(int i=64; i>0; i--)
System.out.print( ""+(char)(loesung[i][0]-2+'A')+(loesung[i][1]-1)+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// rueckwaerts & gespiegelt
System.out.print(""+(++anzahl)+": ");
for(int i=64; i>0; i--)
System.out.print( ""+(char)(loesung[i][1]-2+'A')+(loesung[i][0]-1)+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// *******************************************
// *** Das ganze nochmal 180 grd gedreht ! ***
// *******************************************
// normal
System.out.print(""+(++anzahl)+": ");
for(int i=0; i<64; i++)
System.out.print( ""+(char)(9-loesung[(i+10) % 64][0]+'A')+(10-loesung[(i+10) % 64][1])+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// gespiegelt
System.out.print(""+(++anzahl)+": ");
for(int i=0; i<64; i++)
System.out.print( ""+(char)(9-loesung[(i+10) % 64][1]+'A')+(10-loesung[(i+10) % 64][0])+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// rueckwaerts
System.out.print(""+(++anzahl)+": ");
for(int i=64; i>0; i--)
System.out.print( ""+(char)(9-loesung[(i+10) % 64][0]+'A')+(10-loesung[(i+10) % 64][1])+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// rueckwaerts & gespiegelt
System.out.print(""+(++anzahl)+": ");
for(int i=64; i>0; i--)
System.out.print( ""+(char)(9-loesung[(i+10) % 64][1]+'A')+(10-loesung[(i+10) % 64][0])+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// *******************************************
// *** Das ganze um 90 grd links gedreht ! ***
// *******************************************
// normal
System.out.print(""+(++anzahl)+": ");
for(int i=0; i<64; i++)
System.out.print( ""+(char)(9-loesung[(i+21) % 64][0]+'A')+(loesung[(i+21) % 64][1]-1)+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// gespiegelt
System.out.print(""+(++anzahl)+": ");
for(int i=0; i<64; i++)
System.out.print( ""+(char)(loesung[(i+21) % 64][1]-2+'A')+(10-loesung[(i+21) % 64][0])+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// rueckwaerts
System.out.print(""+(++anzahl)+": ");
for(int i=64; i>0; i--)
System.out.print( ""+(char)(9-loesung[(i+21) % 64][0]+'A')+(loesung[(i+21) % 64][1]-1)+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// rueckwaerts & gespiegelt
System.out.print(""+(++anzahl)+": ");
for(int i=64; i>0; i--)
System.out.print( ""+(char)(loesung[(i+21) % 64][1]-2+'A')+(10-loesung[(i+21) % 64][0])+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// ********************************************
// *** Das ganze um 90 grd rechts gedreht ! ***
// ********************************************
int ecke=21;
while( (loesung[ecke][0] != 2) || (loesung[ecke][1] != 9))
ecke++;
// normal
System.out.print(""+(++anzahl)+"!: ");
for(int i=0; i<64; i++)
System.out.print( ""+(char)(loesung[(i+ecke) % 64][0]-2+'A')+(10-loesung[(i+ecke) % 64][1])+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// gespiegelt
System.out.print(""+(++anzahl)+": ");
for(int i=0; i<64; i++)
System.out.print( ""+(char)(9-loesung[(i+ecke) % 64][1]+'A')+(loesung[(i+ecke) % 64][0]-1)+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// rueckwaerts
System.out.print(""+(++anzahl)+": ");
for(int i=64; i>0; i--)
System.out.print( ""+(char)(loesung[(i+ecke) % 64][0]-2+'A')+(10-loesung[(i+ecke) % 64][1])+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
// rueckwaerts & gespiegelt
System.out.print(""+(++anzahl)+": ");
for(int i=64; i>0; i--)
System.out.print( ""+(char)(9-loesung[(i+ecke) % 64][1]+'A')+(loesung[(i+ecke) % 64][0]-1)+" " );
System.out.println("A1");
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
}
}
} else {
// die 18 Loesungen: normal, gespiegelt, rueckwaerts und rueckwaerts&gespiegelt
// 180 grd gedreht !
// die 18 Loesungen: normal, gespiegelt, rueckwaerts und rueckwaerts&gespiegelt
// 90 grd links gedreht !
// die 18 Loesungen: normal, gespiegelt, rueckwaerts und rueckwaerts&gespiegelt
// 90 grd rechts gedreht !
// die 18 Loesungen: normal, gespiegelt, rueckwaerts und rueckwaerts&gespiegelt
anzahl += ( 18*4 ) * 4;
}
if (abbrechen && (anzahl >= max)) { throw new genugLoesungenException(); }
}
/** Diese Methode beurteilt ob ein Zug eine Sackgasse ist oder nicht.
* Gleichzeitig bereitet sie auch die Entscheidung, welcher Zug
* als naechster zu waehlen ist vor.
* @param x xKoordinate der aktuellen Position
* @param y yKoordinate der aktuellen Position
* @param moves Anzahl der schon durchgefuehrten Zuege.
* @return Sackgasse => false ; Zug okay => true
*/
public final static boolean scanBrett(int x, int y, int moves) {
// Das Feld C2 darf erst als letztes besetzt werden !
if( brett[4+(3 << 4)])
return false;
byte tempRand=0;
int rueckSetzen=0;
second = false;
// Alle eimer leeren !
for(int m=1; m<maxWert+1; m++)
eimerAnzahl[moves][m] = 0;
int pos = x + (y << 4);
try {
// Fuer alle acht Felder die von der aktuellen Pos. erreichbar sind
// einen freien Nachbarn abziehen, und dann
// bestimmen , wieviele frei Nachbarn sie nun noch haben !
// Falls es ein Feld gibt mit nur noch einem freien Nachbarn, besteht Zugzwang !
// Falls es mehr als eins gibt, ist es eine Sackgasse !
for(int m=0; m<8; m++) {
temp1 = pos+ zuege2[m];
if(!brett[temp1]) {
if( (--verbindung[temp1]) == 1 )
if(second) {
rueckSetzen=m+1;
return false;
} else {
second = true;
zugZwang = m;
}
else {
// Die Eimer fuellen! Kriterium: FreieNachbarn + Entfernung zum Rand
tempRand = (byte)(verbindung[temp1]+rand[temp1]);
eimer [moves] [tempRand] [eimerAnzahl[moves] [tempRand] ] = (byte)m;
eimerAnzahl[moves][tempRand]++;
}
}
}
} finally {
// Falls es eine Sackgasse war: Den schon geaenderten Feldern, den
// freien Nachbarn zurueckgeben.
if(rueckSetzen!=0) {
for(int m=0; m<rueckSetzen; m++)
if(!brett[pos+zuege2[m]])
verbindung[pos+zuege2[m]]++;
}
}
return true;
}
/** Diese Methode beurteilt ob ein Zug eine Sackgasse ist oder nicht.
* Der einzige Unterschied zur vorhergehenden Methode ist, dass hier
* kein BucketSort mehr benutzt wird, da sich das ab einem bestimmten Zug
* nicht mehr lohnt.
* @param x xKoordinate der aktuellen Position
* @param y yKoordinate der aktuellen Position
* @param moves Anzahl der schon durchgefuehrten Zuege.
* @return Sackgasse => false ; Zug okay => true
*/
public final static boolean scanBrett2(int x, int y, int moves) {
if( brett[4+(3 << 4)])
return false;
int rueckSetzen=0;
second = false;
int pos = x + (y << 4);
try {
for(int m=0; m<8; m++) {
temp1 = pos+ zuege2[m];
if(!brett[temp1]) {
if( (--verbindung[temp1]) == 1 )
if(second) {
rueckSetzen=m+1;
return false;
} else {
second = true;
zugZwang = m;
}
}
}
} finally {
if(rueckSetzen!=0) {
for(int m=0; m<rueckSetzen; m++)
if(!brett[pos+zuege2[m]])
verbindung[pos+zuege2[m]]++;
}
}
return true;
}
/** Diese Methode testes Rekursiv alle moeglichen Springerzuege durch.
* Sie benutzt keine Zugbewertung, da sie nur fuer die letzen 30 Zuege zustaendig ist.
* @param x xKoordinate des Feldes auf dem der letzte Zug endete
* @param y yKoordinate des Feldes auf dem der letzte Zug endete
* @param moves Anzahl der schon durchgefuehrten Zuege
*/
public final static void Springer2(int x, int y, int moves) throws genugLoesungenException {
// Loesung gefunden ?
if (moves == 64) {
gibLoesungAus();
}
else {
int xx,yy,tt;
// Fuehrte der letzte Zug in eine Sackgasse ?
// Nein: besteht Zugzwang ?
if(scanBrett2(x,y,moves)) {
if(second) {
// Zugzwang ausfuehren !
xx = x+zuege[zugZwang][0];
yy = y+zuege[zugZwang][1];
tt = (yy << 4) + xx;
if(!brett[tt]) {
loesung[moves][0]=xx;
loesung[moves][1]=yy;
brett[tt] = true;
Springer2(xx,yy,moves+1);
brett[tt] = false;
}
} else
// Alle 8 umliegenden Felder durchtesten ...
// frei ? => dann setzten !
for(int i=0; i<8; i++) {
xx = x+zuege[i][0];
yy = y+zuege[i][1];
tt = xx + (yy << 4);
if(!brett[tt]) {
loesung[moves][0]=xx;
loesung[moves][1]=yy;
brett[tt] = true;
Springer2(xx,yy,moves+1);
brett[tt] = false;
}
}
// Feld mit freien Nachbarn wieder auf alten Stand bringen !
int pos = x + (y << 4);
for(int m=0; m<8; m++)
if(!brett[pos+zuege2[m]])
verbindung[pos+zuege2[m]]++;
}
}
}
/** Diese Methode testes Rekursiv alle moeglichen Springerzuege durch.
* Sie benutzt Zugbewertung, um zu entscheiden in welcher Reihenfolge
* die moeglichen Zuege durchgefuehrt werden sollen !
* @param x xKoordinate des Feldes auf dem der letzte Zug endete
* @param y yKoordinate des Feldes auf dem der letzte Zug endete
* @param moves Anzahl der schon durchgefuehrten Zuege
*/
public final static void Springer(int x, int y, int moves) throws genugLoesungenException {
// ist es Zeit auf den schnelleren Backtracker zu wechseln ?
if (moves == 35) {
Springer2(x,y,moves);
}
else {
int xx,yy,tt;
// Fuehrte der letzte Zug in eine Sackgasse ?
// Nein: Besteht Zugzwang ?
if(scanBrett(x,y,moves)) {
if(second) {
// Zugzwang ausfuehren !
xx = x+zuege[zugZwang][0];
yy = y+zuege[zugZwang][1];
tt = (yy << 4) + xx;
if(!brett[tt]) {
loesung[moves][0]=xx;
loesung[moves][1]=yy;
brett[tt] = true;
Springer(xx,yy,moves+1);
brett[tt] = false;
}
} else {
//bestimme die guenstigste Reihenfolge fuer Abarbeitung !
temp1 = 1; // Welcher Eimer ?
int anz = 0; // Wieviele Loesungen eingetragen ?
while(temp1<maxWert+1) {
if(eimerAnzahl[moves][temp1] != 0) {
for(int n=0; n<eimerAnzahl[moves][temp1]; n++){
eimer[moves][0][anz] = eimer[moves][temp1][n];
anz++;
}
}
temp1++;
}
// Teste Alle moeglichen Zuege in der durch die Zugbewertung
// festgelegten Reihenfolge durch !
for(int i=0; i<anz; i++) {
xx = x+zuege[ eimer[moves][0][i] ][0];
yy = y+zuege[ eimer[moves][0][i] ][1];
tt = xx + (yy << 4);
if(!brett[tt]) {
loesung[moves][0]=xx;
loesung[moves][1]=yy;
brett[tt] = true;
Springer(xx,yy,moves+1);
brett[tt] = false;
}
}
}
// Feld mit freien Nachbarn wieder auf alten Stand bringen !
int pos = x + (y << 4);
for(int m=0; m<8; m++)
if(!brett[pos+zuege2[m]])
verbindung[pos+zuege2[m]]++;
}
}
}
/** Diese Methode ist die Ausgabemethode fuer den langsamen Algorithmus
* der alle Loesungen findet. Sie erzeugt aus einer gefundenen Loesung
* noch eine weitere.
*/
public static void _gibLoesungAus() throws genugLoesungenException{
if(ausgeben) {
// normale Loesung
System.out.print(""+(++anzahl)+": ");
for(int i=0; i<65; i++)
System.out.print( ""+(char)(loesung[i][0]-2+'A')+(loesung[i][1]-1)+" " );
System.out.println("");
if (!abbrechen || (anzahl < max)) {
// gespiegelte Loesung !
System.out.print(""+(++anzahl)+": ");
for(int i=0; i<65; i++)
System.out.print( ""+(char)(loesung[i][1]-2+'A')+(loesung[i][0]-1)+" " );
System.out.println("");
}
} else {
// normale und gespiegelte Loesung
anzahl += 2;
}
if (abbrechen && (anzahl >= max)) {
throw new genugLoesungenException();
}
}
/** Diese Methode beurteilt ob ein Zug eine Sackgasse ist oder nicht.
* Gleichzeitig bereitet sie auch die Entscheidung, welcher Zug
* als naechster zu waehlen ist vor.
* @param x xKoordinate der aktuellen Position
* @param y yKoordinate der aktuellen Position
* @param moves Anzahl der schon durchgefuehrten Zuege.
* @return Sackgasse => false ; Zug okay => true
*/
public final static boolean _scanBrett(int x, int y, int moves) {
if( brett[4+(3 << 4)])
return false;
int i=0,j=0,k=0,l=0;
byte tempRand=0;
second = false;
// Wieviele Felder mit m Abstand zum Rand ?
for(int m=0; m<_maxWert+1; m++)
eimerAnzahl[moves][m] = 0;
for(int m=0; m<8; m++) {
i=x+zuege[m][0];
j=y+zuege[m][1];
temp1 = i+(j << 4);
if(!brett[temp1]){
k=0;
l=0;
if ((i==4) && (j==3))
l++;
while((l<2) && (k<8)) {
if(!brett [temp1 + zuege2[k]] )
l++;
k++;
}
tempRand = rand[temp1];
eimer [moves] [tempRand] [eimerAnzahl[moves] [tempRand] ] = (byte)m;
eimerAnzahl[moves][tempRand]++;
if(l==1) {
if(second) {
return false;
}
else {
second = true;
zugZwang = m;
}
}
}
}
return true;
}
/** Diese Methode beurteilt ob ein Zug eine Sackgasse ist oder nicht.
* Der einzige Unterschied zur vorhergehenden Methode ist, dass hier
* kein BucketSort mehr benutzt wird, da sich das ab einem bestimmten Zug
* nicht mehr lohnt.
* @param x xKoordinate der aktuellen Position
* @param y yKoordinate der aktuellen Position
* @param moves Anzahl der schon durchgefuehrten Zuege.
* @return Sackgasse => false ; Zug okay => true
*/
public final static boolean _scanBrett2(int x, int y, int moves) {
if( brett[4+(3 << 4)])
return false;
int i=0,j=0,k=0,l=0;
second = false;
for(int m=0; m<8; m++) {
i=x+zuege[m][0];
j=y+zuege[m][1];
temp1 = i+(j << 4);
if(!brett[temp1]){
k=0;
l=0;
if ((i==4) && (j==3))
l++;
while((l<2) && (k<8)) {
if(!brett [temp1+zuege2[k]] )
l++;
k++;
}
if(l==1) {
if(second) {
return false;
}
else {
second = true;
zugZwang = m;
}
}
}
}
return true;
}
/** siehe oben ( dies ist bloss die Version fuer den langsamen Algorithmus ) ...
*/
public final static void _Springer2(int x, int y, int moves) throws genugLoesungenException {
if (moves == 64) {
_gibLoesungAus();
}
else {
int xx,yy,tt;
if(_scanBrett2(x,y,moves)) {
if(second) {
xx = x+zuege[zugZwang][0];
yy = y+zuege[zugZwang][1];
tt = xx + (yy << 4);
if(!brett[tt]) {
loesung[moves][0]=xx;
loesung[moves][1]=yy;
brett[tt] = true;
_Springer2(xx,yy,moves+1);
brett[tt] = false;
}
} else
for(int i=0; i<8; i++) {
xx = x+zuege[i][0];
yy = y+zuege[i][1];
tt = xx + (yy << 4);
if(!brett[tt]) {
loesung[moves][0]=xx;
loesung[moves][1]=yy;
brett[tt] = true;
_Springer2(xx,yy,moves+1);
brett[tt] = false;
}
}
}
}
}
/** siehe oben ( dies ist bloss die Version fuer den langsamen Algorithmus ) ...
*/
public final static void _Springer(int x, int y, int moves) throws genugLoesungenException {
if (moves == 35) {
_Springer2(x,y,moves);
}
else {
int xx,yy,tt;
if(_scanBrett(x,y,moves)) {
if(second) {
xx = x+zuege[zugZwang][0];
yy = y+zuege[zugZwang][1];
tt = (yy << 4) + xx;
if(!brett[tt]) {
loesung[moves][0]=xx;
loesung[moves][1]=yy;
brett[tt] = true;
_Springer(xx,yy,moves+1);
brett[tt] = false;
}
} else {
//bestimme die guenstigste Reihenfolge fuer Abarbeitung !
temp1 = 1; // Welcher Eimer ?
int anz = 0; // Wieviele Loesungen eingetragen ?
while(temp1<_maxWert+1) {
if(eimerAnzahl[moves][temp1] != 0) {
for(int n=0; n<eimerAnzahl[moves][temp1]; n++){
eimer[moves][0][anz] = eimer[moves][temp1][n];
anz++;
}
}
temp1++;
}
for(int i=0; i<anz; i++) {
xx = x+zuege[ eimer[moves][0][i] ][0];
yy = y+zuege[ eimer[moves][0][i] ][1];
tt = (yy << 4) +xx;
if(!brett[tt]) {
loesung[moves][0]=xx;
loesung[moves][1]=yy;
brett[tt] = true;
_Springer(xx,yy,moves+1);
brett[tt] = false;
}
}
}
}
}
}
public static void main(String args[]) {
// Ueberpruefung der Parameter:
// '-v' mit Ausgabe der gefundenen Loesung
// '<n>' Nach n gefundenen Loesungen anhalten
for(int i=0; i<args.length; i++){
if(args[i].equals("-v"))
ausgeben = true;
else
try {
max = Long.parseLong(args[i]);
abbrechen = true;
} catch ( NumberFormatException nfe) {
//tu nix !
}
}
// Das Feld in dem der aktuelle Zug gespeichert wird
loesung = new int[65][2];
// Eimer fuer bucketSort initialisieren !
eimerAnzahl = new byte[65][maxWert+1];
eimer = new byte[65][maxWert+1][8];
// Falls mehr Loesungen gefordert sind
// als der schnelle Algorithmus findet (ca. 78 Mio.), dann:
// Schachbrett fuer den langsamen Algorithmus vorbereiten
if((max > 77817887) || (!abbrechen)) {
for(int i=2; i<10; i++)
for(int j=2; j<10; j++)
brett[i+(j << 4)] = false;
loesung[0][0] = 2;
loesung[0][1] = 2;
brett[2+(2 << 4)] = true;
loesung[1][0] = 3;
loesung[1][1] = 4;
brett[3+(4 << 4)] = true;
loesung[64][0] = 2;
loesung[64][1] = 2;
} else {
//Falls der schnelle Algorithmus zu Anwendung kommt:
// Die durch die vorgegebenen Zuege veraenderte Verbindungsanzahl
// berechnen.
//initialisiert die noch mgl.Verbindungen eines Feldes auf die richtigen Startwerte
setzeSpringer(8,4);
loesung[21][0] = 9;
loesung[21][1] = 2;
loesung[22][0] = 8;
loesung[22][1] = 4;
loesung[64][0] = 2;
loesung[64][1] = 2;
}
// Unsere Namen ausgeben :-)
System.out.println(" Mathias Retzlaff, Stefan Roehrich, Daniel Heck, Hendrik Dahlkamp");
try {
// Rekursion starten
if((max > 77817887) || (!abbrechen))
_Springer(3,4,2);
else
Springer(8,4,23);
} catch (genugLoesungenException e) {
//Es wurden genug Leosungen gefunden ! => tu nix !
}
}
} // ende class Springer
/* Alle Rechte vorbehalten. */
/* (C)opyright 1999 by Mathias Retzlaff, Stefan Roehrich, Daniel Heck, Hendrik Dahlkamp*/
/* Version 2.3.42 -- Release 3 */