इस समस्या में, हमें तीन पूर्णांक मान K, N, M दिया जाता है। हमारा कार्य K शूरवीरों को NxM शतरंज की बिसात में इस तरह रखना है कि कोई भी दो शूरवीर एक दूसरे पर हमला न करें। 0 वैध तरीकों वाले मामले हो सकते हैं और कई वैध तरीकों वाले मामले भी हो सकते हैं। आपको सभी मान्य मामलों को प्रिंट करना होगा।
नाइट एक शतरंज का टुकड़ा है जो दो चाल आगे बढ़ता है और फिर एक दायें के बायें चलता है। यह बिसात में किसी भी दिशा में जा सकता है।
हमला वह स्थिति है जब एक टुकड़ा अपने वैध चाल के एक मौके में अन्य टुकड़ों के समान स्थान पर हो सकता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट - एम =3, एन =3, के =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
यहां, हमने के द्वारा शूरवीरों की स्थिति और उन पदों को चिह्नित किया है जहां उन पर ए द्वारा हमला किया गया है।