কে-নাইটদের এমনভাবে রাখুন যাতে তারা একে অপরকে C++ এ আক্রমণ না করে

এই সমস্যায়, আমাদের তিনটি পূর্ণসংখ্যার মান দেওয়া হয়েছে K, N, M। আমাদের কাজ হল K নাইটদের একটি NxM চেসবোর্ডে রাখা যাতে কোনো দুই নাইট একে অপরকে আক্রমণ না করে। 0টি বৈধ উপায়ের ক্ষেত্রে এবং একাধিক বৈধ উপায়ের ক্ষেত্রেও হতে পারে। আপনাকে সমস্ত বৈধ কেস মুদ্রণ করতে হবে৷

নাইট একটি দাবা টুকরা যা দুই চাল এগিয়ে যায় এবং তারপর ডানের বামে এক সরে যায়। এটি দাবাবোর্ডে যেকোনো দিকে যেতে পারে।

আক্রমণ এমন একটি অবস্থান যখন একটি টুকরো তার বৈধ পদক্ষেপের একটি সুযোগে অন্য টুকরাগুলির মতো একই জায়গায় থাকতে পারে।

সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,

ইনপুট − M =3, N =3, K =5

আউটপুট −

K A K
A K A
K A K

A K A
K K K
A K A

এই সমস্যাটি সমাধান করার জন্য, আমরা প্রতিটি সারিতে, কলাম দ্বারা কলামে একটি করে নাইট স্থাপন শুরু করব। এবং প্রতিটি স্থান নির্ধারণের পরে আক্রমণ করার চেয়ে অবস্থান পরীক্ষা করুন। নাইট স্থাপন করার সময় আমরা এটি নিরাপদ কি না তা পরীক্ষা করব। যদি এটি নিরাপদ হয়, তাহলে আমরা এটি স্থাপন করব এবং তারপরে পরবর্তী অবস্থানে চলে যাব। আমরা ব্যাকট্র্যাকিং ব্যবহার করব, যাতে সমস্ত সম্ভাব্য উপায় পাওয়া যায় এবং এর জন্য, আমরা ব্যাকট্র্যাকিংয়ের জন্য প্রতিটি নাইট বসানোর পরে একটি নতুন বোর্ড তৈরি করব। এইভাবে আমরা ব্যাকট্র্যাকিং ব্যবহার করে সমস্ত সম্ভাব্য সমাধান পাব

উদাহরণ

আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,

#include <iostream>
using namespace std;
int m, n, k, count = 0;
void displayPositions(char** board){
   cout<<endl;
   for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
         cout<<board[i][j]<<"\t";
      }
      cout<<endl;
   }
}
void canattack(int i, int j, char a,
char** board){
   if ((i + 2) < m && (j - 1) >= 0) {
      board[i + 2][j - 1] = a;
   }
   if ((i - 2) >= 0 && (j - 1) >= 0) {
      board[i - 2][j - 1] = a;
   }
   if ((i + 2) < m && (j + 1)< n) {
      board[i + 2][j + 1] = a;
   }
   if ((i - 2) >= 0 && (j + 1) < n) {
      board[i - 2][j + 1] = a;
   }
   if ((i + 1) < m && (j + 2) <n) {
      board[i + 1][j + 2] = a;
   }
   if ((i - 1) >= 0 && (j + 2) < n) {
      board[i - 1][j + 2] = a;
   }
   if ((i + 1) < m && (j - 2) >= 0) {
      board[i + 1][j - 2] = a;
   }
   if ((i - 1) >= 0 && (j - 2) >= 0) {
      board[i - 1][j - 2] = a;
   }
}
bool canPlace(int i, int j, char** board){
   if (board[i][j] == '_')
      return true;
   else
      return false;
}
void place(int i, int j, char k, char a,
char** board, char** new_board){
   for (int y = 0; y < m; y++) {
      for (int z = 0; z < n; z++) {
         new_board[y][z] = board[y][z];
      }
   }
   new_board[i][j] = k;
   canattack(i, j, a, new_board);
}
void placeKnights(int k, int sti, int stj, char** board){
   if (k == 0) {
      displayPositions(board);
      count++;
   } else {
      for (int i = sti; i < m; i++) {
         for (int j = stj; j < n; j++) {
            if (canPlace(i, j, board)) {
               char** new_board = new char*[m];
               for (int x = 0; x < m; x++) {
                  new_board[x] = new char[n];
               }
               place(i, j, 'K', 'A', board, new_board);
               placeKnights(k - 1, i, j, new_board);
            }
         }
         stj = 0;
      }
   }
}
int main() {
   m = 3, n = 3, k = 5;
   char** board = new char*[m];
   for (int i = 0; i < m; i++)
   board[i] = new char[n];
   for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++)
      board[i][j] = '_';
   }
   cout<<"The ways in which "<<k<<" knights can be placed in "<<m<<"x"<<n<<" chessboard are :\n";
   placeKnights(k, 0, 0, board);
   return 0;
}

আউটপুট

The ways in which 5 knights can be placed in 3x3 chessboard are :
K A K
A K A
K A K

A K A
K K K
A K A

এখানে, আমরা K দ্বারা নাইটদের অবস্থান চিহ্নিত করেছি এবং অবস্থান যেখানে তারা A দ্বারা আক্রমণ করেছে।