नाइट के दौरे की समस्या

शतरंज में, हम जानते हैं कि शूरवीर एक विशेष तरीके से कूद सकता है। यह दो वर्गों को क्षैतिज रूप से और एक वर्ग को लंबवत या दो वर्गों को लंबवत और एक वर्ग क्षैतिज रूप से प्रत्येक दिशा में स्थानांतरित कर सकता है, इसलिए पूरा आंदोलन अंग्रेजी अक्षर 'एल' जैसा दिखता है।

इस समस्या में, एक खाली शतरंज बोर्ड है, और बोर्ड में किसी भी स्थान से एक नाइट शुरू होता है, हमारा काम यह जांचना है कि क्या नाइट बोर्ड के सभी वर्गों का दौरा कर सकता है या नहीं। जब यह सभी चौकों पर जा सकता है, तो उस स्थान तक पहुंचने के लिए शुरुआती बिंदु से आवश्यक छलांगें लगाएं।

इस समस्या के कई समाधान हो सकते हैं, लेकिन हम एक संभावित समाधान खोजने की कोशिश करेंगे।

इनपुट और आउटपुट

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) जगह पर है और अभी तक असाइन नहीं किया गया है।

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)

इनपुट − (एक्स, वाई) स्थान, चालों की संख्या, समाधान मैट्रिक्स, और संभावित एक्स और वाई आंदोलन सूचियां।

>आउटपुट - अद्यतन समाधान मैट्रिक्स यदि मौजूद है।

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