C++で互いに攻撃しないようにK騎士を配置します

この問題では、3つの整数値K、N、Mが与えられます。私たちのタスクは、2人の騎士が互いに攻撃しないようにK人の騎士をNxMチェス盤に配置することです。有効な方法が0の場合もあれば、複数の有効な方法がある場合もあります。有効なケースをすべて印刷する必要があります。

騎士 は、2つ前に移動し、次に1つが右左に移動するチェスの駒です。チェス盤のどの方向にも移動できます。

攻撃 有効な動きの1つのチャンスで1つのピースが他のピースと同じ場所にあることができる位置です。

問題を理解するために例を見てみましょう

入力 − M =3、N =3、K =5

出力 −

K A K
A K A
K A K

A K A
K K K
A K A

この問題を解決するために、各行に1列ずつ騎士を配置し始めます。そして、各配置の後に攻撃しているよりも位置を確認してください。騎士を配置する際に、それが安全かどうかを確認します。安全であれば、それを配置してから次の位置に移動します。可能なすべての方法が得られるようにバックトラックを使用します。このために、バックトラック用の騎士を配置するたびに新しいボードを作成します。これが、バックトラッキングを使用して考えられるすべてのソリューションを取得する方法です。

例

ソリューションの実装を示すプログラム

#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で攻撃される位置をマークしています。