নাইট এর সফর সমস্যা

দাবাতে, আমরা জানি যে নাইট একটি বিশেষ পদ্ধতিতে লাফ দিতে পারে। এটি দুটি বর্গক্ষেত্র অনুভূমিকভাবে এবং একটি বর্গক্ষেত্র উল্লম্বভাবে বা দুটি বর্গক্ষেত্র উল্লম্বভাবে এবং একটি বর্গক্ষেত্র অনুভূমিকভাবে প্রতিটি দিকে সরাতে পারে, তাই সম্পূর্ণ নড়াচড়াটি ইংরেজি অক্ষর '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, 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

নাইট ট্যুর(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