ナイトツアーの問題

チェスでは、騎士が特別な方法でジャンプできることを私たちは知っています。水平方向に2マス、垂直方向に1マス、または垂直方向に2マス、水平方向に1マス移動できるため、完全な移動は英語の文字「L」のようになります。

この問題では、空のチェス盤があり、騎士は板の任意の場所から開始します。私たちのタスクは、騎士が板のすべての正方形を訪問できるかどうかを確認することです。すべての広場を訪れることができたら、出発点からその場所に到達するために必要な数のジャンプを配置します。

この問題には複数の解決策がありますが、考えられる解決策を1つ見つけようとします。

入力と出力

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、solution）

入力- 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;
   //all possible moves for knight
   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