骑士的旅行问题

在国际象棋中，我们知道骑士可以以特殊的方式跳跃。它可以在每个方向上水平移动两个正方形，垂直移动一个正方形，垂直移动两个正方形，水平移动一个正方形，因此完整的移动看起来像英文字母“ L”。

在这个问题中，有一个空的棋盘，一个骑士从棋盘上的任何位置开始，我们的任务是检查骑士是否可以访问棋盘上的所有广场。当它可以访问所有广场时，然后放置从起点到达该位置所需的跳数。

这个问题可以有多种解决方案，但是我们将尝试找到一种可能的解决方案。

输入输出

Input:  
The size of a chess board. Generally, it is 8. as (8 x 8 is the size of a normal chess board.)
Output:
The knight’s moves. Each cell holds a number, that indicates where to start and the knight will reach a cell at which move.

  0  59  38  33  30  17   8  63
 37  34  31  60   9  62  29  16
 58   1  36  39  32  27  18   7
 35  48  41  26  61  10  15  28
 42  57   2  49  40  23   6  19
 47  50  45  54  25  20  11  14
 56  43  52   3  22  13  24   5
 51  46  55  44  53   4  21  12

算法

isValid（x，y，解）

输入- 放置x和y以及解矩阵。

输出-检查(x,y)是否到位并且尚未分配。

Begin
   if 0 ≤ x ≤ Board Size and 0 ≤ y ≤ Board Size, and (x, y) is empty, then
      return true
End

knightTour(x,y,move,sol,xMove,yMove)

输入-(x,y)位置，移动次数，解矩阵以及可能的x和y移动列表。

输出-更新的解决方案矩阵（如果存在）。

Begin
   if move = Board Size * Board Size, then //when all squares are visited
      return true
   for k := 0 to number of possible xMovement or yMovement, do
      xNext := x + xMove[k]
      yNext := y + yMove[k]
      if isValid(xNext, yNext, sol) is true, then
         sol[xNext, yMext] := move
         if knightTour(xNext, yNext, move+1, sol, xMove, yMove), then
            return true
         else
            remove move from the sol[xNext, yNext] to backtrack
   done
   return false
End

示例

#include <iostream>
#include <iomanip>
#define N 8

using namespace std;
int sol[N][N];

bool isValid(int x, int y, int sol[N][N]) {     //check place is in range and not assigned yet
   return ( x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}

void displaySolution() {
   for (int x = 0; x < N; x++) {
      for (int y = 0; y < N; y++)
         cout << setw(3) << sol[x][y] << " ";
      cout << endl;
   }
}

int knightTour(int x, int y, int move, int sol[N][N], int xMove[N], int yMove[N]) {
   int xNext, yNext;
   if (move == N*N)     //when the total board is covered
      return true;

   for (int k = 0; k < 8; k++) {
      xNext = x + xMove[k];
      yNext = y + yMove[k];
      if (isValid(xNext, yNext, sol)) {     //check room is preoccupied or not
         sol[xNext][yNext] = move;
         if (knightTour(xNext, yNext, move+1, sol, xMove, yMove) == true)
            return true;
         else
            sol[xNext][yNext] = -1;// backtracking
      }
   }
   return false;
}

bool findKnightTourSol() {
   for (int x = 0; x < N; x++)     //initially set all values to -1 of solution matrix
      for (int y = 0; y < N; y++)
         sol[x][y] = -1;
   //骑士的所有可能动作
   int xMove[8] = {  2, 1, -1, -2, -2, -1,  1,  2 };
   int yMove[8] = {  1, 2,  2,  1, -1, -2, -2, -1 };
   sol[0][0]  = 0;     //starting from room (0, 0)

   if (knightTour(0, 0, 1, sol, xMove, yMove) == false) {
      cout << "Solution does not exist";
      return false;
   } else
      displaySolution();
   return true;
}

int main() {
   findKnightTourSol();
}

输出结果

 0  59  38  33  30  17   8  63
37  34  31  60   9  62  29  16
58   1  36  39  32  27  18   7
35  48  41  26  61  10  15  28
42  57   2  49  40  23   6  19
47  50  45  54  25  20  11  14
56  43  52   3  22  13  24   5
51  46  55  44  53   4  21  12