यह समस्या शतरंज बोर्ड पर N क्वीन्स की एक व्यवस्था खोजने की है, जैसे कि कोई क्वीन बोर्ड पर किसी अन्य क्वीन पर हमला न कर सके।
शतरंज की क्वीन्स किसी भी दिशा में हमला कर सकती हैं - क्षैतिज, लंबवत और विकर्ण तरीके से।
N क्वीन्स की स्थितियों को दर्शाने के लिए एक बाइनरी मैट्रिक्स का उपयोग किया जाता है, जहां कोई क्वीन दूसरी क्वीन्स पर हमला नहीं कर सकती। यहां, हम 8 क्वीन्स की समस्या हल करते हैं।
इनपुट
शतरंज बोर्ड का आकार। यह यहां 8 है क्योंकि (8x8 सामान्य शतरंज बोर्ड का आकार है)।
आउटपुट
वह मैट्रिक्स जो दर्शाता है कि N क्वीन्स को किस पंक्ति और कॉलम में रखा जा सकता है।
यदि समाधान मौजूद नहीं है, तो यह false लौटाएगा।
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0
इस आउटपुट में, मान 1 क्वीन्स के लिए सही स्थान को दर्शाता है। 0 शतरंज बोर्ड पर खाली स्थानों को दर्शाता है।
एल्गोरिदम
isValid(board, row, col)
Begin
यदि वर्तमान कॉलम के बाईं ओर कोई क्वीन है, तो
return false
यदि बाएं ऊपरी विकर्ण पर कोई क्वीन है, तो
return false
यदि बाएं निचले विकर्ण पर कोई क्वीन है, तो
return false
return true // अन्यथा यह वैध स्थान है
End
solveNQueen(board, col)
Begin
यदि सभी कॉलम भर गए हैं, तो
return true
बोर्ड की प्रत्येक पंक्ति के लिए, करें
यदि isValid(board, i, col), तो
बोर्ड में स्थान (i, col) पर क्वीन सेट करें
यदि solveNQueen(board, col+1) = true, तो
return true
अन्यथा बोर्ड से स्थान (i, col) से क्वीन हटाएं।
done
return false
End
उदाहरण
#include <iostream>
using namespace std;
#define N 4
void printBoard(int board[N][N]) {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++)
cout << board[i][j] << " ";
cout << endl;
}
}
bool isValid(int board[N][N], int row, int col) {
for(int i = 0; i < col; i++) // जांचें कि बाईं ओर क्वीन है या नहीं
if(board[row][i])
return false;
for(int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if(board[i][j]) // जांचें कि बाएं ऊपरी विकर्ण पर क्वीन है या नहीं
return false;
for(int i = row, j = col; j >= 0 && i < N; i++, j--)
if(board[i][j]) // जांचें कि बाएं निचले विकर्ण पर क्वीन है या नहीं
return false;
return true;
}
bool solveNQueen(int board[N][N], int col) {
if(col >= N) // जब N क्वीन्स सफलतापूर्वक रखी गईं
return true;
for(int i = 0; i < N; i++) { // प्रत्येक पंक्ति के लिए, जांचें कि क्वीन रखना संभव है या नहीं
if(isValid(board, i, col)) {
board[i][col] = 1; // यदि मान्य है, तो स्थान (i, col) पर क्वीन रखें
if(solveNQueen(board, col + 1)) // अन्य कॉलम्स के लिए रिकर्सिवली जाएं
return true;
board[i][col] = 0; // जब कोई स्थान खाली नहीं है तो उस क्वीन को हटाएं
}
}
return false; // जब कोई संभावित क्रम नहीं मिलता
}
bool checkSolution() {
int board[N][N];
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
board[i][j] = 0; // सभी एलिमेंट्स को 0 पर सेट करें
if(solveNQueen(board, 0) == false) { // 0वें कॉलम से शुरू
cout << "Solution does not exist";
return false;
}
printBoard(board);
return true;
}
int main() {
checkSolution();
return 0;
}
आउटपुट
1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0
N-क्वीन समस्या एक क्लासिक बैकट्रैकिंग समस्या है। N=4 के लिए, दो समाधान मौजूद हैं। N=8 के लिए, 92 विशिष्ट समाधान हैं। एल्गोरिदम कॉलम दर कॉलम क्वीन्स रखता है, पंक्तियों और विकर्णों में संघर्षों की जांच करता है। समय जटिलता O(N!) है लेकिन प्रूनिंग के साथ व्यवहार में बहुत तेज है।
