fork download
copy 
  1. // knight_heuristic.cpp
  2. // Warnsdorff heuristic + safe randomization to maximize Score = sum a[r][c]*(r+1 + c+1)
  3. // Input: n
  4. // Output: n lines each with n integers (visit order 1..n^2)
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. using ll = long long;
  9. struct Cand { int r, c, deg, weight; };
  10.  
  11. const int dr[8] = {2,1,-1,-2,-2,-1,1,2};
  12. const int dc[8] = {1,2,2,1,-1,-2,-2,-1};
  13.  
  14. int n;
  15. std::mt19937_64 rng((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
  16.  
  17. inline bool inb(int r, int c){
  18.     return r>=0 && r<n && c>=0 && c<n;
  19. }
  20.  
  21. // Try one Warnsdorff run starting at (sr,sc).
  22. // top_shuffle: shuffle among top this many candidates after sorting by (deg, weight).
  23. // returns matrix a (n x n) with visit indices (1..n^2), empty vector if failed
  24. vector<int> attempt_warnsdorff(int sr, int sc, int top_shuffle){
  25.     vector<int> a(n*n, 0); // a[r*n + c] = visit index
  26.     int r = sr, c = sc;
  27.     a[r*n + c] = 1;
  28.     for(int step=2; step<=n*n; ++step){
  29.         vector<Cand> cand;
  30.         cand.reserve(8);
  31.         for(int k=0;k<8;++k){
  32.             int nr = r + dr[k], nc = c + dc[k];
  33.             if(!inb(nr,nc)) continue;
  34.             if(a[nr*n + nc] != 0) continue;
  35.             int deg = 0;
  36.             for(int k2=0;k2<8;++k2){
  37.                 int nnr = nr + dr[k2], nnc = nc + dc[k2];
  38.                 if(inb(nnr,nnc) && a[nnr*n + nnc] == 0) ++deg;
  39.             }
  40.             cand.push_back({nr, nc, deg, nr + nc}); // weight = r+c (0-indexed)
  41.         }
  42.         if(cand.empty()){
  43.             return {}; // failed
  44.         }
  45.         sort(cand.begin(), cand.end(), [](const Cand &A, const Cand &B){
  46.             if(A.deg != B.deg) return A.deg < B.deg;
  47.             return A.weight < B.weight;
  48.         });
  49.         int top = min<int>(top_shuffle, (int)cand.size());
  50.         if(top > 1){
  51.             // shuffle only the prefix top to break ties / diversify, safe wrt strict weak ordering
  52.             shuffle(cand.begin(), cand.begin() + top, rng);
  53.         }
  54.         // choose first candidate after possible shuffle
  55.         r = cand[0].r;
  56.         c = cand[0].c;
  57.         a[r*n + c] = step;
  58.     }
  59.     return a;
  60. }
  61.  
  62. inline long long calc_score(const vector<int>& a){
  63.     // a size == n*n, a[pos] = visit index (1..n^2)
  64.     long long sc = 0;
  65.     for(int r=0;r<n;++r){
  66.         for(int c=0;c<n;++c){
  67.             int val = a[r*n + c];
  68.             // Score uses 1-based r,c in statement: (r+c)
  69.             sc += 1LL * val * ( (r+1) + (c+1) );
  70.         }
  71.     }
  72.     return sc;
  73. }
  74.  
  75. int main(){
  76.     ios::sync_with_stdio(false);
  77.     cin.tie(nullptr);
  78.     if(!(cin >> n)) return 0;
  79.     if(n <= 0) return 0;
  80.  
  81.     // quick small-n handling: for n <= 4 knights tour mostly doesn't exist except trivial n=1
  82.     if(n == 1){
  83.         cout << 1 << '\n';
  84.         return 0;
  85.     }
  86.  
  87.     // parameters — bạn có thể điều chỉnh:
  88.     const int MAX_TRIES = 1500;     // tổng số lần thử (tăng nếu có thời gian)
  89.     const int TOP_SHUFFLE = 6;     // shuffle top-K candidates after sorting
  90.     const int START_PRESET = 8;    // số lần thử các start preset trước khi random starts
  91.  
  92.     // candidate starts: corners, near-corners, center-ish
  93.     vector<pair<int,int>> starts;
  94.     starts.push_back({0,0});
  95.     starts.push_back({0,n-1});
  96.     starts.push_back({n-1,0});
  97.     starts.push_back({n-1,n-1});
  98.     if(n > 6){
  99.         starts.push_back({1,1});
  100.         starts.push_back({1,n-2});
  101.         starts.push_back({n-2,1});
  102.         starts.push_back({n-2,n-2});
  103.     }
  104.     // also add some center starts
  105.     starts.push_back({n/2, n/2});
  106.     starts.push_back({n/2, (n-1)/2});
  107.  
  108.     vector<int> best;
  109.     ll bestScore = -1;
  110.  
  111.     // deterministic first: try each preset start once without shuffle to get decent baseline
  112.     for(auto &p : starts){
  113.         auto res = attempt_warnsdorff(p.first, p.second, 1); // no shuffle
  114.         if(!res.empty()){
  115.             ll sc = calc_score(res);
  116.             if(sc > bestScore){
  117.                 bestScore = sc;
  118.                 best = res;
  119.             }
  120.         }
  121.     }
  122.  
  123.     // randomized attempts
  124.     for(int t=0; t<MAX_TRIES; ++t){
  125.         int sr, sc;
  126.         if(t < (int)starts.size() * 2){
  127.             // try each start a couple times
  128.             auto &p = starts[t % starts.size()];
  129.             sr = p.first; sc = p.second;
  130.         } else {
  131.             // random start
  132.             sr = rng() % n;
  133.             sc = rng() % n;
  134.         }
  135.         auto res = attempt_warnsdorff(sr, sc, TOP_SHUFFLE);
  136.         if(res.empty()) continue;
  137.         ll scv = calc_score(res);
  138.         if(scv > bestScore){
  139.             bestScore = scv;
  140.             best = res;
  141.         }
  142.         // small optimization: if found a full tour whose last visited cell is one of max (r+c) maybe it's already very good,
  143.         // but we continue to search to try to get even higher score.
  144.     }
  145.  
  146.     // If still empty: fallback one more exhaustive small attempt from (0,0) without shuffle
  147.     if(best.empty()){
  148.         auto res = attempt_warnsdorff(0,0,1);
  149.         if(!res.empty()){
  150.             best = res;
  151.             bestScore = calc_score(res);
  152.         }
  153.     }
  154.  
  155.     // If still empty (rare), produce trivial sequential fill to satisfy format (but checker gives 0)
  156.     if(best.empty()){
  157.         for(int r=0;r<n;++r){
  158.             for(int c=0;c<n;++c){
  159.                 cout << (r*n + c + 1) << (c+1==n?'\n':' ');
  160.             }
  161.         }
  162.         return 0;
  163.     }
  164.  
  165.     // Print best tour (row-major)
  166.     for(int r=0;r<n;++r){
  167.         for(int c=0;c<n;++c){
  168.             cout << best[r*n + c] << (c+1==n?'\n':' ');
  169.         }
  170.     }
  171.  
  172.     // If you want to see the score for debugging, uncomment:
  173.     // cerr << "BestScore=" << bestScore << "\n";
  174.  
  175.     return 0;
  176. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6YC3ME
language:
C++14 (gcc 8.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!