डेली कोडिंग प्रॉब्लम: चेकमेट चेक करने के लिए अपने कोडिंग स्किल्स का इस्तेमाल करें

चेकमेट की जाँच करें

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

तो आगे की हलचल के बिना, आइए देखते हैं हमारी समस्या। हालांकि शुरू करने से पहले, हमेशा की तरह, दो अस्वीकरण:

• ये समस्याएं अद्भुत न्यूज़लेटर डेली कोडिंग प्रॉब्लम द्वारा प्रदान की जाती हैं, जिसे आप सब्सक्राइब कर सकते हैं यहाँ : इसे देखें और अपनी दैनिक चुनौती को भी हल करने का प्रयास करें!
• मैं एक विशेषज्ञ प्रोग्रामर नहीं हूं, बस एक लड़का हूं जो अपने प्रयासों (और असफलताओं) को साझा करना पसंद करता है। यदि आपके पास कोई बेहतर विचार या समाधान है, तो आप इसे साझा करने के लिए स्वागत से अधिक हैं: मुझे यह देखना अच्छा लगेगा कि आप इससे निपटते हैं!

समस्या

आज की समस्या शुरू में Oracle द्वारा पूछी गई थी।

आपको शतरंज बोर्ड पर टुकड़ों की स्थिति का प्रतिनिधित्व करने वाले 8 से 8 मैट्रिक्स के साथ प्रस्तुत किया जाता है। बोर्ड पर केवल काले राजा और विभिन्न सफेद टुकड़े हैं। इस मैट्रिक्स को देखते हुए, निर्धारित करें कि राजा चेक में है या नहीं।

प्रत्येक टुकड़ा कैसे चलता है, इसके विवरण के लिए देखें यहाँ .

उदाहरण के लिए, निम्नलिखित मैट्रिक्स दिया गया है:

 ...K.... ........ .B...... ......P. .......R ..N..... ........ .....Q..

आपको True वापस करना चाहिए , क्योंकि बिशप तिरछे राजा पर हमला कर रहा है।

समस्या बिल्कुल स्पष्ट है, इसलिए हम इसके बारे में अधिक विस्तार से नहीं बताएंगे। हालांकि हमें कुछ शुरुआती विशिष्टताओं की आवश्यकता है:

1. हम एक ग्राफ पर हैं, बोर्ड पर नहीं: हम बोर्ड पर केस के केंद्र के रूप में समस्या द्वारा दिए गए प्रत्येक बिंदु पर विचार करेंगे। नतीजा वही है;
2. सफेद राजा अन्य 7 प्यादों के साथ छुट्टी पर चला गया है: राजा और प्यादे सभी टुकड़ों में सबसे अधिक उबाऊ हैं और उन्हें हटाने से हमारा समाधान उतना नहीं बदलने वाला है;
3. हमें यह सत्यापित करने की आवश्यकता है कि क्या राजा इसी मोड़ पर नियंत्रण में है , जिसका अर्थ है कि यदि वह आगे नहीं बढ़ता है तो अगले सफेद मोड़ पर इसे लिया जाएगा;
4. शुरुआत में खेल द्वारा स्थितियां दी जाती हैं : मैं अतिव्यापी टुकड़ों या गलत शुरुआती स्थितियों के सत्यापन में नहीं जाऊंगा।

समाधान

सबसे पहले, टुकड़ों और चाल-सेटों का एक त्वरित पुनर्कथन:

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

और चूंकि वे सभी राजा को जल्द से जल्द पकड़ने में रुचि रखते हैं, इसलिए हम यह मान सकते हैं कि उनका अगला कदम काले राजा को पकड़ने वाला होगा । इसलिए, चूंकि हम काले राजा की स्थिति को भी जानते हैं, हमें केवल यह जांचने की आवश्यकता है कि क्या काले राजा की स्थिति अन्य मोहरों की संभावित अगली चालों में से एक है। यदि ऐसा है, तो अगले सफेद मोड़ के दौरान सफेद टुकड़ा काले राजा को पकड़ने के लिए वहां जाएगा।

स्थिति कुछ इस तरह दिखती है:
ऊपर की तस्वीर में आप देख सकते हैं (… मुझे उम्मीद है, भ्रम के लिए खेद है …) सफेद तरफ प्रत्येक टुकड़े की हर संभव चाल , अलग-अलग रंगों से रंगी हुई, और ऊपर का काला राजा पकड़े जाने की प्रतीक्षा कर रहा है। तो उदाहरण के लिए बिशप, (2,7) से शुरू होकर, (1,6), (1,8), (3,8), (3,6), (4,5), (5,) तक जा सकता है। 4) और इसी तरह।

मैंने बस बेतरतीब ढंग से इन टुकड़ों की शुरुआती स्थिति तय की क्योंकि यह अंतिम परिणाम को प्रभावित नहीं करता है।

चूँकि हम 8x8 ग्राफ़ पर हैं (स्पष्ट होने के लिए, कोई भी अन्य आयाम उसी तरह काम करेगा) और हमारे पास प्रत्येक टुकड़े के शुरुआती निर्देशांक हैं, हम निर्देशांक x, y की श्रृंखला बना सकते हैं जो हमारे टुकड़े अगली चाल होंगे। ऐसा करने के लिए, हम पहले प्रत्येक टुकड़े के लिए एक वर्ग को परिभाषित करते हैं, उसके निर्देशांक को परिभाषित करते हैं और फिर वहाँ से हर संभव चाल की गणना करने के लिए नियमों को परिभाषित करते हैं।

टुकड़े - प्यादा

आइए प्यादा के साथ सरल शुरुआत करें। वैसे, मैं इसे पायथन में बना रहा हूं, क्योंकि यह इस समय सबसे लोकप्रिय भाषाओं में से एक है और यकीनन किसी के द्वारा सबसे अधिक पठनीय है। फिर भी, आपको यह जानने की आवश्यकता होगी कि अब से किस वर्ग का पालन किया जा सकता है । यहाँ है इस अवधारणा की एक सुंदर साफ व्याख्या।

आइए संक्षेप में समझाते हैं: हम पहले class Pawn वर्ग और __init__ इसके निर्देशांक x,y को परिभाषित करते हैं। उसके बाद, हम वहां से प्यादा संभावित चालों की गणना करने के लिए possibleMoves विधि को परिभाषित करते हैं। प्यादा चालें अपेक्षाकृत आसान होती हैं, इसलिए हम उन्हें केवल चर moves में जोड़ते हैं, यह जाँचने के बाद कि यह हमारे ग्रिड से बाहर नहीं जाती है, और moves सरणी वापस कर देता है। यहाँ ध्यान देने योग्य दो बातें, विशेष रूप से प्यादा के लिए:

1. हम सफेद मोहरे को नीचे से ऊपर की ओर बढ़ने पर विचार करते हैं, जैसे कि हम सफेद खिलाड़ी हैं जो अपने मोहरे को अपने प्रतिद्वंद्वी की ओर आगे बढ़ा रहे हैं। यह वास्तव में कुछ भी नहीं बदलता है, यह सिर्फ चीजों को क्रम में रखता है।

2. हम जानबूझकर सामान्य गति को छोड़ देते हैं , क्योंकि हम काले राजा को पकड़ने में रुचि रखते हैं: चूंकि प्यादा केवल तिरछे तरीके से कब्जा कर सकता है और हम टुकड़ों को अन्य दिशाओं में ले जाने की परवाह नहीं करते हैं, हम इसकी सामान्य गति को छोड़ सकते हैं।

   
   

अब हम बस मोहरे की चालों को उसके निर्देशांक देकर और possibleMoves विधि को कॉल करके देख सकते हैं, जैसे: print(Pawn(7,2).possibleMoves()) और हमें [(6,3),(8,3)] जैसा कुछ प्राप्त करना चाहिए [(6,3),(8,3)] .

इसके अलावा, आप शीर्ष पर देख सकते हैं कि हमने अपने ग्रिड आयामों को चर के रूप में परिभाषित किया है , इसलिए हम संभवतः उन्हें अन्य आयामों के बोर्डों पर एल्गोरिथम चलाने के लिए बदल सकते हैं।

अब चलो टावर पर चलते हैं।

मीनार

दोबारा, हम टावर क्लास को इसके निर्देशांक के साथ शुरू करते हैं और possibleMoves फ़ंक्शन को परिभाषित करते हैं। यहां सभी संभावित चालों को इकट्ठा करने के लिए हम टॉवर दो अक्षों पर सभी बिंदुओं को श्रेणीबद्ध करते हैं और प्रत्येक एकल निर्देशांक को चर moves में जोड़ते हैं, जो सभी लूपों के बाद वापस आ जाएगा। पहले की तरह, टावर चालों की जांच करने के लिए हम केवल print(Tower(5,3).possibleMoves()) सकते हैं और हमें कुछ इस तरह मिलना चाहिए: [(1,3), (2,3), (3,3), ..., (5,8)] .

बिशप

अब बारी बिशप की है।

टॉवर की तुलना में बिशप की चालें अधिक जटिल हैं, इसलिए हम यहां क्या हो रहा है, इसकी थोड़ी व्याख्या कर सकते हैं। मूल रूप से हमें इसकी शुरुआती स्थिति से शुरू होने वाले दो विकर्ण अक्षों पर अंक एकत्र करने की आवश्यकता है । क्लास और इनिट मेथड घोषित करने के बाद, हम दो वेरिएबल बनाते हैं: moves , पहले की तरह, और currentPos , जिसका उपयोग हम अपने अक्षों के साथ चलते हुए एकत्रित किए गए बिंदुओं पर नज़र रखने के लिए करेंगे। अब while लूप का उपयोग करते हुए, और यह जाँचते हुए कि हम अपने ग्रिड के बाहर नहीं जा रहे हैं, हम x और y उसी के अनुसार बढ़ाते और घटाते हैं जहाँ हम जाना चाहते हैं । उदाहरण के लिए, यदि हम इसकी शुरुआती स्थिति से ऊपर-बाएँ जाना चाहते हैं, तो हमें y मान को बढ़ाते हुए x मान को कम करना होगा। यदि हम दाईं ओर नीचे जाना चाहते हैं, तो हमें y मान को घटाते हुए x मान को बढ़ाना होगा और इसी तरह आगे भी। अंत में, हम बस एक बार फिर moves लौटाते हैं।

रानी

अब आप सोच सकते हैं: यदि टॉवर चालें जटिल हैं और बिशप और भी अधिक हैं, तो हम रानी को कैसे कोडित करने जा रहे हैं? दरअसल, एक साधारण ट्रिक की मदद से क्वीन मूव्स को कोड करना सबसे आसान है। फिर देखते हैं रानी।

ठीक है, यहाँ क्या हो रहा है? ठीक है, अगर हम इसके बारे में सोचते हैं, तो रानी के पास बिशप और टावर संयुक्त की समान चालें हैं । वह एक रानी की तुलना में टॉवर के आकार के बिशप मेचा-बॉट की तरह अधिक है। इस कारण से, उसकी चालों को कोडिंग करना वास्तव में सरल है। उसकी कक्षा घोषित करने के बाद हम बस उसकी possibleMoves बिशप और टावर की संभावित चालों के परिणामस्वरूप चालों के संघ सरणी के रूप में परिभाषित करते हैं।

ध्यान दें कि possibleMoves फ़ंक्शन में Bishop और Tower उदाहरणों को कॉल करते समय उनके पैरामीटर x और y self.x, self.y के रूप में दिया जाता है, इसलिए वे वास्तव में रानी निर्देशांक हैं।

शूरवीर

अब शूरवीर को!

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

राजा

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

समाधान कोड

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

अब हम केवल कुछ निर्देशांक के रूप में एक वेरिएबल blackKing बनाते हैं। फिर प्रत्येक टुकड़े के लिए हम इसकी कक्षा का एक उदाहरण बनाते हैं जिसे हमने अभी बनाया है और चाल के पूर्ण सेट की गणना करने के लिए possibleMoves विधि को कॉल करता है। एक बार हमारे पास होने के बाद, हम जांचते हैं कि blackKing निर्देशांक उन चाल-सेटों में मौजूद हैं या नहीं : यदि वे हैं, तो हम यह प्रिंट करते हैं कि राजा को उस विशेष टुकड़े द्वारा चेक किया गया है। यहाँ परिणाम कुछ इस प्रकार है:

 Pawn moves: [(8, 3), (6, 3)] Tower moves: [(1, 3), (2, 3), (3, 3), (4, 3), (6, 3), (7, 3), (8, 3), (5, 1), (5, 2), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8)] Check by the tower! Bishop moves: [(3, 8), (1, 6), (1, 8), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1)] Queen moves: [(4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (2, 1), (2, 3), (1, 4), (4, 1), (1, 2), (2, 2), (4, 2), (5, 2), (6, 2), (7, 2), (8, 2), (3, 1), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8)] Knight moves: [(4, 7), (4, 5), (8, 7), (8, 5), (5, 4), (7, 4), (7, 8), (5, 8)] Check by the knight!

मैंने उपरोक्त गन्दी छवि को संदर्भ के रूप में इस्तेमाल किया, ताकि आप जांच सकें कि राजा वास्तव में टावर और नाइट द्वारा चेक किया गया है।

चेक मेट

क्या होगा अगर हम यह भी गणना करना चाहते हैं कि क्या राजा के पास अभी भी जीवित रहने की कुछ संभावना है या यह वास्तव में चेक मेट है? इस उद्देश्य के लिए, हमें राजा की चालों के सेट की गणना करने की आवश्यकता है।

आइए इसका थोड़ा वर्णन करें। सबसे पहले, हम अपनी कक्षा को परिभाषित करते हैं और पहले की तरह समन्वय करते हैं। उसके बाद हम possibleMoves विधि बनाते हैं और राजा की संभावित चालों को कोड करते हैं (फिर से, मुझे पूरा यकीन है कि एक तेज़ तरीका है, लेकिन केवल 8 संभावित चालें हैं इसलिए ...)। उसके बाद, हम जाँचते हैं कि कौन सी चालें अवैध हैं (बोर्ड के बाहर जाएँ) और केवल validMoves लौटाएँ।

तो अब, यह जाँचने के लिए कि क्या राजा के पास अभी भी जीवित रहने का एक मौका है, हमें यह जाँचने की आवश्यकता है कि क्या उसकी कोई भी संभावित चाल चालों के दूसरे टुकड़े में नहीं है। ऐसा करने के लिए हम केवल बादशाह की चालों और दूसरी चालों पर लूप करते हैं।

इसलिए अभी भी हमारे राजा के बचने की उम्मीद है! उसके लिए भाग्यशाली मुझे लगता है …

समय जटिलता

हमेशा की तरह, इस समाधान की समय जटिलता पर एक संक्षिप्त नज़र डालें।

सबसे पहले, चूंकि प्रत्येक टुकड़ा एक वर्ग का एक उदाहरण है, हमें उस उदाहरण को आरंभ करने के समय पर विचार करना चाहिए।

• प्यादा या शूरवीर जैसे मोहरे के अंदर कोई लूप नहीं होता है और यह किसी चर आयाम पर निर्भर नहीं करता है, इसलिए हम उन्हें O(1) मान सकते हैं;
• टावर थोड़ा मुश्किल है: चूंकि इसमें लूप के लिए 4 शामिल हैं, आप तुरंत सोच सकते हैं कि इसकी समय जटिलता ओ (एन) है, है ना? वास्तव में, यदि हम इस बारे में सोचें कि टावर कैसे चलता है, तो हम देखेंगे कि चाहे वह बोर्ड पर कहीं भी रखा गया हो, उसकी चाल उसके ऊर्ध्वाधर और क्षैतिज अक्षों पर फ्री बोर्ड केस तक सीमित होती है। और चूंकि बोर्ड एक वर्गाकार है, हमारे पास अपने टावर को आगे बढ़ाने के लिए हमेशा 14 फ्री केस होंगे। तो इसकी समय जटिलता वास्तव में O(1) होनी चाहिए, जो निर्देशांक के 14 जोड़ों के लिए स्थिर है। यहाँ एक ग्राफिक उदाहरण है:

• दुर्भाग्य से, हम बिशप के लिए ऐसा नहीं कह सकते, चालों का कौन सा सेट थोड़ा अधिक जटिल प्रतीत होता है। मूल रूप से, इसमें 7, 9, 11 या 13 चालें होती हैं जो इस बात पर निर्भर करती हैं कि इसे बोर्ड पर कहाँ रखा गया है। इसलिए, उसकी चालों के सेट की गणना करने के लिए आवश्यक चरण उसकी स्थिति पर आधारित होते हैं, इस प्रकार हम O(n) के एक टीसी पर विचार कर सकते हैं।

• रानी को टॉवर और बिशप के संयुक्त कदमों के सेट की जरूरत है। चूंकि समय जटिलता का मूल्यांकन करते समय हमें सबसे खराब परिदृश्य पर ध्यान देना चाहिए , बिशप का टीसी टावर के टीसी पर प्रबल होता है। इस प्रकार, हमें रानी के लिए O(n) के एक टीसी पर भी विचार करना चाहिए।

• अंत में, राजा के पास चालों का एक कठिन कोडित सेट होता है, लेकिन एक सत्यापन प्रक्रिया भी शामिल होती है जो लूप के लिए उपयोग करती है । इसलिए तकनीकी रूप से, भले ही राजा की चालें किसी भी मामले में अपेक्षाकृत छोटी हों, हमें उसके tc को O(n) मानना चाहिए, वह भी बोर्ड पर उसकी स्थिति पर निर्भर करता है।

  
  

इस बिंदु पर, हम ब्लैक किंग की चेक स्थिति को सत्यापित करने और प्रिंट करने के लिए प्रत्येक टुकड़े के लिए लूप का उपयोग करते हैं। इससे हमें कोई समस्या नहीं होती है जहां टीसी स्थिर है (टॉवर लें, उदाहरण के लिए: हम इसकी 14 चालों की गणना करते हैं और फिर उन पर 14 बार लूप करते हैं, इसलिए हम इसे निश्चित समय भी मान सकते हैं)। फिर भी, जहां tc O(n) या उससे ऊपर है, वहां हमें परेशानी होने वाली है, क्योंकि हम एक लूप जोड़ रहे हैं जो चालों की संख्या बढ़ने पर भी बढ़ेगा।

अंत में, हम चेक मेट को सत्यापित करने के लिए लूप के लिए एक डबल (आंतरिक) का उपयोग करते हैं , जो निश्चित रूप से राजा की चालों की संख्या और अन्य टुकड़ों की चालों के आधार पर O(n²) का एक टीसी होने वाला है।

इतना ही; मेरा समाधान है। मैं अच्छी तरह से जानता हूं कि कुछ बिंदु यथासंभव कुशल नहीं हैं, लेकिन लिखते समय मुझे सही समाधान बनाने से ज्यादा प्रक्रिया का वर्णन करने का विचार पसंद आया।

आपका इसके बारे में क्या सोचना है? मुझे इसके बारे में अपनी राय दें और आइए टिप्पणियों में आपके समाधान पर चर्चा करें!

हमेशा की तरह, अगर आपको लेख पसंद आया है, तो कृपया एक या दो ताली छोड़ें और सदस्यता लें, या इसे किसी ऐसे व्यक्ति के साथ साझा करें, जो इस तरह के एल्गोरिदम में दिलचस्पी ले सकता है, यदि आप कर सकते हैं! अंत तक पढ़ने के लिए धन्यवाद, इस बार इस समाधान की लंबाई हमेशा से अधिक दी गई है!

हमेशा की तरह, पढ़ने के लिए धन्यवाद।