एन क्वींस प्रभुत्व पहेली को हल करने के लिए एल्गोरिदम

Question

मैंने अधिक सामान्य एन क्वींस समस्या हल की है, लेकिन अब मैं एन क्वींस प्रभुत्व समस्या को हल करने के लिए एक एल्गोरिदम की तलाश में हूं।

"n बोर्ड × एक n को देखते हुए, वर्चस्व संख्या है, जो क्वीन्स (या अन्य टुकड़े) पर हमला करने या हर वर्ग पर कब्जा करने के लिए आवश्यक की न्यूनतम संख्या है पाते हैं। 8 × 8 बोर्ड के लिए, रानी की वर्चस्व संख्या 5 है। " - विकिपीडिया

मैं बड़े पैमाने पर खोज की है और इस समस्या पर कुछ भी लेकिन विद्वानों के कागजात, दूर से समझ में आता है कुछ भी नहीं है नहीं मिल रहा।

मेरा पहला विचार सिर्फ एक रानी को नीचे रखना है और फिर अगली रानी को उस जगह पर रखें जहां अधिकांश अन्य वर्गों पर हमला कर सकते हैं। हालांकि, यह समाधान उत्पन्न कर सकता है, लेकिन मैं यह गारंटी देने का कोई तरीका नहीं समझ सकता कि समाधान न्यूनतम समाधान है।

किसी भी मदद की सराहना की जाएगी, धन्यवाद।

Answer 1

अपने एल्गोरिदम का उपयोग करके, आप सभी संभावित संयोजन उत्पन्न कर सकते हैं और इससे कम ले सकते हैं। संकेत: इसके लिए रिकर्सन का उपयोग करें और समान परिस्थितियों को संसाधित न करें (या इसे कैश करें) जैसे सममित प्लेसमेंट, वही ऑर्डर आदि।

Answer 2

निम्नलिखित कुशल नहीं है, लेकिन यह काम करेगा।

समस्या को पूर्णांक प्रोग्रामिंग समस्या के रूप में पुनरारंभ करें। बोर्ड पर प्रत्येक वर्ग या तो 0 या 1 है। किसी वर्ग के लिए स्वयं का योग और सभी हमलावर वर्ग बिल्कुल 1 होना चाहिए। और आप कुल योग को कम करना चाहते हैं।

Answer 3

यह एक होमवर्क प्रश्न होने की भावना में, मैं समाधान प्रदान नहीं करूंगा, बल्कि समाधान की एक श्रृंखला जो समाधान का कारण बनता है। निम्नलिखित जवाब देने का एक तरीका है "क्या आप n क्वींस के साथ बोर्ड पर हावी हो सकते हैं?" फिर आप n = 1, n = 2, ...

1) स्थिति 1 में एक रानी रखकर, फिर आप सभी शेष पदों पर हावी होकर रानी 1 तक नहीं पहुंच सकते हैं (एन -1) क्वींस (एन -1) से चुने गए पद (2,3, ...)?

2) यदि नहीं, तो क्या आप स्थिति 2 में रानी रख सकते हैं, और उसके बाद चुने गए सभी शेष पदों पर हावी हो सकते हैं (एन -1) क्वींस (एन -1) पदों (3,4) , ...)?

3) एक इतने पर ... यानी जगह पहले की स्थिति 3, तो स्थान 4 पर रानी, ​​आदि

ध्यान दें कि यह समाधान पुनरावर्ती है - प्रत्येक प्रत्यावर्तन में, "शेष पदों एक रानी जोड़ने के लिए" और "पदों को अभी तक किसी भी रानी द्वारा पहुंच योग्य नहीं है" तर्क के रूप में पारित किया जाता है। जब "किसी भी रानी द्वारा पदों तक पहुंचने योग्य नहीं है" खाली है, तो आपको एक समाधान मिल गया है।

* किसी भी तरह से सभी बोर्ड पदों को ऑर्डर करें, उदाहरण के लिए बाएं से दाएं, ऊपर से नीचे। ताकि 8x8 बोर्ड पर 64 पदों को केवल एक सूचकांक (1..64) द्वारा संदर्भित किया जा सके।

Answer 4

int count; 

int safetyOfThisPosition(int col,int row,int *x) 

{ 

     int iterator; 
     for(iterator=0;iterator<col;iterator++) 
     { 
     if(row==x[iterator] || abs(col-iterator)==abs(row-x[iterator])) 
      return 0; 
     } 
     return 1; 
} 

void Nqueen(int col){ 

     int row,iterator; 
     static int x[N]; 
     for(row=0;row<N;row++) 
     { 
      if(safetyOfThisPosition(col,row,x)) 
      { 
       x[col]=row; 
       if(col==N-1) 
       { 
        for(iterator=0;iterator<=col;iterator++) 
       printf("%d ",x[iterator]); 
        printf("\n"); 
       } 
       else 
        Nqueen(col+1); 
      } 
     } 

    } 

int main(){ 

     Nqueen(0); 
     return 0; 
    }