নাইটস টুর সমস্যা

চেসে আমরা জানি, নাইট একটি বিশেষ ভাবে জাম্প করতে পারে। এটি বাড়ি স্কয়ার হরিজেন্টালি এবং এক স্কয়ার ভার্টিক্যালি বা দুটি স্কয়ার ভার্টিক্যালি এবং এক স্কয়ার হরিজেন্টালি প্রতিটি ডিরেকশনে মুভ করতে পারে, তাই পুরো মুভমেন্ট ইংরেজি অক্ষর 'L'-এর মতো দেখয়।

এই সমস্যায়, একটি খালি চেস বোর্ড আছে, এবং বোর্ডের যেকোনো লোকেশন থেকে একটি নাইট শুরুর, আমাদের কাজ হলো চেক করা যে নাইট বোর্ডের সব স্কয়ার ভিজিট করতে পারে কিনা। যখন সেটি সব স্কয়ার ভিজিট করতে পারে, তবে সেই লোকেশনে পৌঁছানোর জন্য কতগুলো জাম্প লাগলো সেটি নম্বর দিয়ে রাখা হয়।

এই সমস্যার একাধিক সমাধান থাকতে পারে, কিন্তু আমরা একটি সম্ভাব্য সমাধান খুঁজে বের করার চেষ্টা করব।

ইনপুট এবং আউটপুট

ইনপুট: চেস বোর্ডের সাইজ। সাধারণত এটি 8। কারণ (৮ x ৮ হলো নরমাল চেস বোর্ডের সাইজ।) আউটপুট: নাইটের মুভমেন্ট। প্রতিটি সেল একটি নাম্বার ধারণ করে, যা ইন্ডিকেট করে کہ কোথা থেকে শুরু করলে নাইট কোন মুভে সেলে পৌঁছাবে। 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) প্লেসে আছে কিনা এবং এসাইন করা হয়নি কিনা।

শুরু
  যদি 0 ≤ x ≤ Board Size এবং 0 ≤ y ≤ Board Size, এবং (x, y) খালি থাকে, তবে
    return true
শেষ

knightTour(x, y, move, sol, xMove, yMove)

ইনপুট - (x, y) প্লেস, মুভের সংখ্যা, সলিউশন ম্যাট্রিক্স, এবং সম্ভাব্য x এবং y মুভমেন্ট লিস্ট।

আউটপুট - আপডেটেড সলিউশন ম্যাট্রিক্স যদি এক্সিস্ট করে।

শুরু
  যদি move = Board Size * Board Size, তবে //যখন সব স্কয়ার ভিজিট হয়ে গেছে
    return true
  k := 0 থেকে সম্ভাব্য xMovement বা yMovement সংখ্যা পর্যন্ত, করুন
    xNext := x + xMove[k]
    yNext := y + yMove[k]
    যদি isValid(xNext, yNext, sol) true হয়, তবে
      sol[xNext, yMext] := move
      যদি knightTour(xNext, yNext, move+1, sol, xMove, yMove) true হয়, তবে
        return true
      অন্যথায়
        sol[xNext, yNext] থেকে move রিমুভ করুন ব্যাকট্র্যাক করার জন্য
  শেষ
  return false
শেষ

উদাহরণ

#include <iostream> #include <iomanip> #define N 8 using namespace std; int sol[N][N]; bool isValid(int x, int y, int sol[N][N]) { //চেক করুন প্লেস রেঞ্জে আছে কিনা এবং এসাইন করা হয়নি 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) //যখন টোটাল বোর্ড কভার হয়েছে return true; for (int k = 0; k < 8; k++) { xNext = x + xMove[k]; yNext = y + yMove[k]; if (isValid(xNext, yNext, sol)) { //চেক করুন রুম preoccupied কিনা sol[xNext][yNext] = move; if (knightTour(xNext, yNext, move+1, sol, xMove, yMove) == true) return true; else sol[xNext][yNext] = -1;// ব্যাকট্র্যাকিং } } return false; } bool findKnightTourSol() { for (int x = 0; x < N; x++) //প্রাথমিকভাবে সলিউশন ম্যাট্রিক্সের সব ভ্যালু -1 সেট করুন for (int y = 0; y < N; y++) sol[x][y] = -1; //নাইটের সব সম্ভাব্য মুভ 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; //(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