// Project KnightsTour

// Display the results of a knight's
// tour: a knight (L-shaped move) that
// visits every square of an n x n board.

// Here is the search order from the
// current square *:
//        6 7
//       5   8
//         *
//       4   1
//        3 2

import java.io.PrintWriter;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.InputMismatchException;
import java.util.Date;
public class KnightsTour
{
    private static int[ ][ ] array;
    private static int size;
    private static boolean done;

    public static void main(String[ ] args)
                  throws FileNotFoundException
    {
        System.out.print("Enter size of board: ");
        Scanner con = new Scanner(System.in);
        try
        {
            size = con.nextInt( );
        }
        catch(InputMismatchException e)
        {
            System.out.println("Enter a numeric size >= 3");
            System.exit(0);
        }

        done = false;
        array = new int[size][size];
        initialize();
        System.out.println(new Date( ));
        search(0, 0, 1);
        printResult( );
        System.out.println(new Date( ));
    }

    // Initialize each square of board to unvisited.
    public static void initialize()
    {
        for(int y = 0; y <= size - 1; y++)
            for(int x = 0; x <= size - 1; x++)
                array[y][x] = 0;
    }

    // Recursive search method.
    public static void search(int x, int y, int depth)
    {
        if (done)
            return;
        else if (depth == size * size + 1)
        {
            done = true;
            return;
        }
        else if (0 <= x && 0 <= y &&
                 x <= size - 1 && y <= size - 1 &&
                 array[y][x] == 0)
        {
            array[y][x] = depth;
            search(x + 2, y + 1, depth + 1);
            search(x + 1, y + 2, depth + 1);
            search(x - 1, y + 2, depth + 1);
            search(x - 2, y + 1, depth + 1);
            search(x - 2, y - 1, depth + 1);
            search(x - 1, y - 2, depth + 1);
            search(x + 1, y - 2, depth + 1);
            search(x + 2, y - 1, depth + 1);
            if (!done)
                array[y][x] = 0;
        }
        return;
    }

    // Print result of search.
    public static void printResult( )
                       throws FileNotFoundException
    {
        for(int y = 0; y <= size - 1; y++)
        {
            for(int x = 0; x <= size - 1; x++)
            {
                int value = array[y][x];
                if (value > 0)
                    System.out.printf("%3d", value);
            }
            System.out.println( );
        }
    }
}