// Zettel 11 | Jan Kellermann, Astrid Bertram, Gruppe 15 |	Tutorin: Susanne Richter

import java.io.*;
class Springer {

	static final int[] springerX = { 2, 1,-1,-2,-2,-1, 1, 2}; // Moegliche Springerzuege
	static final int[] springerY = { 1, 2, 2, 1,-1,-2,-2,-1};
	static int a,b,n,hitcounter=0;
	static int[][] schachbrett = new int[0][0];

	public static void main(String[] argv) throws Exception {

		System.out.print("\nWelche Groesse soll das Schachfeld haben? ");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int foobar = Integer.parseInt(br.readLine());
		if (foobar==0) System.exit(1); else n=foobar;

		System.out.print("\nStartkoordinate X fuer Springer = ");
		foobar = Integer.parseInt(br.readLine());
		if ((foobar<0) || (foobar>n)) System.exit(1); else a=foobar;

		System.out.print("\nStartkoordinate Y fuer Springer = ");
		foobar = Integer.parseInt(br.readLine());
		if ((foobar<0) || (foobar>n)) System.exit(1); else b=foobar;

		schachbrett = new int[n][n];
		System.out.println("\nEin Schachfeld mit der Groesse "+n+"x"+n
			+" und dem Springer auf "+a+","+b+" wird getestet.\n");
		playchess(a,b,1);
	}

	static void playchess( int x, int y, int zug ) throws Exception {
		schachbrett[x][y] = zug; // Feld besetzen
		if (zug == n*n) {
			hitcounter++;
			// *********************Die Matrix ausgeben**********************
			for (int k=0; k<n; k++) System.out.print("+----");
			System.out.println("+");
			for (int i=0; i<n; i++) {
				for (int j=0; j<n; j++)
					if (schachbrett[i][j]!=0)
						if (schachbrett[i][j]<10)
							System.out.print("|  "+schachbrett[i][j]+" ");
						else System.out.print("| "+schachbrett[i][j]+" ");
					else System.out.print("|    ");
				System.out.println("|");
				for (int k=0; k<n; k++) System.out.print("+----");
				System.out.println("+");
			}
			// *****************Fertig mit Matrix ausgeben*******************

			System.out.print("\n Noch ein anderer Versuch? (j/n) "); // Abfragen ob nochmal
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String foobar = br.readLine();
			if (!foobar.equals("j")) System.exit(1);
			schachbrett[x][y]=0; // Feld zuruecksetzen und weitere Loesungen suchen
		} else {
			for (int i=0; i<springerX.length; i++) { // alle moeglichen Zuege durchprobieren
				int xNeu = x + springerX[i]; // Neue x-Koordinate ermitteln
				int yNeu = y + springerY[i]; // Neue y-Koordinate ermitteln
				if ((0<=xNeu) && (xNeu<n) && (0<=yNeu) && (yNeu<n) && // wenn AUF dem Feld
								(schachbrett[xNeu][yNeu] == 0))	// und noch frei
				     playchess(xNeu, yNeu, zug+1);
			}
			if ((x==a) && (y==b)) { // Wenn alle moeglichen Zuege von Startpunkt aus durch
				if (hitcounter==0) System.out.println(" Leider keine Loesungen gefunden!");
				else System.out.println(" Keine weiteren Loesungen gefunden!");
			}
			schachbrett[x][y]=0; // Feld zuruecksetzen
		}
	}
}