Problem J

The Knight’s Tour

Input: standard input

Output: standard output

Time Limit: 5 seconds

Memory Limit: 32 MB

 

 

The Knight’s Tour Happens on a (N x N) Chess Board. There are two types of knight’s tour, a) Knight’s Circuit Tour and b) Knight’s Path Tour. Knight’s Circuit Tour means that Knight will start from a square, follow Knight’s movement rules and jump to another square and thus visit all the squares and come back to its initial square without visiting any square twice. Knight’s path tour is very similar to this; the only difference is that knight won’t have to come back to its initial square. Below you can see two types of knight’s tour in a (6 x 6) board. All the circuit tours are also path tours but not vice versa.

 

 


Fig: Knight’s Circuit Tour

Fig: Knight’s Path Tour

 

 

Given a board size N you will have to determine whether there exists a Knight’s Circuit Tour in that Board. If there is a knight Circuit Tour you will have to print the knight Path Tour in that Board from a given location. You can assume that there will be a possible Knight Path Tour from that given position when there exists a knight’s circuit tour in that board.

 

Input

The input file contains several lines of input. Each line contains three integer N (1<N<=50), row (1<= row <=N), col (1<= col <=N). Here N is the board length, row and col are the row and column of the starting position. The row increases from top to bottom and column increases from left to right.

 

Output

If there is no knight’s circuit tour possible for the (N x N) board, print the line “No Circuit Tour.”, otherwise print N lines each containing N numbers. The increasing numbers actually shows the order of knight’s path tour. So the starting position will always have 1 and the last position will always have (N x N). All the numbers will be printed right justified in a field width of five. A blank line should separate the output for two consecutive sets. If there is more than one solution, any one of the solutions will be enough.

 

Sample Input:

5 1 1

6 2 2

6 1 1

 

Sample Output:

No Circuit Tour.

 

   25   32   11    2   19   34

   10    1   26   33   12    3

   31   24    9   18   35   20

    8   17   36   27    4   13

   23   30   15    6   21   28

   16    7   22   29   14    5

 

    1   32    9   18    3   34

   10   19    2   33   28   17

   31    8   29   16   35    4

   20   11   36   27   24   15

    7   30   13   22    5   26

   12   21    6   25   14   23

(World Final Warm-up Contest, Problem Setter: Shahriar Manzoor)