1#include <bits/stdc++.h>
2using namespace std;
3
4// Warnsdorff's heuristic — always move to the square with the
5// fewest onward moves. Solves N×N knight's tours efficiently.
6const int DR[8] = {-2,-2,-1,-1, 1, 1, 2, 2};
7const int DC[8] = {-1, 1,-2, 2,-2, 2,-1, 1};
8
9int degree(int r, int c, const vector<vector<int>>& b, int n) {
10 int cnt = 0;
11 for (int k = 0; k < 8; ++k) {
12 int nr = r + DR[k], nc = c + DC[k];
13 if (nr >= 0 && nc >= 0 && nr < n && nc < n && b[nr][nc] == 0) ++cnt;
14 }
15 return cnt;
16}
17
18bool knightTour(int n, int sr, int sc, vector<vector<int>>& b) {
19 b.assign(n, vector<int>(n, 0));
20 int r = sr, c = sc; b[r][c] = 1;
21 for (int step = 2; step <= n * n; ++step) {
22 int bestDeg = INT_MAX, br = -1, bc = -1;
23 for (int k = 0; k < 8; ++k) {
24 int nr = r + DR[k], nc = c + DC[k];
25 if (nr < 0 || nc < 0 || nr >= n || nc >= n || b[nr][nc]) continue;
26 int d = degree(nr, nc, b, n);
27 if (d < bestDeg) { bestDeg = d; br = nr; bc = nc; }
28 }
29 if (br == -1) return false;
30 r = br; c = bc; b[r][c] = step;
31 }
32 return true;
33}
