इस समस्या में, हमें तीन पूर्णांक मान 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 << "वे तरीके जिनमें " << k << " नाइट्स को " << m << "x" << n << " शतरंज बोर्ड में रखा जा सकता है :\n";
placeKnights(k, 0, 0, board);
return 0;
}
आउटपुट
वे तरीके जिनमें 5 नाइट्स को 3x3 शतरंज बोर्ड में रखा जा सकता है : K A K A K A K A K A K A K K K A K A
यहां, हमने नाइट्स की स्थितियों को K से और उन स्थितियों को जहां वे हमला करते हैं A से चिह्नित किया है।