class Backtracking {

	public static void main(String[] argv) {
		Springer s=new Springer();
		s.versuchen(0,0,1);
		System.out.println(s);	
		System.out.println("Insgesamt "+s.getSteps()+" Versuche waren zum Finden der Loesung noetig!\n");
		s.reset();
		
		AchtDamen d=new AchtDamen();
		d.versuchen(0);
		System.out.println("Position der acht Damen: "+d);	
		
		// letzter Aufruf, da Labyrinth().versuchen() das Prg. beendet
		System.out.print("\nLabyrinth: ");	
		new Labyrinth().sucheAusweg(5,4);
	}

}
class AchtDamen {
	public AchtDamen() { 
		reset();
	}
	static final int n = 8;
	int[] dameInDerSpalte = new int[n]; // Werte 0 bis 7
	// die folgenden drei boolean-Felder muessen mit true vorbelegt werden
	boolean[] reihe           = new boolean[n];     // false gibt an, dass Reihe belegt wurde
	boolean[] diagonaleLinks  = new boolean[2*n-1]; // false gibt an, dass Diagonale belegt ist
	boolean[] diagonaleRechts = new boolean[2*n-1]; // dito.
	boolean versuchen( int x ) {
		if (x == n)
			// letzte Dame wurde erfolgreich platziert
			return true;
		else // probiere alle Reihen durch 
			for (int y=0; y<n; y++) {
			int links  = (x+y)       % (2*n-1); // Idx d. Diagonale links
			int rechts = (x-y-1+2*n) % (2*n-1); // Idx d. Diagonale rechts
			if (reihe[y] && diagonaleLinks[links] && diagonaleRechts[rechts]) {
				dameInDerSpalte[x]=y; // Dame in der Spalte x steht in Reihe y
				reihe[y] = diagonaleLinks[links] = diagonaleRechts[rechts] = false;
				// Reihe und zwei Diagonalen sind jetzt besetzt
				boolean erfolg = versuchen(x+1);
				if (erfolg)
					return true;
				else
					// Reihe und Diagonalen wieder freigeben (Backtracking)
					reihe[y] = diagonaleLinks[links] = diagonaleRechts[rechts] = true;
			}
		}
		return false;
	}
	void reset() {
		for(int y=0;y<n;y++) {
			reihe[y]=true;
			dameInDerSpalte[y]=0;
		}
		for(int y=0;y<2*n-1;y++) {
			diagonaleLinks[y]=true;
			diagonaleRechts[y]=true;
		}
	}
	public String toString() {
		String s="";
		for(int y=0;y<n;y++) 
			s+=dameInDerSpalte[y]+",";
		return s;
	}
}
class Springer {
	// nach Solymosi, Grude: 
	// Grundkurs Algorithmen und Datenstrukturen, Vieweg 2000, 53
	static final int[] springerX = { 2, 1,-1,-2,-2,-1, 1, 2};
	static final int[] springerY = { 1, 2, 2, 1,-1,-2,-2,-1};
	static final int n = 8;
	static int[][] schachbrett = new int[n][n];
	static int steps;
	boolean versuchen( int x, int y, int nr ) {
		steps++;
		schachbrett[x][y] = nr; // Feld besetzen
		if (nr == n*n) return true; // alle Felder wurden besetzt
		else
			for (int versuch=0; versuch<springerX.length; versuch++) {
				// alle moeglichen Zuege durchprobieren
				int xNeu = x + springerX[versuch];
				int yNeu = y + springerY[versuch];
				if ( // xNeu und yNeu sind auf dem Brett und
				     0 <= xNeu && xNeu < n && 0 <= yNeu && yNeu < n &&
				     // Feld ist noch nicht besucht worden,
				     schachbrett[xNeu][yNeu] == 0 &&
				     // dann besuchen
				     versuchen (xNeu, yNeu, nr+1) 
				   )
					return true;
			}
		schachbrett[x][y]=0; // Feld zuruecksetzen
		return false;        // alle Versuche blieben erfolglos
	}
	int getSteps() { 
		return steps;
	}
	void reset() {
		steps=0;
		for(int y=0;y<n;y++)
			for(int x=0;x<n;x++) 
				schachbrett[x][y]=0;
	}
	public String toString() {
		java.text.DecimalFormat f=new java.text.DecimalFormat("00");
		String s="";
		for(int y=0;y<n;y++) {
			for(int x=0;x<n;x++) {
				if(x>0)s+=" ";
				s+=f.format(schachbrett[x][y]);
			}
			if(y<n-1)s+="\n";
		}
		return s;
	}
}

class Labyrinth {

	static final boolean[][] gang = { { false, true, true,false,false,false },
	                            { true ,false,false, true, true,false },
	                            { true ,false, true,false, true,false },
	                            { false, true,false,false, true,false },
	                            { false, true, true, true,false, true },
	                            { false,false,false,false, true,false }};
	

	static final boolean[] ausgang =  { true ,false,false,true,false, true };
	
	static boolean[] marke   =  { false,false,false,false,false,false };
	
	/**
	 * sucht Ausweg, von Index 'von' nach Index 'nach' gehend
	 */
	void sucheAusweg(int von, int nach) {
		if ( gang[von][nach] && !marke[nach] ) {
			System.out.print(""+von+"-->"+nach+" ");
			if ( ausgang[nach] ) {
				System.out.println("Endlich draussen!");
				System.exit(1);
			}
			marke[nach] = true;  // Marke setzen, um Zyklus zu verhindern
			for (int i=0; i<gang.length; i++)
				sucheAusweg(nach,i);
			marke[nach] = false; // Marke ruecksetzen
		}
	}
}