एक बिलियन क्वींस समस्या समाधान या, "एन-क्वींस वितरण समस्या के समाधान की सूची में पैटर्न का अध्ययन"

सारांश

एक वर्णन उन कानूनों का दिया गया है जो n- क्वींस वितरण समस्या के सभी समाधानों की अनुक्रमिक सूची में स्थापित किए गए थे। यह स्थापित है कि:

• एन के बढ़ते मूल्य के साथ सभी समाधानों की सामान्य सूची में पूर्ण समाधान का अनुपात घटता है।
  
• संपूर्ण समाधान सभी समाधानों की अनुक्रमिक सूची में इस तरह वितरित किए जाते हैं कि पूर्ण समाधान जो सूची में एक दूसरे के करीब स्थित होते हैं, वे सबसे अधिक पाए जाते हैं।
  
• सभी समाधानों की सामान्य सूची में पूर्ण समाधान के क्रम में समरूपता है। यदि सूची की शुरुआत से आई-वें स्थिति में समाधान पूरा हो गया है, तो स्थिति n-i + 1 पर स्थित सूची के अंत से सममित समाधान भी पूरा हो गया है (समाधान की समरूपता का नियम)।
  
• सभी समाधानों की सूची में सममित रूप से स्थित दोनों प्रकार के समाधानों की जोड़ी, पूरक हैं - संगत पंक्तियों की स्थिति सूचकांकों का योग n + 1 (समाधानों के पूरक का नियम) के बराबर और स्थिर है। इससे पता चलता है कि सभी पूर्ण समाधानों की सूची का केवल पहला भाग "अद्वितीय" है, सूची के दूसरे छमाही से कोई भी पूर्ण समाधान पूरक नियम के आधार पर प्राप्त किया जा सकता है। इस नियम का एक परिणाम यह है कि n के किसी भी मूल्य के लिए, पूर्ण समाधानों की संख्या हमेशा एक सम संख्या होगी।
  
• समाधान मैट्रिक्स की पंक्तियों की गतिविधि इस मैट्रिक्स के मध्य से गुजरने वाली क्षैतिज अक्ष के संबंध में सममित है। इसका मतलब यह है कि i-th पंक्ति की कोशिकाओं की गतिविधि हमेशा पंक्ति n-i + 1 की कोशिकाओं की गतिविधि के साथ मेल खाती है। गतिविधि से अभिप्राय उस आवृत्ति से है जिसके साथ सेल इंडेक्स पूर्ण समाधानों की सूची के अनुरूप लाइन में होता है। इसी प्रकार, हल मैट्रिक्स के स्तंभों की कोशिकाओं की गतिविधि मैट्रिक्स को दो समान भागों में विभाजित करने वाली ऊर्ध्वाधर अक्ष के बारे में सममित है।
  
• सभी समाधानों की क्रमिक खोज में n के बावजूद, पहला पूरा समाधान एक निश्चित अनुक्रम के बाद ही दिखाई देता है। लघु समाधानों के प्रारंभिक अनुक्रम का आकार n के साथ बढ़ता है। N के मूल्यों के लिए पहले पूर्ण समाधान की उपस्थिति से पहले लघु समाधानों की सूची की लंबाई निकटतम विषम मूल्यों की तुलना में काफी लंबी है।
  
• निर्णय मैट्रिक्स में वह रेखा, जिस पर कठिनाइयाँ आगे बढ़ने लगती हैं, और पहला छोटा निर्णय बनता है, मैट्रिक्स को सुनहरा नियम के अनुसार विभाजित करता है। N के छोटे मानों के लिए, ऐसा निष्कर्ष अनुमानित है, हालांकि, n के मूल्य में वृद्धि के साथ, इस तरह के निष्कर्ष की सटीकता मानक नियम के स्तर तक बढ़ जाती है।
  

यह प्रकाशन लेख [1] से मुख्य परिणाम प्रस्तुत करता है, जो "आर्टिफिशियल इंटेलिजेंस की मॉडलिंग, 2018, 5 (1)" पत्रिका में प्रकाशित हुआ था। Habré पर n-Queens की समस्या से जुड़े कार्य थे: [२] , [३]
N-nn-size chessboard पर n क्वीन्स बांटने की समस्या का एक लंबा इतिहास रहा है। यह मूल रूप से 1848 में एम। बेजल द्वारा तैयार किया गया था [4] एक नियमित शतरंज के लिए एक बौद्धिक कार्य के रूप में। समय के साथ, समस्या का विवरण F. Nauck [5] द्वारा विस्तारित किया गया था, और एक शतरंज का आकार किसी भी मूल्य पर ले सकता था।

परिचय

समस्या का कथन काफी सरल है: आपको आकार nxn की एक बिसात पर n क्वीन्स को वितरित करने की आवश्यकता है ताकि प्रत्येक पंक्ति में, प्रत्येक स्तंभ, और जहाँ रानी स्थित है, वहाँ से गुजरने वाले बाएँ और दाएँ विकर्णों पर, एक से अधिक रानी न हों। यह कार्य किसी को समझने या समझाने में आसान है, लेकिन इसे हल करना मुश्किल है। तथ्य यह है कि कोई नियम नहीं हैं जिसके आधार पर आप प्रत्येक लाइन पर रानियों की व्यवस्था कर सकते हैं ताकि समाधान प्राप्त हो सके। एक समाधान केवल कुछ पंक्तियों में क्वीन्स की व्यवस्था के विभिन्न रूपों की गणना करके प्राप्त किया जा सकता है। हालांकि, समाधान की इस पद्धति की जटिलता इस तथ्य में निहित है कि रानियों की व्यवस्था के सभी वेरिएंट की संख्या तेजी से बढ़ती हुई एन के साथ बढ़ जाती है। इसके अलावा, रानी को एक निश्चित रेखा की मुक्त स्थिति में रखने के लिए कोई भी कदम उठाने से शेष रेखाओं में मुक्त स्थिति की सूची में बदलाव होता है, और जब एक कदम पीछे लौटते हैं, तो खोज शाखा बनाने के लिए, पहले किए गए कार्यों के निशान को साफ करना आवश्यक है।

एन-क्वींस समस्या को हल करने के विभिन्न पहलुओं से संबंधित प्रकाशनों की एक बड़ी संख्या है। उन्हें अनुसंधान के कई क्षेत्रों के लिए जिम्मेदार ठहराया जा सकता है: एक शतरंजबोर्ड (n) के आकार के दिए गए मूल्य के लिए सभी पूर्ण समाधानों की खोज, n के विभिन्न मूल्यों के लिए एक समाधान खोजने के लिए एक त्वरित एल्गोरिदम का विकास, संपूर्ण समस्या का हल, संपूर्ण समाधान के लिए k क्वीन्स की एक मनमानी रचना। एल्गोरिथम गणना की कम्प्यूटेशनल जटिलता, साथ ही समस्या के मूल सूत्रीकरण के विभिन्न संशोधनों। इन क्षेत्रों से परिचित होने के लिए, मैं बी जॉर्डन, एस। ब्रेट [6] और आईपी जेंट, सी। जेफरसन, पी। नाइटिंगेल [7] द्वारा दिलचस्प प्रकाशनों की सिफारिश करूंगा, जो विभिन्न शोध क्षेत्रों का काफी विस्तृत अवलोकन प्रदान करता है। विशेष रूप से नोट वाल्टर कॉस्टर्स द्वारा समर्थित ऑनलाइन प्रकाशन [8] है , जिसे यूनिवर्सिटेट लीडेन के एक समूह द्वारा तैयार किया गया था और इसमें एन-क्वीन समस्या (दिसंबर 2018 तक) से संबंधित 342 प्रकाशनों के लिंक शामिल हैं।

यद्यपि एन-क्वींस समस्या 150 से अधिक वर्षों से सक्रिय है, और इस समय के दौरान भारी संख्या में प्रकाशन सामने आए हैं, मुझे ऐसी नौकरी नहीं मिली जो इस समस्या को हल करने के परिणामों में पैटर्न खोजने के लिए प्रासंगिक होगी। सभी समाधानों की खोज से संबंधित अधिकांश परियोजनाओं में अधिकांश संभावनाएं उन समाधानों को नहीं बचा पाईं जो पाए गए थे और यह नहीं देखा था कि "अंदर" क्या था। समस्या बयान में, अन्य प्रमुख लक्ष्य थे, और हमारे सम्मानित सहयोगियों ने उन्हें हासिल किया। हालांकि, दूरस्थ रूप से, यह मुझे प्रतीत हुआ कि स्थिति तब होती है जब कोई व्यक्ति नाश्ते के लिए अंडे उबालता है, लेकिन उन्हें नहीं खाता है, लेकिन उनकी स्मृति में केवल उबले हुए अंडे की संख्या को छोड़कर, उन्हें फेंक देता है। मुझे हमेशा यकीन है कि यदि डेटा यादृच्छिक नहीं है, तो उनमें एक निश्चित नियमितता होनी चाहिए, अगर हमें यह नियमितता नहीं मिल रही है। यह विश्वास था कि इस कार्य में पैटर्न की खोज का कारण था।

विचार के लिए उपयोगी जानकारी के साथ हैबर समुदाय के सदस्यों को प्रदान करने की इच्छा के साथ, मैं प्रतिभाशाली प्रोग्रामर चाहूंगा, जिनमें से अधिकांश हेबर पर, कंप्यूटर सिमुलेशन (कम्प्यूटेशनल सिमुलेशन) के रूप में विकास की ऐसी दिशा पर अधिक ध्यान देना चाहते हैं। एक शोध विधि के रूप में, इस तरह के "एल्गोरिथम गणित" का उपयोग कई क्षेत्रों के "अग्रणी किनारे" पर किया जाता है: कृत्रिम बुद्धिमत्ता, सॉफ्टवेयर विज्ञान, डेटा विज्ञान, ... और मुझे यकीन है कि व्यावहारिक अनुप्रयोग के लिए बहुत जटिल और महत्वपूर्ण समस्याओं को एल्गोरिथम गणित के आधार पर हल किया जाएगा। अन्यथा।

परिभाषित

इसके बाद, हम प्रतीक n द्वारा बिसात के आकार को निरूपित करेंगे। एक समाधान को पूर्ण कहा जाएगा यदि सभी एन क्वीन्स को लगातार एक शतरंज की बिसात पर रखा जाए। अन्य सभी समाधान, जब सही ढंग से रखी गई रानियों की संख्या n से कम है - हम लघु समाधान कहेंगे। एक समाधान की लंबाई से हमारा मतलब सही ढंग से रखी गई रानियों की संख्या (k) से है। N के दिए गए मान के लिए सभी समाधानों की संख्या m द्वारा निरूपित की जाएगी। आकार nx n के "बिसात" के एनालॉग के रूप में, हम आकार nx n के "समाधान मैट्रिक्स" पर विचार करेंगे।

शुरुआत

एक अध्ययन का संचालन करने के लिए, एन के मनमाने मूल्य के लिए सभी समाधानों की खोज करने के लिए एक एल्गोरिथ्म विकसित किया गया था। हमने मानक पुनरावर्तन या नेस्टेड लूप की सामान्य प्रणाली का उपयोग नहीं किया। एन के बड़े मूल्यों के लिए, इस तरह का दृष्टिकोण काफी समस्याग्रस्त होगा। एल्गोरिथ्म को इंटरेक्टिंग घटनाओं के एक सेट के आधार पर बनाया गया था, जिनमें से प्रत्येक में एक निश्चित प्रणाली की कार्रवाई हो रही है, परस्पर जुड़ी हुई है। यह समस्या के समाधान की शाखा में अगले नोड को चुनते समय (फॉरवर्ड ट्रैकिंग) राज्य संरचना को बदलने के लिए तंत्र को लागू करना संभव बनाता है, या एक या एक से अधिक चरणों (वापस ट्रैकिंग) पर वापस आने पर पहले किए गए कार्यों के निशान को साफ़ करता है। एल्गोरिथ्म में मेमोरी आकार या प्रोसेसर की गति के लिए कोई विशेष आवश्यकताएं नहीं हैं।

इस एल्गोरिथ्म के आधार पर, समाधान मैट्रिक्स n = (7, ..., 16) के विभिन्न मूल्यों के लिए सभी अनुक्रमिक समाधान (दोनों छोटे और पूर्ण) पाए गए। चूंकि पूर्ण समाधानों की सूची का आकार नामित अनुक्रम है; इंटीग्रेट सीक्वेंस का ऑन-लाइन इनसाइक्लोपीडिया (अनुक्रम A000170 [9]) और कई प्रकाशनों में संकेत दिया गया है, इसलिए हमारे द्वारा विचार किए गए एन के मूल्यों के लिए सभी समाधानों की सूची (लघु + पूर्ण) का आकार देना मेरे लिए दिलचस्प लगता है: 7 (194), 8 (736), 9 (2 936), 10 (12 774), 11 (61 076), 12 (314 730), 13 (1 716 652), 14 (10 030 692), 15 () 62 518 772), 16 (415 515 376)।

इसके अलावा, पाए गए समाधानों का उपयोग करते हुए, हम कुछ समस्याओं के समाधान, उन्हें हल करने के तरीके और परिणामों का विवरण देते हैं।

1. वह राज्य स्थान जिसमें समाधान खोजे जाते हैं

आकार n के निर्णय के मैट्रिक्स की कुछ पंक्तियों में क्वीन्स की व्यवस्था के लिए विभिन्न विकल्पों की गणना राज्य स्थान के गठन की ओर ले जाती है। यदि मैट्रिक्स के एक या दूसरे सेल में रानियों की व्यवस्था पर कोई प्रतिबंध नहीं था, तो राज्य स्थान का आकार n होगा। यदि हम प्रत्येक पंक्ति और प्रत्येक कॉलम में एक से अधिक रानी के स्थान को प्रतिबंधित करने वाले नियम को ध्यान में रखते हैं, तो हमें राज्य स्थान का एक सबसेट मिलता है, जिसका आकार n के बराबर होगा! राज्य स्थान का यह सबसेट बदमाश द्वारा n के वितरण की समस्या से मेल खाता है। अगर, इसके साथ ही, हम नियम को भी ध्यान में रखते हैं, जहाँ रानी स्थित है, वहाँ से गुजरने वाले बाएँ और दाएँ विकर्णों पर एक से अधिक रानी के स्थान को निषिद्ध करते हैं, तो हमें कुछ खोज स्थान मिलते हैं जिनका आकार n से कम होगा! .. हम राज्य अंतरिक्ष के ऐसे सबसेट को कहते हैं! - एक उत्पादक खोज स्थान, इस तथ्य पर आधारित है कि केवल इस उप-क्षेत्र में सभी संभव समाधान हैं। उत्पादक खोज स्थान में कोई भी पूर्ण शाखाएं निश्चित संख्या में रानियों के साथ सही तरीके से रखी गई हैं। मूल रूप से, ये छोटे निर्णय हैं, और केवल एक छोटा सा शेष भाग पूर्ण निर्णय हैं।

चित्रा 1 तीन संकेतकों के प्राकृतिक लघुगणक के रेखांकन को दर्शाता है: ए) निर्णय मैट्रिक्स के आकार पर भाज्य मूल्य (एन!); बी) सभी निर्णयों की संख्या (दोनों कम और पूर्ण); सी) समाधान मैट्रिक्स (एन) के आकार के आधार पर पूर्ण समाधानों की संख्या। जैसा कि अपेक्षित था, सभी घटता बढ़ते एन के साथ एक घातीय वृद्धि की विशेषता है। सभी समाधानों की संख्या और पूर्ण समाधानों की संख्या की वृद्धि दर भिन्न होती है, हालांकि यह ग्राफ पर इतना ध्यान देने योग्य नहीं है, छोटे मान n मानों के कारण। उदाहरण के लिए, n = 13 के लिए, इन संकेतकों के लघुगणक के बीच का अंतर 3.148 है, और n = 16 के लिए यह अंतर 0.190 से बढ़ जाता है और 3.338 है। जाहिर है, n में और वृद्धि के साथ, यह विसंगति अधिक महत्वपूर्ण होगी।

चित्र 1 मान n पर राज्य स्थान के आकार के लघुगणक की निर्भरता

2. सभी निर्णयों की सामान्य सूची में पूर्ण निर्णयों का अनुपात कैसे बदलता है?

जाहिर है, अगर सभी समाधानों की संख्या की वृद्धि दर सभी समाधानों की संख्या की वृद्धि दर से पीछे है, तो सभी समाधानों की सामान्य सूची में एक पूर्ण समाधान खोजने की संभावना n के बढ़ते मूल्य के साथ घट जाएगी। चित्रा 2 एन के मूल्य पर सभी समाधानों की सामान्य सूची में पूर्ण समाधान के अनुपात का एक ग्राफ दिखाता है। यह देखा जाता है कि समाधान मैट्रिक्स के आकार में वृद्धि के साथ, सामान्य सूची में सभी पूर्ण समाधानों की हिस्सेदारी घट जाती है। प्रारंभिक मानों n = (7, ..., 14) के लिए, यह मान 0.2062 से 0.2062 से 0.0364 तक कम हो जाता है, और फिर इस मूल्य में एक क्रमिक, स्पर्शोन्मुख कमी जारी रहती है। यहां दो बयानों के बीच एक औपचारिक विरोधाभास पैदा होता है: एक तरफ, पूर्ण समाधानों की संख्या तेजी से बढ़ती हुई n के साथ बढ़ती जाती है, और दूसरी तरफ, सभी समाधानों की अनुक्रमिक सूची में एक पूर्ण समाधान की संभावना लगातार कम हो रही है। यह प्रतीत होता है कि विरोधाभास बहुत सरल रूप से समझाया गया है, उत्पादक स्थान का आकार और सभी समाधानों की सूची का संबद्ध आकार पूर्ण समाधानों की संख्या की तुलना में एन के साथ तेजी से बढ़ता है। यह एक घास के ढेर में सुई खोजने की कोशिश करने जैसा है - बढ़ती एन के साथ "घास की मात्रा" सुइयों की संख्या की तुलना में तेजी से बढ़ती है जो वहां खो जाती हैं। इसलिए, हम मान सकते हैं कि यदि n = 27 के लिए, पूर्ण समाधानों की संख्या लगभग 2.346 * 10 ^{17 है} , तो सभी समाधानों की संख्या का संबंधित मूल्य सबसे अधिक संभावना होगा ~ 10 ²⁰ से अधिक परिमाण के 3-4 आदेश

अंजीर। 2 बढ़ती एन के साथ सभी समाधानों की सामान्य सूची में पूर्ण समाधान के अनुपात में कमी

3. सभी समाधानों की सूची में विभिन्न लंबाई के समाधान की आवृत्ति क्या है?

जैसा कि पहले उल्लेख किया गया है, उत्पादक खोज स्थान में सभी पूर्ण शाखाएं सही ढंग से रखी गई विभिन्न रानियों की संख्या के साथ समाधान हैं।
यह हमारे लिए रुचि है कि सभी समाधानों की सामान्य सूची में विभिन्न लंबाई के समाधान क्या हैं।

मान 1 के लिए तालिका 1 = (7, ..., 12) विभिन्न लंबाई वाले समाधानों के लिए सापेक्ष आवृत्तियों के संबंधित मूल्यों को प्रस्तुत करता है। इस डेटा का संबंधित दृश्य प्रतिनिधित्व चित्र 3 में दिखाया गया है।

तालिका का विश्लेषण हमें निम्नलिखित निष्कर्ष निकालने की अनुमति देता है:

ए) आकार एन के प्रत्येक मैट्रिक्स के लिए, समाधान की एक निश्चित लंबाई होती है जिसमें अधिकतम आवृत्ति होती है (बोल्ड में हाइलाइट किया गया)।

तालिका 1. आकार n = (7, ... 12) के एक मैट्रिक्स के लिए अलग-अलग लंबाई (के) के समाधान की सापेक्ष आवृत्ति (%)

n \ k	4	5	6	7	8	9	10	11	12
7	10.31	31.23	27.84	20.62
8	2.45	20.38	34.78	29.89	12.50
9	0.34	5.79	21.73	35.83	34.32	11.99
10	0.05	1.35	8.41	25.62	32.94	25.96	5.67
11		0.15	2.12	11.80	26.71	34.47	20.36	4.39
12		0.01	0.29	3.28	13.56	29.88	31.29	17.18	4.51

बी) के रूप में n बढ़ जाती है, विभिन्न लंबाई के साथ समाधान की संख्या बढ़ जाती है। तदनुसार, सभी निर्णयों की सापेक्ष आवृत्ति घट जाती है।

अंजीर। 3 समाधान मैट्रिक्स, n = 7, ..., 16 के आकार के आधार पर विभिन्न लंबाई के समाधान की आवृत्ति

c) आकार n के प्रत्येक मैट्रिक्स के लिए, समाधान की लंबाई का एक निश्चित न्यूनतम आकार होता है, जिसके नीचे लघु समाधान नहीं होते हैं। बढ़ते एन के साथ, इस सीमा का मूल्य बढ़ जाता है। उदाहरण के लिए, n = 8 के लिए, थ्रेसहोल्ड मान 4 है, क्रमशः n = 16 के लिए, थ्रेसहोल्ड मान 7 है।

4. सभी समाधानों की अनुक्रमिक सूची में पूर्ण समाधानों की सापेक्ष व्यवस्था क्या है?

समस्या के बयान में "एन क्वीन्स के वितरण पर" कोई कारण नहीं हैं जो सभी समाधानों की सामान्य सूची में पूर्ण निर्णयों के अनुक्रम के बारे में कोई धारणा बनाने का कारण देगा। हम इस बात में रुचि रखते थे कि क्या सामान्य सूची में पूर्ण समाधान समान रूप से, बेतरतीब ढंग से वितरित किया जाता है, या यदि इसकी कुछ ख़ासियतें हैं। यह पता लगाने के लिए, हमने सभी समाधानों की अनुक्रमिक सूची में निकटतम पूर्ण समाधानों के बीच की दूरी का विश्लेषण किया। जैसा कि चित्र 4 से देखा जा सकता है, जहाँ n = 12 के लिए, संगत आवृत्तियों में परिवर्तन का एक ग्राफ प्रस्तुत किया गया है,

अंजीर। 4 सभी पूर्ण समाधानों की अनुक्रमिक सूची में निकटतम पूर्ण समाधानों के बीच की दूरी बनाम आवृत्ति। (एन = 12)

सबसे बड़ी आवृत्ति के साथ पूर्ण समाधान होते हैं जो सभी समाधानों की एक सामान्य अनुक्रमिक सूची में तुरंत एक दूसरे का अनुसरण करते हैं। ये खोज शाखा के गठन के मामले हैं जब अंतिम लाइनों में मुक्त पदों का संबंध आपको दो या अधिक लगातार पूर्ण समाधान बनाने की अनुमति देता है। इसके अलावा, अधिकतम आवृत्ति वे पूर्ण समाधान हैं जिनके बीच स्थित हैं: एक लघु समाधान, दो लघु समाधान, आदि।

5. क्या सभी समाधानों की सामान्य सूची में पूर्ण समाधान की व्यवस्था में एक पैटर्न है?

इस प्रश्न का उत्तर देने के लिए, हमने n = (7, ..., 16) के लिए सभी समाधानों की अनुक्रमिक सूचियों का विश्लेषण किया है। परिणामों को स्पष्ट रूप से प्रदर्शित करने के लिए, चित्र 5 में, मान n = 8 के लिए, एक ग्राफ प्रस्तुत किया गया है जहां सभी 736 समाधानों की सूची में प्रत्येक समाधान की लंबाई क्रमिक रूप से इंगित की गई है। यहां, केवल 92 समाधान पूर्ण हैं और उन्हें लाल रंग में हाइलाइट किया गया है, शेष 644 समाधान छोटे हैं और नीले रंग में हाइलाइट किए गए हैं। यह देखा जा सकता है कि संपूर्ण समाधान समान रूप से सभी समाधानों की सूची में वितरित नहीं किए जाते हैं। ऐसे क्षेत्र हैं जहां पूर्ण समाधान अधिक सामान्य हैं, और ऐसे स्थान हैं जहां पूर्ण समाधान दुर्लभ हैं या बिल्कुल नहीं हैं।

अंजीर। 5 एक 8 x 8 मैट्रिक्स (लाल - पूर्ण समाधान, नीला - लघु समाधान) के लिए सभी समाधानों की एक क्रमिक सूची में प्रत्येक समाधान की लंबाई। सभी समाधानों की कुल संख्या 736 है

हालांकि, यहां कुछ और महत्वपूर्ण है। यदि आप ध्यान से नीले-लाल बारकोड से मिलते जुलते आकृति को देखते हैं, तो आपको एक बहुत ही महत्वपूर्ण विशेषता दिखाई देगी, सभी लाल रेखाएं सममितीय हैं जो कुछ सशर्त ऊर्ध्वाधर रेखाओं के संबंध में समाधानों की सूची के मध्य से गुजरती हैं। वास्तव में, जैसा कि चेक से पता चलता है, अगर सामान्य सूची की शुरुआत से आई-वें चरण में एक पूर्ण समाधान है, तो, तदनुसार, एक पूर्ण समाधान निश्चित रूप से चरण एम-आई + 1 पर पाया जाएगा। उदाहरण के लिए, n = 8 के लिए, यदि सभी समाधानों के लिए अनुक्रमिक खोज में पहला पूर्ण समाधान चरण 43 में प्रकट होता है, तो, तदनुसार, सूची में अंतिम पूर्ण समाधान चरण 736–43 + 1 = 694 में मिलेगा। यदि 10x10 मैट्रिक्स के लिए 17 वें समाधान चरण 368 की सूची में दिखाई देते हैं, तो इसके लिए पूर्ण समाधान सममित चरण 12774-17 + 1 = 12407 पर सभी समाधानों की सूची में दिखाई देता है। यह नियम किसी भी आकार के निर्णय मैट्रिक्स के लिए सही है। इसलिए, हम एक नियम बना सकते हैं। N के किसी भी मूल्य के लिए, यदि सभी समाधानों की अनुक्रमिक सूची में, सूची की शुरुआत से i-th स्थिति में, समाधान पूर्ण है, तो स्थिति m-i + 1 पर स्थित सूची के अंत से सममित समाधान भी पूरा हो जाएगा (समाधानों की समरूपता का नियम)। m, , . , n, , . ( – ).

, – . n+1 . , 17- n=10 368- (1, 5, 7, 10, 4, 2, 9, 3, 6, 8).

, 12407 (10, 6, 4, 1, 7, 9, 2, 8, 5, 3). , (11, 11, …,11). n, , , . . n, ( , ), , – n+1 ( ). Q(i ) Q1(i) – ,

<b>`Q ( i ) + Q1 ( i ) = n + 1, i = (1, n) `</b> 

इस नियम का अर्थ है कि यदि i- वें चरण पर एक पूर्ण समाधान प्राप्त किया जाता है, तो चरण m - i +1 पर सममित पूर्ण समाधान ज्ञात हो जाता है । इसलिए, सभी पूर्ण समाधानों की खोज करते समय, सभी पूर्ण समाधानों में से केवल पहले आधे भाग को खोजने के लिए पर्याप्त है। पूर्ण समाधानों की सूची का दूसरा भाग पहले से प्राप्त समाधानों से निर्धारित किया जा सकता है, जो पूरकता के नियम पर आधारित है। पूर्ण समाधानों की आधी सूची प्राप्त करने का मानदंड पिछले पूर्ण समाधान Q (i-1) और बाद के Q (i) के बीच पूरक नियम की पूर्ति है। यानी, यह आवश्यक है कि दो लगातार समाधानों के संगत सूचकांकों की प्रत्येक जोड़ी का योग n + 1 के बराबर हो। चूंकि सभी पूर्ण समाधानों की सूची से कोई भी पूर्ण समाधान अद्वितीय है, केवल उन निरंतर पूर्ण समाधानों को पूरक होगा जो सीमा के दोनों किनारों पर हैं जो सूची को आधे में विभाजित करता है।

ये दो नियम भविष्य में अनुमति देंगे, जब एन के किसी भी अगले मूल्य के लिए सभी पूर्ण समाधानों की खोज करेंगे, गणना की मात्रा को कम करने के लिए और, तदनुसार, गणना का समय आधा।

6. पहला पूर्ण समाधान खोजने के लिए चरणों के अनुक्रम का दृश्य

समाधान खोज की एक शाखा बनाते समय (फॉरवर्ड ट्रैकिंग) प्रदर्शन करने और वापस लौटने (बैक ट्रैकिंग) की प्रक्रिया कैसे होती है? इस प्रश्न का उत्तर देने के लिए, हमने 10 x 10 मैट्रिक्स के लिए, लाइनों के बीच प्रारंभिक 194 बदलावों के अनुक्रम को निर्धारित किया, जब तक कि पहला पूर्ण समाधान प्रकट नहीं होता है। इसी ग्राफ को चित्र 6 में दिखाया गया है। नीली रेखाएं एक आगे की गति का संकेत देती हैं, और लाल रेखाएं वापसी का संकेत देती हैं। इन 194 चरणों के दौरान, 35 लघु समाधान बनाए गए थे। आंकड़ा बताता है कि अधिकांश संक्रमण (84.5%) लाइनों (5, 6, 7, 8) के बीच होते हैं। यह "लक्ष्य" के रास्ते पर एक तरह की "अड़चन" है। जैसा कि आंकड़े से पता चलता है, 4 लाइन पर स्विच करने के केवल 7 मामले हैं और तीसरी लाइन पर स्विच करने का एक मामला है। 9 वीं पंक्ति में स्विच करने के 13 मामले भी हैं। 10 वीं पंक्ति में जाने के तीन प्रयास असफल रहे, क्योंकि 10 वीं पंक्ति की इन खोज शाखाओं में कोई खाली स्थान नहीं था। यह उदाहरण लघु की सभी शाखाओं को प्रदर्शित करता है

अंजीर। 6 पहले 194 खोज चरणों (n = 10) के लिए बैकट्रैकिंग (लाल) और फॉरवर्डट्रैकिंग (नीला) घटनाओं का दृश्य।

समाधान, पहले पूर्ण समाधान तक। इस तरह की समस्या को हल करने के लिए कोई भी एल्गोरिदम प्रभावी होगा यदि इसमें एक तंत्र शामिल है जो शाखाओं के सभी (या भाग) को समाप्त कर देगा जो छोटे समाधानों का नेतृत्व करते हैं।

7. पहला पूर्ण समाधान कितने छोटे निर्णयों के बाद दिखाई देता है?

यह देखते हुए कि संपूर्ण समाधान सभी समाधानों की सूची के अलग-अलग हिस्सों में अलग-अलग दिखाई देते हैं, यह पता लगाना महत्वपूर्ण है कि क्रमिक तरीके से सभी समाधानों की खोज करते समय पहला पूर्ण समाधान कितने छोटे समाधान दिखाई देता है। इस उद्देश्य के लिए, मानों के लिए n = (7, ..., 35), पहले पूर्ण समाधान की उपस्थिति तक सभी छोटे समाधान क्रमिक रूप से गणना किए गए थे। जैसा कि चित्र 7 से देखा जा सकता है, जो n पर निर्भरता का एक ग्राफ दिखाता है, चरण संख्या का प्राकृतिक लघुगणक, जब पहला पूर्ण समाधान दिखाई दिया, यहां तक ​​कि n के मूल्यों के लिए, पहला पूर्ण समाधान n के निकटतम विषम मानों की तुलना में बहुत बाद में प्रकट होता है। उदाहरण के लिए, एक विषम मान n = 21 के लिए, पहला पूर्ण समाधान चरण 3138 पर दिखाई देता है, और अगले सम मान n = 22 के लिए, पहला पूर्ण समाधान चरण 628169 पर दिखाई देता है। तदनुसार, अगले विषम मान n = 23 के लिए, पहला पूर्ण समाधान चरण 9155 पर दिखाई देता है।

अंजीर। 7 एन के विभिन्न मूल्यों के लिए पहले पूर्ण समाधान तक छोटे समाधानों की संख्या

समीपवर्ती विषम मानों की तुलना में, क्रमशः n = 22 के लिए पुनरावृति चरणों की संख्या 200.2 और 68.6 गुना अधिक है। यह विशेष रूप से n = 34 के लिए गिनती के समय में स्पष्ट है। यहां, पहला पूर्ण समाधान क्रमशः 826 337 184 वें चरणों में और निकटतम विषम संख्याओं (33, 35) के लिए 50 704 900 वें और 84 888 759 वें चरणों में दिखाई देता है। बढ़ते हुए एन के साथ पहले पूर्ण समाधान की उपस्थिति से पहले लघु समाधानों की संख्या के मोनोटोनिक विकास के उल्लंघन के बारे में भी कहा जाना चाहिए। N के मानों के लिए, यह n = 19 पर होता है, विषम मान के लिए, n = 24 और n = 26 पर।

8. क्या सभी पूर्ण समाधानों की सूची में प्रत्येक पंक्ति की सेल आवृत्ति समान है?

Nxn- आकार का निर्णय मैट्रिक्स, जो एक शतरंजबोर्ड के एनालॉग के रूप में कार्य करता है, एक दृश्य की तरह है जिस पर सभी घटनाएँ होती हैं। इस दृश्य पर बनने वाले किसी भी पूर्ण समाधान में विभिन्न पंक्तियों की कोशिकाओं के सूचक होते हैं, क्योंकि ऐसी प्रत्येक कोशिका समाधान खोज शाखा में एक नोड है। प्रश्न जो हमें रूचि देगा, वह निम्नलिखित है: क्या प्रत्येक पंक्ति में भार विभिन्न कोशिकाओं के लिए समान है जब सभी पूर्ण समाधानों की सूची बनाते हैं? जाहिर है, उच्च आवृत्ति मूल्य, पूर्ण समाधानों की सूची बनाने में इस सेल की गतिविधि जितनी अधिक होगी। इसे स्थापित करने के लिए, हम प्रत्येक पंक्ति के लिए निर्धारित करते हैं, सभी पूर्ण समाधानों की एक सूची के आधार पर, विभिन्न सूचकांकों की सापेक्ष आवृत्ति। सबसे पहले, हम आकार n = 8 के समाधान मैट्रिक्स के लिए विश्लेषण करते हैं। आइए हम अनुक्रम में पूर्ण समाधानों की सरणी की प्रत्येक पंक्ति की जांच करते हैं और विभिन्न सूचकांक मूल्यों की आवृत्ति निर्धारित करते हैं। तालिका 2 प्रत्येक आठ पंक्तियों में और अंजीर में अलग-अलग कोशिकाओं की निरपेक्ष गतिविधि आवृत्तियों के संबंधित मूल्यों को दिखाती है। 8

तालिका 2. सभी पूर्ण समाधानों की सूची के विश्लेषण के आधार पर, 8x8 निर्णय मैट्रिक्स की आठ पंक्तियों में से प्रत्येक में सेल गतिविधि की निरपेक्ष आवृत्ति

पंक्ति \ col	1	2	3	4	5	6	7	8
1	4	8	16	18	18	16	8	4
2	8	16	14	8	8	14	16	8
3	16	14	4	12	12	4	14	16
4	18	8	12	8	8	12	8	18
5	18	8	12	8	8	12	8	18
6	16	14	4	12	12	4	14	16
7	8	16	14	8	8	14	16	8
8	4	8	16	18	18	16	8	4

4 ग्राफ़ का एक समूह प्रस्तुत किया गया है, जहाँ प्रत्येक ग्राफ़ एक पंक्ति में सापेक्ष आवृत्तियों में परिवर्तन की विशेषता बताता है। मूल रूप से महत्वपूर्ण निष्कर्ष जो प्राप्त किए गए सभी डेटा के विश्लेषण से निकाला जा सकता है, इस प्रकार है:

• मनमाना आकार n के निर्णय मैट्रिक्स के लिए, i- वें पंक्ति की कोशिकाओं की गतिविधि सेल n-i + 1 की गतिविधि के साथ मेल खाती है, अर्थात। पहली पंक्ति की कोशिकाओं की गतिविधि हमेशा अंतिम पंक्ति की कोशिकाओं की गतिविधि के साथ मेल खाती है, क्रमशः दूसरी पंक्ति की कोशिकाओं की गतिविधि प्रायद्वीपीय पंक्ति की कोशिकाओं की गतिविधि के साथ मेल खाती है, आदि।
  
  यदि n विषम है, तो केवल समाधान मैट्रिक्स की मध्य पंक्ति में सममितीय युग्म नहीं होता है, अन्य सभी कोशिकाओं के लिए, उपरोक्त नियम मान्य है।
• हम इसे "समाधान मैट्रिक्स की विभिन्न पंक्तियों की कोशिकाओं की गतिविधि के क्षैतिज समरूपता की संपत्ति" कहते हैं । इस कारण से, हमने आकार n = 8 के निर्णय मैट्रिक्स के लिए केवल 4 ग्राफ़ प्रस्तुत किए, क्योंकि पंक्तियों (1, 8), (2.7), (3.6) और (4.5) के लिए सेल गतिविधि के संबंधित ग्राफ़ पूरी तरह से समान हैं।

यह भी ध्यान दिया जाना चाहिए कि आवृत्ति मान मैट्रिक्स को दो समान भागों में विभाजित करने वाली ऊर्ध्वाधर अक्ष के बारे में सममित हैं (एन के एक मूल्य के मामले में भी), या मध्य स्तंभ (एन के एक विषम मूल्य के मामले में) से गुजरते हैं। हम इसे "समाधान मैट्रिक्स की विभिन्न पंक्तियों की कोशिकाओं की गतिविधि के ऊर्ध्वाधर समरूपता संपत्ति" कहते हैं ।

इसके अलावा, तालिका 2 के विश्लेषण से निम्नानुसार, समाधान मैट्रिक्स में आवृत्तियां बाएं और दाएं मुख्य विकर्णों के संबंध में सममित हैं।

अंजीर। 8 पूर्ण समाधानों की सूची बनाते समय संबंधित पंक्तियों की सेल गतिविधि, n = 8

मुझे लगता है कि समस्या के बयान में प्रतिबंधात्मक नियमों की मौजूदगी, और गैर-नियतत्ववाद की संबंधित संपत्ति, विभिन्न रूपों में नोड्स के बीच एक प्रकार का सामंजस्यपूर्ण संबंध है। खोज की वे शाखाएं जो इन नियमों में फिट होती हैं - एक पूर्ण समाधान के गठन की ओर ले जाती हैं। खोज की शेष शाखाएं, कुछ कदम पर, इन नियमों का उल्लंघन करती हैं, और परिणामस्वरूप, छोटे निर्णयों के रूप में "अपनी यात्रा पूरी करें"। यहां यह ध्यान दिया जाना चाहिए कि निर्णय मैट्रिक्स की कोशिकाओं का प्रक्षेपण प्रभाव समूह के भीतर केवल एक स्थानीय संबंध है, उनके बीच समन्वित कार्यों के लिए कोई निर्धारित नियम नहीं हैं। कोशिकाओं की सामूहिक गतिविधि केवल प्रतिबंधात्मक नियमों के प्रभाव के परिणामस्वरूप होती है। इसलिए, एक दिलचस्प सवाल खुला रहता है, गैर-निर्धारक कारकों की तरह प्रतिबंधात्मक नियम, निर्णय मैट्रिक्स की कोशिकाओं को प्रभावित करते हैं, जो अंततः एक "सामंजस्यपूर्ण" सेल गतिविधि मैट्रिक्स के गठन की ओर जाता है - क्षैतिज और ऊर्ध्वाधर अक्षों के संबंध में सममित, साथ ही साथ बाएं के संबंध में। और सही मुख्य विकर्ण। क्या यह केवल इस समस्या की एक विशेषता है, या यह अन्य गैर-निर्धारक समस्याओं के लिए भी है?

9. फॉरवर्ड ट्रैकिंग किस लाइन नंबर से होती है - बैक ट्रैकिंग एल्गोरिदम चालू?

यदि हम रानी के स्थान के लिए निर्णय मैट्रिक्स में अनुक्रमिक पंक्ति चयन एल्गोरिथ्म के संचालन का पालन करते हैं, तो हम देख सकते हैं कि एक निश्चित रेखा से शुरू, जिसे हम "स्टॉपर" कहेंगे, "आगे" ब्रेकिंग की प्रक्रिया होती है। खोज शाखा में, यह पहली पंक्ति है जहां मुफ्त की उपलब्धता के साथ समस्याएं हैं

अंजीर। निर्णय मैट्रिक्स (भाग -1) के आकार पर एन रोक स्टॉप राउर इंडेक्स के अनुपात की निर्भरता

रानी के स्थान के लिए स्थिति। यह इस लाइन से है कि बैक ट्रैकिंग एल्गोरिदम को पहले किए गए कार्यों के निशान को साफ़ करने के लिए चालू किया जाता है और वापस लौटता है। यह वह रेखा है जिस पर पहला लघु समाधान दिखाई देता है।

अंजीर। 9-2 निर्णय मैट्रिक्स के आकार पर एन रोक स्टॉप राउर इंडेक्स के अनुपात की निर्भरता (भाग -2)

"StopRow" लाइन का सूचकांक, जिसके साथ कठिनाइयाँ आगे बढ़ने लगती हैं, निर्णय मैट्रिक्स के आकार n पर निर्भर करता है। यदि हम इस सूचकांक के अनुपात पर विचार करते हैं, जिसे हम स्टॉपइंड द्वारा समाधान मैट्रिक्स n के आकार में निरूपित करते हैं, तो, जैसा कि चित्र 9-1 से देखा जा सकता है, जहां प्रारंभिक मान n = (7, ..., 99) के लिए गणना परिणाम प्रस्तुत किए जाते हैं, यह अनुपात किसी बड़े या छोटे पर उतार-चढ़ाव करता है। पक्ष और कम हो जाता है। N = (100, ..., 300) में वृद्धि के साथ, यह अनुपात 0.619 - 0.642 (छवि 9-2) के बीच में उतार-चढ़ाव करता है, और n में और वृद्धि के साथ, हम निम्नलिखित परिणाम प्राप्त करते हैं (n के मान क्रम से दिए गए हैं, और कोष्ठक में मान है) स्टॉपइंड और स्टॉपइंड / एन अनुपात: 1000 (619, 0.6190), 2000 (1239, 0.6195), 3000 (1856, 0.6187), 4000 (2473, 0.6182), 5000 (3091, 0.6182)। आश्चर्यजनक रूप से, यह तर्क दिया जा सकता है कि स्टॉप। -लाइन निर्णय मैट्रिक्स को सुनहरे अनुपात नियम के अनुसार विभाजित करती है : अर्थात्, StopInd / n अनुपात एक छोटी राशि से भिन्न होता है (n-StopInd) / StopInd एक छोटी राशि से बढ़ता है जो n के साथ शून्य तक जाता है। उदाहरण के लिए, n / 5000 के बीच संबंधों के बीच अंतर है। 3091/5000 और 1909/3091 0.006 है, जो इन दोनों संबंधों के औसत का 0.1% से कम है।

ग्राफ दो आंकड़ों में दिखाया गया है 9- (1,2) में परिवर्तनशीलता का एक गैर-यादृच्छिक रूप है, जो एक "संगीतमय सीढ़ी" पर एक रिकॉर्डिंग जैसा दिखता है। बार-बार कूदता है और कुछ अनियमित आवधिकता के साथ स्टेप वाइज नीचे गिरता दिखाई देता है। जाहिर है, इस तरह के वक्र व्यवहार के लिए कुछ कारण है, और शायद यह शोध के लिए रुचि का होगा। इस कारण से, अधिक विस्तृत विज़ुअलाइज़ेशन के उद्देश्य से, ग्राफ़ को दो आंकड़ों में प्रस्तुत किया गया था।

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

निष्कर्ष

• यदि, प्रकाशन को देखते हुए, हम एक निष्कर्ष पर पहुँच गए हैं, तो स्वाभाविक रूप से यह सवाल उठेगा: "लेख शीर्षक में वन बिलियन क्वीन्स प्रॉब्लम सॉल्यूशन का क्या अर्थ है?" हैबर के लिए प्रकाशन की तैयारी में, मैंने सोचा कि एक व्यक्ति जिसके पास हीरा है, जहां हीरे का खनन होता है, उसे अपने दोस्तों और रिश्तेदारों को कम से कम एक हीरा देना चाहिए, अन्यथा यह अनुचित होगा। इसलिए, मैं हब्र समुदाय के सभी सदस्यों को एक उपहार पेश करना चाहता हूं: प्रतिभागियों, आयोजकों, आगंतुकों। जैसा कि नाम से ही स्पष्ट है, यह एक बिलियन-बिलियन आकार की शतरंज की बिसात पर एक अरब रानियों को वितरित करने की समस्या का समाधान है।
  
  बेशक, यह एक मुखर हीरा नहीं है, लेकिन बौद्धिक कला के सच्चे पारखी लोगों के लिए, "कुछ प्रकार के हीरे" से अधिक मूल्यवान हो सकता है। इसके अलावा, हीरे दुनिया भर में कई अलग-अलग हैं, और यह समाधान अब तक केवल एक प्रति में है। और हमारे बाइट-गॉड (*) देखता है कि मैं यह ईमानदारी से कर रहा हूं।
  परिणामी समाधान एक बिलियन नंबरों की एक आयामी सरणी है, जिसे माटलैब .mat प्रारूप में प्रस्तुत किया गया है और यह उपलब्ध है: Google ड्राइव पर एक बिलियन क्वींस समस्या समाधान
  -इस सरणी का पहला तत्व पहली पंक्ति में रानी की स्थिति को दर्शाता है, दूसरा तत्व - दूसरी पंक्ति में स्थिति, आदि। यह nBillion संभव समाधानों में से केवल एक समाधान है। और nBillion का मूल्य इतनी बड़ी संख्या है कि इसे अनंत का करीबी रिश्तेदार माना जा सकता है।
  
• मुझे ऐसा लगता है कि इस समाधान को आभासी बौद्धिक मूल्यों की श्रेणी के लिए जिम्मेदार ठहराया जा सकता है। हम कह सकते हैं कि "यह कुछ ऐसा है जिसमें कुछ है।" वे वास्तव में "छुआ नहीं जा सकता", इसलिए यह केवल संवेदनाओं के स्तर पर चेतना में माना जाता है। वहां, वास्तव में, एक अद्भुत आदेश और स्पष्ट और निहित सद्भाव है। यह एक विशुद्ध रूप से प्रतीकात्मक उपहार है (शाब्दिक और आलंकारिक रूप से) जिसे समुदाय के सभी सदस्यों को संबोधित किया जाता है। मुझे लगता है, " आप हर किसी की तरह नहीं हैं ।"
  
  (मुझे आशा है कि कोई व्यक्ति "उपहार घर ले जाता है।" फ़ाइल काफी बड़ी है - 3.7 जीबी। यह साफ, सत्यापित डेटा है। यह Google ड्राइव चेतावनी प्रदर्शित करेगा - समझ के साथ इसका इलाज करें)
  
• यह निर्णय लेने से पहले, मैंने इस तरह के उपहार की व्यक्तिगत-सामूहिक प्रकृति के बारे में सोचा। क्या यह संभव है कि एक को मूल और बाकी को प्रतियों के साथ प्रस्तुत किया जाएगा? लेकिन समाधान सरल था। इस मामले में, "मूल" और "कॉपी" की सामान्य "रोज़" अवधारणाएं अपना अर्थ खो देती हैं। हम प्रतिलिपि नहीं बनाते हैं, लेकिन एक और मूल बनाते हैं। और "मूल" सभी के लिए समान हैं और समान रूप से समान हैं।
  
• मुझे लगता है कि रिश्तेदारों की कंपनी में, आप सबसे अधिक केवल एक ही ऐसे "बौद्धिक उत्पाद" प्राप्त करेंगे। अगर आप अपनी सास को इस तरह के उपहार के बारे में बताएंगे तो यह मज़ेदार होगा: "एक माँ की कल्पना करें, जिसकी शतरंज की बिसात 50,000 किमी तक मापी जाती है, जिस पर 1 बिलियन रानियों को इस तरह से वितरित किया जाता है कि कोई अन्य करीबी सीमा पर नहीं दिखता है"। कौन जानता है, शायद इसके बाद, दामाद की अधिक सराहना की जाएगी, क्योंकि उसे ऐसा अजीब उपहार दिया जाता है।
  

मैं सभी हाबर समुदाय के स्वास्थ्य, सफलता और कल्याण की कामना करता हूं। नया साल हम सबके लिए शुभकामनाएँ ला सकता है।

(*) - चूँकि यह ऑब्जेक्ट के नाम से संदर्भित है, इसलिए इसका विवरण भी दिया जाना चाहिए।
बाइट भगवान का मतलब एक बहुआयामी इकाई है, जिसमें शून्य और सभी शामिल हैं, जो हर मायने में उचित है और सभी दिशाओं में अनंत है। इस अंतरिक्ष में शून्य और लोगों का कोई भी क्रम निश्चित ज्ञान का प्रतिनिधित्व करता है।

संदर्भ

[४] मैक्स बेज़ेल, ens-रानियों की समस्या का प्रस्ताव ", बर्लिनर शेचज़ितुंग, वॉल्यूम
३ (१mitted४mitted), पृष्ठ ३६३। (लेखक नाम \ _ स्कछफ्रेन्ड के तहत प्रस्तुत किया गया। ")

[५] फ्रांज नावक, ब्रीफचसेलन मिट एलेन फर ऑल ", इलिसपिरेट ज़ेतुंग, वॉल्यूम
377 नंबर 15 (1850), पृष्ठ 182।

[६] बेल जॉर्डन; स्टीवंस ब्रेट (2009)। "N- रानियों के लिए ज्ञात परिणामों और अनुसंधान क्षेत्रों का सर्वेक्षण।" असतत गणित। 309 (1): 1-31

[,] जेंट, इयान पी ।; जेफरसन, क्रिस्टोफर; कोकिला, पीटर (अगस्त 2017)। "एन-क्वींस कंप्लीशन की जटिलता"। आर्टिफिशियल इंटेलिजेंस रिसर्च जर्नल। AAAI प्रेस। 59: 815–848

[[] डब्ल्यू। कोस्टर्स और ऑल, एन-क्वींस - ३४२ संदर्भ, (२० नवंबर, २०१ K)

[९] एनजेए स्लोअन, ऑन-लाइन इनसाइक्लोपीडिया ऑफ इंटेगर सीक्वेंस, इलेक्ट्रॉनिक रूप से प्रकाशित। 2016