नाइट टूर समस्या

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

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

इस समस्या के कई समाधान हो सकते हैं, लेकिन हम एक संभावित समाधान ढूंढने का प्रयास करेंगे।

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

इनपुट: शतरंज बोर्ड का आकार। आमतौर पर, यह 8 है। क्योंकि (8 x 8 सामान्य शतरंज बोर्ड का आकार है।) आउटपुट: नाइट की चालें। प्रत्येक सेल एक संख्या रखता है, जो इंगित करता है कि कहां से शुरू करना है और नाइट किस चाल में उस सेल तक पहुंचेगा। 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  #include  #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