放置K骑士，使其在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攻击了骑士的位置。