Under construction

Still being built. Things may change

Knight Tour

Time limit1sMemory limit128 MB

Summary
Construct a full knight's tour on an N by N board (N up to 666) starting from a given square, using Warnsdorff-style or divide-and-conquer construction, or report impossibility.
Level

Hard8 of 10

Topics
Backtracking, Divide and conquer, Greedy
Solved
No attempts yet

Problem

There is an N × N chessboard, where 6 ≤ N ≤ 666. A knight starts from the given square and must visit every square of the board exactly once using only legal knight moves. A square that has already been visited cannot be visited again.

Input

The first line contains the integer N. The second line contains two integers r and c, the starting position. r is the row number and c is the column number, and coordinates are 1-based.

Output

If such a route exists, print N × N lines containing the visited positions in order. Each line must contain the row number and column number separated by a space. If no route exists, print -1 -1 on the first line.

Examples1

  1. Example 1

    Input
    6
1 1
    Expected output
    1 1
3 2
5 1
6 3
5 5
3 6
2 4
1 6
3 5
5 6
4 4
5 2
3 1
1 2
3 3
2 1
1 3
2 5
4 6
6 5
5 3
6 1
4 2
5 4
6 6
4 5
6 4
4 3
6 2
4 1
2 2
1 4
2 6
3 4
1 5
2 3