วาง K-knights เพื่อไม่ให้โจมตีซึ่งกันและกันใน C++

ในปัญหานี้ เราได้รับค่าจำนวนเต็มสามค่า K, N, M หน้าที่ของเราคือวางอัศวิน K ไว้ในกระดานหมากรุก NxM เพื่อไม่ให้อัศวินสองคนโจมตีกัน อาจมีกรณีที่ 0 วิธีที่ถูกต้องและกรณีที่มีหลายวิธีที่ถูกต้อง คุณต้องพิมพ์กรณีที่ถูกต้องทั้งหมด

อัศวิน เป็นชิ้นหมากรุกที่เคลื่อนที่ไปข้างหน้า 2 ครั้งแล้วเลื่อนไปทางซ้ายของขวา สามารถเคลื่อนที่ไปในทิศทางใดก็ได้บนกระดานหมากรุก

โจมตี คือตำแหน่งเมื่อชิ้นหนึ่งสามารถอยู่ในตำแหน่งเดียวกันกับชิ้นอื่นในโอกาสเดียวของการเคลื่อนไหวที่ถูกต้อง

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล − 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.