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

चेकमेट की जाँच करें हल करने के लिए एक और समस्या के साथ आपका स्वागत है! यदि आप शतरंज और खेलना पसंद करते हैं: तो यह आपके लिए है! आज हम राजा को युद्ध के मैदान में एक और दिन जीवित रहने में मदद करेंगे, साथ ही कोड का एक बड़ा समूह भी लिखेंगे। कोडिंग तो आगे की हलचल के बिना, आइए देखते हैं हमारी समस्या। हालांकि शुरू करने से पहले, हमेशा की तरह, दो अस्वीकरण: ये समस्याएं अद्भुत न्यूज़लेटर डेली कोडिंग प्रॉब्लम द्वारा प्रदान की जाती हैं, जिसे आप सब्सक्राइब कर सकते हैं : इसे देखें और अपनी दैनिक चुनौती को भी हल करने का प्रयास करें! यहाँ मैं एक विशेषज्ञ प्रोग्रामर नहीं हूं, बस एक लड़का हूं जो अपने प्रयासों (और असफलताओं) को साझा करना पसंद करता है। यदि आपके पास कोई बेहतर विचार या समाधान है, तो आप इसे साझा करने के लिए स्वागत से अधिक हैं: मुझे यह देखना अच्छा लगेगा कि आप इससे निपटते हैं! समस्या आज की समस्या शुरू में Oracle द्वारा पूछी गई थी। मैट्रिक्स के साथ प्रस्तुत किया जाता है। आपको शतरंज बोर्ड पर टुकड़ों की स्थिति का प्रतिनिधित्व करने वाले 8 से 8 बोर्ड पर केवल काले राजा और विभिन्न सफेद टुकड़े हैं। इस मैट्रिक्स को देखते हुए, निर्धारित करें कि राजा चेक में है या नहीं। प्रत्येक टुकड़ा कैसे चलता है, इसके विवरण के लिए देखें यहाँ . उदाहरण के लिए, निम्नलिखित मैट्रिक्स दिया गया है: ...K.... ........ .B...... ......P. .......R ..N..... ........ .....Q.. वापस करना चाहिए आपको True , क्योंकि बिशप तिरछे राजा पर हमला कर रहा है। समस्या बिल्कुल स्पष्ट है, इसलिए हम इसके बारे में अधिक विस्तार से नहीं बताएंगे। हालांकि हमें कुछ शुरुआती विशिष्टताओं की आवश्यकता है: हम एक ग्राफ पर हैं, बोर्ड पर नहीं: नतीजा वही है; हम बोर्ड पर केस के केंद्र के रूप में समस्या द्वारा दिए गए प्रत्येक बिंदु पर विचार करेंगे। सफेद राजा अन्य 7 प्यादों के साथ छुट्टी पर चला गया है: राजा और प्यादे सभी टुकड़ों में सबसे अधिक उबाऊ हैं और उन्हें हटाने से हमारा समाधान उतना नहीं बदलने वाला है; हमें , जिसका अर्थ है कि यदि वह आगे नहीं बढ़ता है तो अगले सफेद मोड़ पर इसे लिया जाएगा; यह सत्यापित करने की आवश्यकता है कि क्या राजा इसी मोड़ पर नियंत्रण में है : मैं अतिव्यापी टुकड़ों या गलत शुरुआती स्थितियों के सत्यापन में नहीं जाऊंगा। शुरुआत में खेल द्वारा स्थितियां दी जाती हैं समाधान सबसे पहले, टुकड़ों और चाल-सेटों का एक त्वरित पुनर्कथन: प्रत्येक टुकड़े की शुरुआती स्थिति और उसकी चाल-सेट को देखते हुए, हम "आसानी से" सकते हैं। हर टुकड़े की हर संभव अगली चाल की गणना कर और चूंकि वे सभी राजा को जल्द से जल्द पकड़ने में रुचि रखते हैं, इसलिए हम यह मान सकते हैं कि । इसलिए, चूंकि हम काले राजा की स्थिति को भी जानते हैं, हमें यदि ऐसा है, तो अगले सफेद मोड़ के दौरान सफेद टुकड़ा काले राजा को पकड़ने के लिए वहां जाएगा। उनका अगला कदम काले राजा को पकड़ने वाला होगा केवल यह जांचने की आवश्यकता है कि क्या काले राजा की स्थिति अन्य मोहरों की संभावित अगली चालों में से एक है। स्थिति कुछ इस तरह दिखती है: ऊपर की तस्वीर में आप देख सकते हैं (… मुझे उम्मीद है, भ्रम के लिए खेद है …) सफेद तरफ , अलग-अलग रंगों से रंगी हुई, और ऊपर का काला राजा पकड़े जाने की प्रतीक्षा कर रहा है। तो उदाहरण के लिए बिशप, (2,7) से शुरू होकर, (1,6), (1,8), (3,8), (3,6), (4,5), (5,) तक जा सकता है। 4) और इसी तरह। प्रत्येक टुकड़े की हर संभव चाल मैंने बस बेतरतीब ढंग से इन टुकड़ों की शुरुआती स्थिति तय की क्योंकि यह अंतिम परिणाम को प्रभावित नहीं करता है। चूँकि हम 8x8 ग्राफ़ पर हैं (स्पष्ट होने के लिए, कोई भी अन्य आयाम उसी तरह काम करेगा) और हमारे पास प्रत्येक टुकड़े के शुरुआती निर्देशांक हैं, हम निर्देशांक की श्रृंखला बना सकते हैं जो हमारे टुकड़े अगली चाल होंगे। ऐसा करने के लिए, हम पहले उसके निर्देशांक को परिभाषित करते हैं और फिर x, y प्रत्येक टुकड़े के लिए एक वर्ग को परिभाषित करते हैं, वहाँ से हर संभव चाल की गणना करने के लिए नियमों को परिभाषित करते हैं। टुकड़े - प्यादा आइए प्यादा के साथ सरल शुरुआत करें। वैसे, मैं इसे में बना रहा हूं, क्योंकि यह इस समय सबसे लोकप्रिय भाषाओं में से एक है और यकीनन किसी के द्वारा सबसे अधिक पठनीय है। फिर भी, । इस अवधारणा की एक सुंदर साफ व्याख्या। पायथन आपको यह जानने की आवश्यकता होगी कि अब से किस वर्ग का पालन किया जा सकता है यहाँ है https://gist.github.com/NicolaM94/ae4e0e850250a6974042b0ac72be7585?embedable=true#file-pawn-py आइए संक्षेप में समझाते हैं: हम पहले वर्ग और इसके निर्देशांक को परिभाषित करते हैं। उसके बाद, हम वहां से प्यादा संभावित चालों की गणना करने के लिए विधि को परिभाषित करते हैं। प्यादा चालें अपेक्षाकृत आसान होती हैं, इसलिए हम उन्हें केवल चर में जोड़ते हैं, यह जाँचने के बाद कि यह हमारे ग्रिड से बाहर नहीं जाती है, और सरणी वापस कर देता है। यहाँ ध्यान देने योग्य दो बातें, विशेष रूप से प्यादा के लिए: class Pawn __init__ x,y possibleMoves moves moves हम सफेद मोहरे को नीचे से ऊपर की ओर बढ़ने पर विचार करते हैं, जैसे कि हम सफेद खिलाड़ी हैं जो अपने मोहरे को अपने प्रतिद्वंद्वी की ओर आगे बढ़ा रहे हैं। यह वास्तव में कुछ भी नहीं बदलता है, यह सिर्फ चीजों को क्रम में रखता है। हम , क्योंकि हम काले राजा को पकड़ने में रुचि रखते हैं: चूंकि प्यादा केवल तिरछे तरीके से कब्जा कर सकता है और हम टुकड़ों को अन्य दिशाओं में ले जाने की परवाह नहीं करते हैं, हम इसकी सामान्य गति को छोड़ सकते हैं। जानबूझकर सामान्य गति को छोड़ देते हैं अब हम बस मोहरे की चालों को उसके निर्देशांक देकर और विधि को कॉल करके देख सकते हैं, जैसे: और हमें जैसा कुछ प्राप्त करना चाहिए . possibleMoves print(Pawn(7,2).possibleMoves()) [(6,3),(8,3)] [(6,3),(8,3)] इसके अलावा, आप शीर्ष पर देख सकते हैं कि , इसलिए हम संभवतः उन्हें अन्य आयामों के बोर्डों पर एल्गोरिथम चलाने के लिए बदल सकते हैं। हमने अपने ग्रिड आयामों को चर के रूप में परिभाषित किया है अब चलो टावर पर चलते हैं। मीनार https://gist.github.com/NicolaM94/7897939bdd7933cb09d8915b7b8bc0b5?embedable=true#file-tower-py दोबारा, हम टावर क्लास को इसके निर्देशांक के साथ शुरू करते हैं और फ़ंक्शन को परिभाषित करते हैं। यहां सभी संभावित चालों को इकट्ठा करने के लिए में जोड़ते हैं, जो सभी लूपों के बाद वापस आ जाएगा। पहले की तरह, टावर चालों की जांच करने के लिए हम केवल सकते हैं और हमें कुछ इस तरह मिलना चाहिए: . possibleMoves हम टॉवर दो अक्षों पर सभी बिंदुओं को श्रेणीबद्ध करते हैं और प्रत्येक एकल निर्देशांक को चर moves print(Tower(5,3).possibleMoves()) [(1,3), (2,3), (3,3), ..., (5,8)] बिशप अब बारी बिशप की है। https://gist.github.com/NicolaM94/a6ae6f6138b78d550b2f2e27d5c453aa?embedable=true#file-bishop-py टॉवर की तुलना में बिशप की चालें अधिक जटिल हैं, इसलिए हम यहां क्या हो रहा है, इसकी थोड़ी व्याख्या कर सकते हैं। मूल रूप से । क्लास और इनिट मेथड घोषित करने के बाद, हम दो वेरिएबल बनाते हैं: , पहले की तरह, और , जिसका उपयोग हम अपने अक्षों के साथ चलते हुए एकत्रित किए गए बिंदुओं पर नज़र रखने के लिए करेंगे। अब लूप का उपयोग करते हुए, और यह जाँचते हुए कि हम अपने ग्रिड के बाहर नहीं जा रहे हैं, हम और उसी के अनुसार । उदाहरण के लिए, यदि हम इसकी शुरुआती स्थिति से ऊपर-बाएँ जाना चाहते हैं, तो हमें मान को बढ़ाते हुए मान को कम करना होगा। यदि हम दाईं ओर नीचे जाना चाहते हैं, तो हमें मान को घटाते हुए मान को बढ़ाना होगा और इसी तरह आगे भी। अंत में, हम बस एक बार फिर लौटाते हैं। हमें इसकी शुरुआती स्थिति से शुरू होने वाले दो विकर्ण अक्षों पर अंक एकत्र करने की आवश्यकता है moves currentPos while x y बढ़ाते और घटाते हैं जहाँ हम जाना चाहते हैं y x y x moves रानी अब आप सोच सकते हैं: यदि टॉवर चालें जटिल हैं और बिशप और भी अधिक हैं, तो हम रानी को कैसे कोडित करने जा रहे हैं? दरअसल, एक साधारण ट्रिक की मदद से क्वीन मूव्स को कोड करना सबसे आसान है। फिर देखते हैं रानी। https://gist.github.com/NicolaM94/22bd55aab7a0976f4656403c3749a6ee?embedable=true#file-queen-py ठीक है, यहाँ क्या हो रहा है? ठीक है, अगर हम इसके बारे में सोचते हैं, । वह एक रानी की तुलना में टॉवर के आकार के बिशप मेचा-बॉट की तरह अधिक है। इस कारण से, उसकी चालों को कोडिंग करना वास्तव में सरल है। उसकी कक्षा घोषित करने के बाद हम बस उसकी के रूप में परिभाषित करते हैं। तो रानी के पास बिशप और टावर संयुक्त की समान चालें हैं possibleMoves बिशप और टावर की संभावित चालों के परिणामस्वरूप चालों के संघ सरणी ध्यान दें कि फ़ंक्शन में और उदाहरणों को कॉल करते समय उनके पैरामीटर और के रूप में दिया जाता है, इसलिए वे वास्तव में रानी निर्देशांक हैं। possibleMoves Bishop Tower x y self.x, self.y शूरवीर अब शूरवीर को! https://gist.github.com/NicolaM94/c19d2c41e4461c66fca54aab239ede9e?embedable=true#file-knight-py नाइट मेरे लिए सबसे खास है। उसका मूव-सेट अजीब है, जैसे "L" आकार का, इसलिए मुझे इसे कोड करने के लिए विशेष रूप से चतुर या तेज़ तरीका नहीं मिला और मैंने इसकी चालों को हार्ड कोडिंग करना समाप्त कर दिया, बस गणना की। उसकी शुरुआती स्थिति से उसके द्वारा की जाने वाली 8 संभावित चालों की राजा राजा के बारे में कुछ संक्षिप्त अवधारणाएँ। चूँकि हमें राजा को स्थानांतरित करने की आवश्यकता नहीं है, केवल यह बता देना कि उसने जाँच की है या नहीं, । हालाँकि, हम लेख के अंत में एक संक्षिप्त कार्यान्वयन भी देखेंगे। इसके अलावा, इसे कोडिंग करना उतना आसान नहीं है जितना कि रानी की चाल-सेट को कम करना, जैसा कि हम बाद में देखेंगे। तो अभी के लिए, उसकी हरकतों को छोड़ दें और समाधान देखें। हमें वास्तव में उसके चाल-सेट को लागू करने की आवश्यकता नहीं है समाधान कोड यह देखते हुए कि हमारे पास प्रत्येक टुकड़े के लिए संभावित स्थान हैं, समाधान अब बहुत आसान है: हमें केवल यह जांचने की आवश्यकता है कि ब्लैक किंग निर्देशांक एक या अधिक अन्य टुकड़ों की चाल के सेट में हैं या नहीं। आइए इसे कोड करें! https://gist.github.com/NicolaM94/75826a753105c3a3aecae4f6890b631a?embedable=true#file-check-py अब हम केवल कुछ निर्देशांक के रूप में एक वेरिएबल बनाते हैं। फिर प्रत्येक टुकड़े के लिए हम इसकी कक्षा का एक उदाहरण बनाते हैं जिसे हमने अभी बनाया है और चाल के पूर्ण सेट की गणना करने के लिए विधि को कॉल करता है। : यदि वे हैं, तो हम यह प्रिंट करते हैं कि राजा को उस विशेष टुकड़े द्वारा चेक किया गया है। यहाँ परिणाम कुछ इस प्रकार है: 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! मैंने उपरोक्त गन्दी छवि को संदर्भ के रूप में इस्तेमाल किया, ताकि आप जांच सकें कि राजा वास्तव में टावर और नाइट द्वारा चेक किया गया है। चेक मेट क्या होगा अगर हम यह भी गणना करना चाहते हैं या यह वास्तव में चेक मेट है? इस उद्देश्य के लिए, हमें राजा की चालों के सेट की गणना करने की आवश्यकता है। कि क्या राजा के पास अभी भी जीवित रहने की कुछ संभावना है https://gist.github.com/NicolaM94/cca18293bedb2293bbc621e86236571f?embedable=true#file-king-py आइए इसका थोड़ा वर्णन करें। सबसे पहले, हम अपनी कक्षा को परिभाषित करते हैं और पहले की तरह समन्वय करते हैं। उसके बाद हम विधि बनाते हैं और राजा की संभावित चालों को कोड करते हैं (फिर से, मुझे पूरा यकीन है कि एक तेज़ तरीका है, लेकिन केवल 8 संभावित चालें हैं इसलिए ...)। उसके बाद, और केवल लौटाएँ। possibleMoves हम जाँचते हैं कि कौन सी चालें अवैध हैं (बोर्ड के बाहर जाएँ) validMoves तो अब, यह जाँचने के लिए कि क्या राजा के पास अभी भी जीवित रहने का एक मौका है, ऐसा करने के लिए हम केवल बादशाह की चालों और दूसरी चालों पर लूप करते हैं। हमें यह जाँचने की आवश्यकता है कि क्या उसकी कोई भी संभावित चाल चालों के दूसरे टुकड़े में नहीं है। https://gist.github.com/NicolaM94/9bdb64c10e2d039905e6353ed37cc101?embedable=true#file-checkmate-py इसलिए अभी भी हमारे राजा के बचने की उम्मीद है! उसके लिए भाग्यशाली मुझे लगता है … समय जटिलता हमेशा की तरह, इस समाधान की समय जटिलता पर एक संक्षिप्त नज़र डालें। सबसे पहले, चूंकि प्रत्येक टुकड़ा है, हमें उस उदाहरण को आरंभ करने के समय पर विचार करना चाहिए। एक वर्ग का एक उदाहरण जैसे मोहरे के अंदर कोई लूप नहीं होता है और यह किसी चर आयाम पर निर्भर नहीं करता है, इसलिए हम उन्हें 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²) का एक टीसी होने वाला है। हम चेक मेट को सत्यापित करने के लिए लूप के लिए एक डबल (आंतरिक) का उपयोग करते हैं इतना ही; मेरा समाधान है। मैं अच्छी तरह से जानता हूं कि कुछ बिंदु यथासंभव कुशल नहीं हैं, लेकिन लिखते समय मुझे सही समाधान बनाने से ज्यादा प्रक्रिया का वर्णन करने का विचार पसंद आया। आपका इसके बारे में क्या सोचना है? मुझे इसके बारे में अपनी राय दें और आइए टिप्पणियों में आपके समाधान पर चर्चा करें! हमेशा की तरह, अगर आपको लेख पसंद आया है, तो कृपया एक या दो ताली छोड़ें और सदस्यता लें, या इसे किसी ऐसे व्यक्ति के साथ साझा करें, जो इस तरह के एल्गोरिदम में दिलचस्पी ले सकता है, यदि आप कर सकते हैं! अंत तक पढ़ने के लिए धन्यवाद, इस बार इस समाधान की लंबाई हमेशा से अधिक दी गई है! हमेशा की तरह, पढ़ने के लिए धन्यवाद।