N क्वीन समस्या

यह समस्या शतरंज बोर्ड पर N क्वीन की व्यवस्था ढूंढने की है, जैसे कि कोई क्वीन बोर्ड पर किसी अन्य क्वीन पर हमला न कर सके।

शतरंज क्वीन किसी भी दिशा में हमला कर सकती है जैसे क्षैतिज, लंबवत, क्षैतिज और विकर्ण तरीके से।

एक बाइनरी मैट्रिक्स का उपयोग N क्वीन की स्थितियों को प्रदर्शित करने के लिए किया जाता है, जहां कोई क्वीन अन्य क्वीन पर हमला नहीं कर सकती।

इनपुट और आउटपुट

इनपुट: शतरंज बोर्ड का आकार। आमतौर पर, यह 8 है। क्योंकि (8 x 8 सामान्य शतरंज बोर्ड का आकार है।) आउटपुट: वह मैट्रिक्स जो दर्शाता है कि 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)

इनपुट: शतरंज बोर्ड, पंक्ति और बोर्ड का कॉलम

आउटपुट - True जब पंक्ति और स्थान पर क्वीन रखना वैध हो या नहीं

Begin 
  if there is a queen at the left of current col, then 
    return false 
  if there is a queen at the left upper diagonal, then 
    return false 
  if there is a queen at the left lower diagonal, then 
    return false; 
  return true //otherwise it is valid place 
End

solveNQueen(board, col)

इनपुट - शतरंज बोर्ड, वह कॉलम जहां क्वीन रखने का प्रयास कर रही है

आउटपुट - वह स्थिति मैट्रिक्स जहां क्वीन रखी गई हैं

Begin 
  if all columns are filled, then 
    return true 
  for each row of the board, do 
    if isValid(board, i, col), then 
      set queen at place (i, col) in the board 
      if solveNQueen(board, col+1) = true, then 
        return true 
      otherwise remove queen from place (i, col) from board. 
  done 
  return false 
End

उदाहरण

#include using namespace std; #define N 8 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++) //check whether there is queen in the left or not if (board[row][i]) return false; for (int i=row, j=col; i>=0 && j>=0; i--, j--) if (board[i][j]) //check whether there is queen in the left upper diagonal or not return false; for (int i=row, j=col; j>=0 && i= N) //when N queens are placed successfully return true; for (int i = 0; i < N; i++) { //for each row, check placing of queen is possible or not if (isValid(board, i, col) ) { board[i][col] = 1; //if validate, place the queen at place (i, col) if ( solveNQueen(board, col + 1)) //Go for the other columns recursively return true; board[i][col] = 0; //When no place is vacant remove that queen } } return false; //when no possible order is found } bool checkSolution() { int board[N][N]; for(int i = 0; i

आउटपुट
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