재진입 Knight의 이동경로 구현

A knight’s tour is a sequence of legal moves by a knight starting
at some square and visiting each square exactly once. A
knight’s tour is called reentrant if there is a legal move that
takes the knight from the last square of the tour back to where
the tour began.

*64. Show that there is a knight’s tour on an 8 × 8 chessboard.
[Hint: You can construct a knight’s tour using a method invented by H. C. Warnsdorff in 1823: Start in any square, and then always move to a square connected to the fewest number of unused squares. Although this method may not always produce a knight’s tour, it often does.]

• Discrete Mathematics and Its Applications 8th 742p
• Rosen의 이산수학 8판 809p

번역본엔 'tour'가 '이동경로'로 번역되어있는데, 'path(경로)'가 아닌 'circuit(순회)'이다. 마땅한 단어가 없었을까?

DFS인데, 갈 수 있는 정사각형을 Hint에서 말한 대로 방문.

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

typedef tuple<int, int, int> tiii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define N 8
#define M 8

int path(vvi board, int n, int col, int row);
int check(const vvi& board, int col, int row);
bool cmp(const tiii& a, const tiii& b);
int print_board(const vvi& board);

int a_col[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int a_row[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
int init_col, init_row;

int main(void) {
  vvi board(N, vi(M));
  init_col = 0;
  init_row = 0;
  path(board, 1, init_col, init_row);
}

int path(vvi board, int n, int col, int row) {
  vector<tiii> sq;
  int res;
  int t_col, t_row;

  board[col][row] = n;

  if (n == N * M) return (print_board(board));

  if (!check(board, init_col, init_row)) return (1);

  for (int i = 0; i < 8; i++) {
    t_col = col + a_col[i];
    t_row = row + a_row[i];
    if (0 <= t_col && t_col < N && 0 <= t_row && t_row < M &&
        !board[t_col][t_row]) {
      sq.push_back({t_col, t_row, check(board, t_col, t_row)});
    }
  }
  sort(sq.begin(), sq.end(), cmp);
  for (tiii t : sq)
    if (!path(board, n + 1, get<0>(t), get<1>(t))) return (0);
  return (1);
}

int check(const vvi& board, int col, int row) {
  int t_col, t_row;
  int res;

  res = 0;
  for (int i = 0; i < 8; i++) {
    t_col = col + a_col[i];
    t_row = row + a_row[i];
    if (0 <= t_col && t_col < N && 0 <= t_row && t_row < M &&
        !board[t_col][t_row])
      res++;
  }
  return (res);
}

bool cmp(const tiii& a, const tiii& b) { return (get<2>(a) < get<2>(b)); }

int print_board(const vvi& board) {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) cout << board[i][j] << ' ';
    cout << '\n';
  }
  return (0);
}