class KnightsTour {
  static int[][] brett;
  static int bredde, bredde2;
  static long antFors?k;

  public static void main (String[] args) {
    bredde = Integer.parseInt(args[0]);
    bredde2 = bredde * bredde;
    brett = new int[bredde][bredde];
    flytt(1, 0, 0);
    System.out.printf("Ingen l?sninger etter %,d trekk!\n",
		      antFors?k);
  }

  static void tegnBrett () {
    for (int rx = bredde-1;  rx >= 0;  rx--) {
      for (int kx = 0;  kx < bredde;  kx++) {
	System.out.printf("%4d",brett[kx][rx]);
      }
      System.out.println();
    }
  }

  static void flytt (int trekk, int r, int k) {
    ++antFors?k;
	
    // Er det lov ? flytte hit?
    if (r < 0 || r >= bredde) return;
    if (k < 0 || k >= bredde) return;
    if (brett[r][k] > 0) return;

    // Det er lov, s? vi pr?ver ? flytte hit.
    brett[r][k] = trekk;

    // Har vi funnet en l?sning?
    if (trekk == bredde2) {
      System.out.printf("L?sning etter %,d trekk\n",
			antFors?k);
      tegnBrett();  System.exit(1);
    }

    // Pr?v ? flytte videre:
    flytt(trekk+1, r+2, k+1);  flytt(trekk+1, r+2, k-1);
    flytt(trekk+1, r+1, k+2);  flytt(trekk+1, r+1, k-2);
    flytt(trekk+1, r-1, k+2);  flytt(trekk+1, r-1, k-2);
    flytt(trekk+1, r-2, k+1);  flytt(trekk+1, r-2, k-1);

    // Det gikk ikke; da trekker vi oss tilbake.
    brett[r][k] = 0;
  }
}