이 문제에서 우리는 세 개의 정수 값 K, N, M을 받습니다. 우리의 임무는 두 기사가 서로 공격하지 않도록 NxM 체스판에 K 기사를 배치하는 것입니다. 유효한 방법이 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로 표시했습니다.