ปัญหาการเดินทางของอัศวิน

ในหมากรุก เรารู้ว่าอัศวินสามารถกระโดดได้ในลักษณะพิเศษ สามารถย้ายช่องสี่เหลี่ยมสองช่องในแนวนอนและแนวตั้งหนึ่งช่องหรือแนวตั้งสองช่องหรือแนวตั้งสองช่อง และแนวนอนหนึ่งช่องในแต่ละทิศทาง ดังนั้นการเคลื่อนไหวทั้งหมดจึงดูเหมือนตัวอักษรภาษาอังกฤษ "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, ย้าย, โซล, 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