p468.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 Not guaranteed 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;
}

=================
p468.ans1
======================
No solution.

=================
p468.in1
======================
3

=================
p468.ans2
======================
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

=================
statement.txt
======================
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

=================
p468.in2
======================
5

=================
