Trong bài toán này, chúng ta được cung cấp ba giá trị nguyên K, N, M. Nhiệm vụ của chúng ta là xếp K quân cờ vào bàn cờ NxM sao cho không có hai quân mã nào tấn công nhau. Có trường hợp có 0 cách hợp lệ và cũng có trường hợp có nhiều cách hợp lệ. Bạn cần in tất cả các trường hợp hợp lệ.
Hiệp sĩ là quân cờ đi trước hai nước và sau đó một quân đi bên trái bên phải. Nó có thể di chuyển theo bất kỳ hướng nào trong bàn cờ.
Tấn công là vị trí khi một quân cờ có thể ở cùng vị trí với các quân cờ khác trong một cơ hội di chuyển hợp lệ của nó.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào - M =3, N =3, K =5
Đầu ra -
K A K A K A K A K A K A K K K A K A
Để giải quyết vấn đề này, chúng ta sẽ bắt đầu đặt các kỵ sĩ lần lượt vào từng hàng, từng cột. Và kiểm tra vị trí hơn là đang tấn công sau mỗi vị trí. Khi đặt các hiệp sĩ, chúng tôi sẽ kiểm tra xem nó có an toàn hay không. Nếu an toàn thì ta đặt rồi chuyển sang vị trí tiếp theo. Chúng tôi sẽ sử dụng backtracking để có thể có được tất cả các cách có thể và vì điều này, chúng tôi sẽ tạo một bảng mới sau mỗi vị trí của kỵ sĩ để backtracking. Đây là cách chúng tôi sẽ có được tất cả các giải pháp khả thi bằng cách sử dụng backtracking.
Ví dụ
Chương trình cho thấy việc triển khai giải pháp của chúng tôi,
#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;
} Đầu ra
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
Ở đây, chúng tôi đã đánh dấu vị trí của các hiệp sĩ theo K và các vị trí mà họ bị tấn công bởi A.