<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

468. A bit of classic
Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Everybody loves classical problems! Real professional can solve them quickly and gaily come to more difficult problems, and amateurs are just able to solve them, which is also important for popularization of computer programming contests. Here you are required to solve classical problem not only in chess but in computer science as well. Given integer N, find a way to bypass every cell of a chessboard N x N exactly once with a chess knight.

Input
Input file contains integer number N — size of the board (1 ≤ N ≤ 250).

Output
If there is no solution for the given size of the board, write to the output file the only message No solution. (without quotes). Otherwise, write to the first line of the output file message There is solution:, and then to every of the N following lines write N numbers separated by spaces — order of traversal of the board. Each of the numbers from 1 to N2 should occur in this sequence exactly once. Knight may start and end its trip at any cell of the chessboard.

Example(s)
sample input
sample output
3
No solution.

sample input
sample output
5
There is solution:
 1 14 9 20 3
 24 19 2 15 10
 13 8 25 4 21
 18 23 6 11 16
 7 12 17 22 5

<|response|>
1. Abridged problem statement
Given an integer N (1 ≤ N ≤ 250), find an open knight's tour on an N×N chessboard: a sequence of knight moves that visits every cell exactly once. If no such tour exists, print "No solution." Otherwise print "There is solution:" on the first line, then an N×N grid of integers 1..N² giving the visitation order.

2. Key observations
- A knight's tour does not exist for N = 2, 3 or 4 (except the trivial 1×1 case).
- For N = 1, the tour is just the single cell.
- For all N ≥ 5, an open knight's tour exists.
- Warnsdorff's heuristic is a simple greedy rule that usually finds a full tour: always move to the unvisited neighbor that has the fewest onward moves (minimum "degree").
- To avoid early dead-ends, randomize ties, randomize the starting cell, and if the tour gets stuck before covering all N² squares, restart the procedure.

3. Full solution approach
a. Handle trivial / no-tour cases:
   - If N is 2, 3 or 4, output "No solution." and stop.
b. Prepare the eight knight moves as a list of (dx,dy) pairs.
c. Seed a random number generator (fixed seed for reproducibility).
d. Repeat until a full tour is found:
   1. Initialize an N×N board of zeros (0 = unvisited).
   2. Shuffle the global list of knight moves.
   3. Pick a random starting cell (cx,cy), mark it as move 1.
   4. For move = 2 to N²:
      - Collect all valid knight moves from (cx,cy) to an unvisited cell (nx,ny).
      - For each candidate (nx,ny), compute its Warnsdorff degree = number of onward moves available from (nx,ny).
      - If there are no candidates, we're stuck: abort this attempt and restart.
      - Otherwise choose the candidate with minimum degree (break ties randomly by prior shuffling).
      - Move to that cell, mark it with the current move number, update (cx,cy).
   5. If we completed all moves up to N², we have a solution; break out of the retry loop.
e. Print "There is solution:" and then the board, each row on its own line with a leading space per cell.

This runs in O(N²·8) per attempt, and empirically the number of attempts before success is small even for N up to 250.

4. C++ implementation with comments
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int N;
vector<pair<int, int>> knight_moves = {{1, 2},  {1, -2},  {2, 1},  {2, -1},
                                       {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};
mt19937 rng(42);

void read() { cin >> N; }

bool is_valid_move(int x, int y, const vector<vector<int>>& board) {
    return x >= 0 && x < N && y >= 0 && y < N && board[x][y] == 0;
}

int get_degree(int x, int y, const vector<vector<int>>& board) {
    int degree = 0;
    for(const auto& [dx, dy]: knight_moves) {
        int next_x = x + dx, next_y = y + dy;
        if(is_valid_move(next_x, next_y, board)) {
            degree++;
        }
    }
    return degree;
}

bool find_tour(vector<vector<int>>& board) {
    int current_x = uniform_int_distribution<int>(0, N - 1)(rng);
    int current_y = uniform_int_distribution<int>(0, N - 1)(rng);
    board[current_x][current_y] = 1;

    for(int position = 2; position <= N * N; position++) {
        vector<pair<int, int>> next_moves;
        for(int i = 0; i < knight_moves.size(); i++) {
            int next_x = current_x + knight_moves[i].first;
            int next_y = current_y + knight_moves[i].second;
            if(is_valid_move(next_x, next_y, board)) {
                int degree = get_degree(next_x, next_y, board);
                next_moves.emplace_back(degree, i);
            }
        }

        if(next_moves.empty()) {
            return false;
        }

        auto [_, move_index] =
            *min_element(next_moves.begin(), next_moves.end());

        current_x += knight_moves[move_index].first;
        current_y += knight_moves[move_index].second;
        board[current_x][current_y] = position;
    }
    return true;
}

void solve() {
    // Uses Warnsdorff's heuristic to greedily select the next move with the
    // fewest onward moves Randomly breaks ties among moves with the same
    // minimum degree. This is not guaranteed to be polynomial time but highly
    // effective for N ≤ 250.

    if(N == 2 || N == 3 || N == 4) {
        cout << "No solution." << endl;
        return;
    }

    vector<vector<int>> board(N, vector<int>(N, 0));
    while(true) {
        board.assign(N, vector<int>(N, 0));
        shuffle(knight_moves.begin(), knight_moves.end(), rng);
        if(find_tour(board)) {
            break;
        }
    }

    cout << "There is solution:" << endl;
    for(const auto& row: board) {
        for(int i = 0; i < N; i++) {
            cout << " " << row[i];
        }
        cout << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with comments
```python
import sys
import random

# Read N
data = sys.stdin.read().strip().split()
if not data:
    sys.exit(0)
N = int(data[0])

# Quick no-solution cases
if N in (2, 3, 4):
    print("No solution.")
    sys.exit(0)

# All eight knight moves
knight_moves = [
    (1,2), (1,-2), (2,1), (2,-1),
    (-1,2), (-1,-2), (-2,1), (-2,-1)
]
random.seed(42)

def is_valid(x, y, board):
    "Check if (x,y) is in bounds and unvisited"
    return 0 <= x < N and 0 <= y < N and board[x][y] == 0

def degree(x, y, board):
    "Count onward moves from (x,y)"
    cnt = 0
    for dx, dy in knight_moves:
        if is_valid(x+dx, y+dy, board):
            cnt += 1
    return cnt

def find_tour():
    "Try one Warnsdorff pass; return board or None if stuck."
    board = [[0]*N for _ in range(N)]
    cx = random.randrange(N)
    cy = random.randrange(N)
    board[cx][cy] = 1

    for step in range(2, N*N + 1):
        candidates = []
        for i, (dx, dy) in enumerate(knight_moves):
            nx, ny = cx+dx, cy+dy
            if is_valid(nx, ny, board):
                candidates.append((degree(nx, ny, board), i))
        if not candidates:
            return None
        random.shuffle(candidates)
        _, move_i = min(candidates, key=lambda x: x[0])
        dx, dy = knight_moves[move_i]
        cx, cy = cx+dx, cy+dy
        board[cx][cy] = step

    return board

# Keep retrying until success
while True:
    random.shuffle(knight_moves)
    result = find_tour()
    if result is not None:
        board = result
        break

# Output
print("There is solution:")
for row in board:
    print(' ' + ' '.join(str(x) for x in row))
```
