टुकड़ों का कौन सा संग्रह कानूनी है?
(सफेद और काले) शतरंज के टुकड़ों के एक संग्रह को कानूनी रूप से कॉल करें यदि यह कानूनी शतरंज खेल की स्थिति में होता है। उदाहरण के लिए, KQRRBBNNPPPPPPPPkqrrbbnnppppppppखेल की शुरुआत में संग्रह है। ऐसा लगता है कि इसका कोई भी उपसमुच्चय (अभी भी दो राजाओं को सम्मिलित करना) संभव है। लेकिन कभी-कभी आपके पास बहुत सारे प्रचार हो सकते हैं, इसलिए उदाहरण के Kkqqqqqqqqलिए संभव है यदि काला सभी आठ प्यादों को रानियों को बढ़ावा देता है जबकि अन्य सभी टुकड़ों पर कब्जा कर लिया जाता है।
टुकड़ों का कौन सा संग्रह कानूनी है?
MathOverflow पर यह उत्तर प्रमाण के बिना / राज्यों को बताता है कि कानूनी संग्रह वे हैं जो निम्नलिखित निम्नलिखित कार्यों का उपयोग करके शुरुआती संग्रह से प्राप्त किए जा सकते हैं:
किसी भी (गैर-राजा) टुकड़े को हटा दें और अधिकतम एक सफेद और अधिकतम एक काले मोहरे पर प्रचार करें।
एक मोहरा हटाएं और एक ही रंग के अधिकांश मोहरे पर और विपरीत रंग के अधिकांश दो प्यादों में प्रचार करें।
क्या यह चरित्र चित्रण सही है?
जवाब
हां, लक्षण वर्णन सही है, और कुल मिलाकर 58,084,310 कानूनी संग्रह हैं।
हेडवे बनाने के लिए, हमें तुच्छताओं में गोता लगाने से बचने के दौरान सटीकता के नुकसान से बचने के लिए सही स्तर के प्रवचन की आवश्यकता होती है।
विलोपन चाल की आवश्यकता और पर्याप्तता
सभी कानूनी संग्रहों तक पहुँचने के लिए दो प्रकार के संचालन को आवश्यक और पर्याप्त बनाने का सुझाव दिया गया था:
(1) Delete a (non-K) officer & promote at most 1 wP and 1bP
(2) Delete a P & promote at most 1P of that color and at most 2Ps of the other color.
सबसे पहले, दो मापदंड आवश्यक हैं। फ़ाइल को अनब्लॉक करने के लिए कैप्चर करना होगा। एक अधिकारी को पकड़ने से दोनों प्यादों को बढ़ावा देने के लिए एक फ़ाइल से अनुमति मिलेगी। पड़ोसी फ़ाइल से मोहरा कैप्चर करने वाला मोहरा अधिक कुशल होता है, क्योंकि यह तीन प्यादों को बढ़ावा देने की अनुमति देता है।
स्थिति भी पर्याप्त है, जैसा कि बोर्ड को 4 जोड़ी फाइलों में विभाजित करके देखा जा सकता है। हमें यह धारणा बनानी होगी कि राजा कार्रवाई के रास्ते से बाहर रह सकते हैं। एक उदाहरण के लिए बाद में देखें जो इस धारणा की वैधता की पड़ताल करता है।
"मांग की आपूर्ति"
शायद इस सवाल पर आगे बढ़ना कि कौन से संग्रह इस तरह से प्राप्त करने योग्य हैं:
- प्रत्येक पक्ष के लिए दृश्यमान "गैर-आरंभिक अधिकारी" की संख्या की गणना करें (पहले से परे रानी, उस प्रकार के दूसरे से परे अन्य अधिकारी): N_w & N_b
- प्रत्येक तरफ "awol pawns" की संख्या की गणना करें: (NSOs में मोहित किए गए पंजे की गिनती नहीं की जाती है): A_w & A_b
- प्रत्येक पक्षों के लिए "लापता अधिकारियों" की संख्या की गणना करें (लापता रानी, या उस प्रकार के दूसरे से कम अन्य अधिकारी): M_w & M_b
फिर निम्नलिखित सुरुचिपूर्ण "आपूर्ति और मांग" असमानताएं एक कानूनी संग्रह के लिए आवश्यक और पर्याप्त मानदंड हैं:
M_b + 2*A_b >= N_w - M_w - A_w
M_w + 2*A_w >= N_b - M_b - A_b
व्हाइट एंड ब्लैक द्वारा शर्तों को समूहीकृत करना, बाएं हाथ की ओर "आपूर्ति" है, दाहिने हाथ की तरफ "मांग" है। आपूर्ति हमेशा गैर-नकारात्मक होती है, इसलिए यदि मांग शून्य या कम है, तो यह हमेशा संतुष्ट है। इसी तरह, 8+ की आपूर्ति किसी भी मांग को पूरा कर सकती है जो हो सकती है।
यहाँ एक उदाहरण है। क्या हम बोर्ड पर 18 रानियां रख सकते हैं? हाँ!
N_w = N_b = 8
(because 8 promoted pawns on each side)
A_w = A_b = 0
(every missing pawn was promoted)
M_w = M_b = 6
(all Rs, Bs & Ns were captured)
M_b + 2*A_b >= N_w - M_w - A_w
translates to:
6 + 2*0 >= 8 - 6 - 0
6 >= 2
तो यह कानूनी है। इसी तरह ब्लैक मांग के लिए व्हाइट सप्लाई के लिए। यहां तक कि अगर हमारे पास बोर्ड पर अभी भी शूरवीर हैं, तो M_b = M_w = 4, असमानता 4> = 4 होगी, इसलिए अभी भी कानूनी है।
साथी / गतिरोध के अलावा
कुछ लोग आश्चर्य करते हैं कि क्या इस तरह की स्थिति बिना साथी या गतिरोध के हासिल की जा सकती है, जो एक उचित सवाल है। इसका जवाब है हाँ। यह साबित करने के लिए कहने जैसा है कि 450 ग्राम कॉर्नफ्लेक्स सभी एक बॉक्स में फिट होंगे। यह आम अनुभव की बात है कि कोई सिर्फ पैक हिला सकता है और कॉर्नफ्लेक्स बस जाता है। बॉक्स में बहुत सारे कॉर्नफ्लेक्स नहीं हैं। हालांकि यह स्पष्ट रूप से अवैध है, राजाओं और 34 (!) तक के सफेद कतारों को बिना मेट या गतिरोध के मंडराने की व्यवस्था करना संभव है। इस घनत्व पर, यह थोड़ा तंग हो रहा है, लेकिन यह विचार प्रयोग दिखाता है कि जब हम केवल 18 रानियों के साथ काम कर रहे हैं, जहां अधिक अनुकूल मित्र दुश्मन के खिलाफ ढाल सकते हैं, वहां भारी मात्रा में स्लैक, और मजबूर साथियों के बारे में चिंता करने की कोई आवश्यकता नहीं है। या गतिरोध। यहां तक कि 18 रानियों के साथ, शतरंज की बिसात, कॉर्नफ्लेक्स का बहुत खाली डिब्बा है :-)
संग्रह की गिनती
पहले सिर्फ व्हाइट यूनिट पर ध्यान दें। कितने कानूनी सफेद संग्रह हैं? 8,694 है। यहाँ एक त्वरित प्रमाण है।
आज्ञा देना की संख्या को दिखाई प्रचारक, शूरवीर या बिशप (यानी किसी भी प्रकार के लिए 2 के मूल पूरक से परे अधिकारी)। (सममिति कारणों से, रानियों को इसके बजाय कुछ पैराग्राफ में निपटाया जाता है।)
V (k) R, N, B के विभिन्न संयोजनों की संख्या है जो इसे प्राप्त करते हैं।
v(0) = 27:
because there may be 0-2 remaining of each of R,N,B.
For k>0, v(k) = (k^2 + 15*k + 38)/2
e.g.:
v(1) = again 27:
3 ways to pick one of R,N,B to be 3;
& 0-2 possible for each of the other two types.
v(2) = 36:
27 ways to have 4,0-2,0-2;
& 9 ways to have 3,3,0-2.
तब अन्य 8-के प्यादे अभी भी पीएस हो सकते हैं, या क्यूएस में बदल सकते हैं, या कब्जा कर लिया जा सकता है।
Q को दृश्यमान रानी पदोन्नति की संख्या (अर्थात 1 के मूल पूरक से आगे की रानी) होने दें।
आइए u_k (q) विभिन्न कॉम्बीनेटरियल तरीकों की संख्या हो जो हम इसे प्राप्त कर सकते हैं (जीवित प्यादों, रानियों और कैद किए गए प्यादों के संदर्भ में)
u_k(0) = 2*(9-k)
because we can have 0 to 8-k pawns, and the rest are captured,
independently we have 0 or 1 queen.
For q>0, u_k(q) = (9-k-q)
s(k) = sum(q=0,...,8-k) [u_k(q)]
= 2*(9-k) + (8-k) + (7-k) + ... 1
= (9-k)(12-k)/2.
Check:
s(8) = 2: 0-1Q
s(7) = 5: 0P,0-2Q; 1P;0-1Q
...
s(0) = 54: = 55-1
So the total number of of legal White collections is:
sum(k=0...8) [s(k)*v(k)]
= 8,694
ये सभी सफेद संग्रह वास्तव में प्राप्त करने योग्य हैं, उदाहरण के लिए यदि ब्लैक में केवल नंगे राजा शेष हैं, लेकिन वास्तव में कई अन्य स्थितियों में भी: आपूर्ति / मांग असमानताएं बहुत मांग नहीं हैं।
अगले अभ्यास में N_w, M_w, A_w के प्रत्येक संयोजन के लिए गिनती शामिल है कि कितने व्हाइट संग्रह मौजूद हैं।
मैंने संग्रह की निम्न तालिका की गणना की, बोर्ड पर टुकड़ों की कुल संख्या के अनुसार क्रमबद्ध, जैसा कि इस तालिका में दिखाया गया है:
2-32 से इकाइयों की प्रत्येक संख्या के लिए, यह दिखाता है
- v_0: आपूर्ति-मांग की चिंता किए बिना बुनियादी उम्मीदवारों की संख्या,
- v_1: वह संख्या जिसके पास आपूर्ति-मांग के विरुद्ध एक भी असफलता है,
- v_2: संख्या, जिनकी आपूर्ति-माँग के विरुद्ध दोहरी विफलता है।
दोहरी गिनती से बचने के लिए, कानूनी पदों की संख्या v_1 - 2 * v_2 + v_3 के रूप में गणना की जाती है। मेरी गणना क्रिउकोव के पूर्व परिणामों से बिल्कुल मेल खाती है।
ध्यान दें कि 25 इकाइयों तक पहुंचने तक कोई विफलता नहीं होती है। ऐसा इसलिए है क्योंकि 8 कैप्चर के साथ, सभी उम्मीदवार पदोन्नति संग्रह हासिल किए जा सकते हैं।
एक "अतिरिक्त क्रेडिट" खुला सवाल (प्रगति में काम)
रेट्रो उत्साही आगे बिशप के रंग के बीच भेद करते हैं, क्योंकि वह एक आक्रमणकारी है। यह संभावित वैधता पर एक प्रमुख, दृश्य प्रभाव है, शतरंज टेबलबेस के लिए आवश्यक वर्गीकरण का हिस्सा है, और रचना में एक सौंदर्यवादी चिंता भी है। तत्संबंधी शब्द "गैर-मानक अधिकारी" (क्वीन या "टिंटेड" बिशप्स हैं जो पहले से परे हैं; दूसरे से परे बदमाश या शूरवीर)। लापता अधिकारियों की गिनती उन्हीं 5 प्रकारों पर आधारित है। कानूनी संग्रहों को चिह्नित करने के लिए अतिरिक्त असमानताएं और पर्याप्तता का निर्धारण अब पर्याप्त रूप से अधिक जटिल है।
सबसे अच्छा तरीका यह हो सकता है कि पहले अनुकूलित आपूर्ति / मांग की असमानताओं को लागू किया जाए। फिर पूछ सकते हैं कि सही टिंट के लिए कुछ बिशप को "नग" करने के लिए कितने अतिरिक्त प्यादा कैप्चर की आवश्यकता होती है?
एक अधिकारी / प्यादा के एक मोहरे पर कब्जा करने के परिणामस्वरूप क्रमशः 2/3 प्यादों का एक ही टिंट वर्गों पर प्रचार किया जाएगा, लेकिन ऐसा लगता है कि ऐसे प्रत्येक बैच के लिए, हम स्वतंत्र रूप से टिंट का चयन करने के लिए स्वतंत्र हैं।