मेरी माइन्सवीपर को हल करने में एल्गोरिदम

Question

मैंने गेम 'माइन्सवीपर' को हल करने के लिए पायथन में एक एल्गोरिदम लागू किया है। कार्यक्रम निम्नानुसार काम करता है:

कहें कि सॉल्वर 'ए' नामक एक वर्ग पर क्लिक करता है। उदाहरण के लिए इस प्रकार संख्या को बराबर 2 दिखाया गया है। वर्ग के पड़ोसियों जो अभी तक अनजान हैं (फिर से उदाहरण के माध्यम से) 'बी' और 'सी' नामक हैं। कार्यक्रम तब स्क्वायर को अभिव्यक्ति [2, {'बी', 'सी'}] से जोड़ता है, और अन्य सभी अभिव्यक्तियों से 'ए' स्ट्रिप्स करता है। किस वर्ग की कटौती खान हैं और जो दो परिस्थितियों में ऐसे अभिव्यक्तियों के जोड़ी सरलीकरण द्वारा प्राप्त नहीं होती हैं।

• एक अभिव्यक्ति में वर्गों अन्य अभिव्यक्ति के वर्गों के एक सबसेट हैं:

  [2, {'a', 'b'}], [1, {'b', 'c'}] -> [2, {'a', 'b'}], [0, {'c'}] 
  

:

[2, {'a', 'b', 'c'}], [1, {'a', 'b'}] -> [1, {'c'}], [1, {'a', 'b'}] 

• एक अभिव्यक्ति के सारे वर्गों खानों रूप में सिद्ध किया रहे हैं

फिर, कुछ अभिव्यक्ति X के लिए, X[0] == 0, हम cl के लिए स्वतंत्र हैं X[1] में नामित सभी वर्गों को चिह्नित करें, और यदि X[0] == len(X[1]), तो हम उन्हें ध्वजांकित कर सकते हैं।

हालांकि, मैं की पहचान करने के लिए संघर्ष कर रहा हूं, जो सरलता के प्रयासों के लिए अभिव्यक्तियों के जोड़े हैं। मेरा वर्तमान दृष्टिकोण वर्गों के ढेर को बनाए रखना है; जब भी एक वर्ग क्लिक किया जाता है, या इसकी अभिव्यक्ति सफलतापूर्वक सरलीकृत होती है, तो इसे स्टैक में जोड़ा जाता है (यदि यह पहले से मौजूद नहीं है)। जब एक वर्ग ढेर से पॉप किया जाता है, तो इसकी अभिव्यक्ति (X) के बीच सरलीकरण का प्रयास किया जाता है, और Y जैसे X[1] & Y[1] != set() के बीच सरलीकरण का प्रयास किया जाता है। जब स्टैक समाप्त हो जाता है तो एल्गोरिदम समाप्त हो जाता है। हालांकि, हालांकि, यह काफी अच्छी तरह से काम करता है, यह सभी स्पष्ट कॉन्फ़िगरेशन को सही ढंग से हल करने में सक्षम नहीं है, और यदि मैं कतार के साथ स्टैक को प्रतिस्थापित करता हूं, या कुछ एल्गोरिदम का उपयोग करता हूं, यह निर्धारित करने के लिए कि कौन सा वर्ग पॉप करना है, !

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

Answer 1

यह दिमाग में कूद गया है, मैं पूरी तरह से कल्पना करने में सक्षम नहीं था कि आपकी विधि बिल्कुल क्या थी।
मुझे उम्मीद है कि ग्राफिकल रूप में मेरा प्रस्तुत करने से आपको उस प्रयास को बचाने में मदद मिलेगी।

छवियां "पढ़ने के क्रम" में आगे बढ़ती हैं।

यह काम मैं इस कि एक अज्ञात टाइल करने के लिए दिया जाना जाता टाइल्स है कि यह यह हो रहा है की संख्या मूल्य को जोड़ने पोस्टिंग के बाद से किया है के साथ फिट करने के लिए लगता है आगे संभावना में वृद्धि कर सकता है से अस्थायी मूल्य है सही ढंग से मॉडलिंग जोखिम का।

---

मैं इस जल्दी नहीं देखने के लिए एक छोटे से अंधा महसूस (इस का उपयोग करते हुए, 16 (या 8 पहली विधि के साथ) की एक अस्थायी मूल्य महत्वपूर्ण के रूप में यह नंबर एक खदान से ही प्राप्त कर सकते हैं है) ।

किसी भी मूल्य के साथ जो 100% तक सामान्य है, सभी मामलों में मैं एक खदान पा सकता हूं।

Answer 2

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

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

a 2 1 2 1 2 i 
b c d e f g h 

आपका स्थिति हो जाएगा:: उदाहरण के लिए, इस छोटे से 7x2 बोर्ड, जहां ah के माध्यम से टाइल्स अज्ञात हैं पर विचार

[2, {a, b, c, d}], 
[1, {c, d, e}], 
[2, {d, e, f}], 
[1, {e, f, g}], 
[2, {f, g, h, i}] 

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

a 2 1 2 1 2 i 
b 2 * 2 * 2 h 

अभी भी कुछ अज्ञात है, एक खदान के साथ a या b और h या i के तहत, लेकिन यदि यह एक बड़ी पहेली का हिस्सा था तो आप बाद में उन लोगों को समझने में सक्षम हो सकते हैं (या आपको अनुमान लगाना पड़ सकता है)।

मेरा मानना ​​है कि खानों दृष्टिकोण के अपने सेट इस तरह काम किया:,

प्रत्येक टाइल कि विस्तार किया गया है के लिए अपने सभी अविस्तारित पड़ोसियों में से एक सेट ("क्षेत्र"), और के सभी सेट युक्त सूची एकत्रित खान जो उस क्षेत्र में हो सकती है। वैसे भी

({a, b, c, d}, [{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}]) 
({c, d, e}, [{c}, {d}, {e}]) 
({d, e, f}, [{d, e}, {d, f}, {e, f}]) 
({e, f, g}, [{e}, {f}, {g}]) 
({f, g, h, i}, [{f, g}, {f, h}, {f, i}, {g, h}, {g, i}, {h, i}]) 

, क्षेत्र सेट अन्तर्विभाजक द्वारा, दो की स्थिति मैं पहली बार जाँच चाहते हैं कि वे अतिव्यापी थे गठबंधन करने के लिए: तो उदाहरण के लिए, उदाहरण में 5 में जाना जाता टाइल्स ऊपर उत्पन्न होगा (बाएँ से दाएँ से)। यदि कोई ओवरलैप नहीं था, तो शर्तों को उपयोगी रूप से संयुक्त नहीं किया जा सकता है।

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

Intersection of areas: {a, b, c, d} & {c, d, e} = {c, d} 
New combined area: {a, b, c, d} | {c, d, e} = {a, b, c, d, e} 
Cartesian product of mine sets (with X marking contradictions): 
    | {a, b} {a, c} {a, d} {b, c} {b, d} {c, d} 
---+------------------------------------------------- 
{c}|  X  {a, c} X  {b, c} X  X 
{d}|  X  X  {a, d} X  {b, d} X 
{e}| {a, b, e} X  X  X  X  X 

New condition: ({a, b, c, d, e}, [{a, b, e}, {a, c}, {b, c}, {a, d}, {b, d}]) 

आप किसी भी टाइल की बाधाओं हालत के क्षेत्र के भीतर एक खदान जा रहा है बस सेट इसका हिस्सा, रिश्तेदार है की कितने गिनती कितने सेट करने के लिए से गणना कर सकते हैं कुल हैं तो ऊपर संयुक्त शर्त दी गई है, आप समझ सकते हैं कि a उस समय का एक 3/5 वां है, जबकि e उस समय का केवल 1/5 वां है। यह जानकारी तब महत्वपूर्ण है जब किसी भी गारंटीकृत-सुरक्षित टाइल्स नहीं होने पर प्रोग्राम को विस्तार करने के लिए किसी स्थान का अनुमान लगाने की आवश्यकता हो। मुझे लगता है कि मैंने उपयोग की जाने वाली खानों की संख्या के लिए कुछ जटिल संयोजन भी किए हैं (ताकि ऊपर दिए गए {ए, बी, ई} मामले को अन्य मामलों की तुलना में थोड़ा अलग किया जा सके, क्योंकि यह दो की बजाय तीन खानों का उपयोग करता है) लेकिन मुझे डर है कि मुझे विवरण याद नहीं है।

माइन्सवीपर एक बहुत चुनौतीपूर्ण गेम है।मेरा मानना ​​है कि मेरा कार्यक्रम समय के 50-60% के बारे में "हार्ड" कठिनाई के बराबर बोर्डों को हल करने में सक्षम था, जिसमें अधिकांश नुकसान या तो शुरुआत के करीब हो रहा था (जब आपको काम करने के लिए छोटी जानकारी के साथ अनुमान लगाना चाहिए) या दाएं अंत (जब अक्सर कुछ असुरक्षित क्षेत्र होते हैं जिन्हें अनुमान लगाने की आवश्यकता होती है)। यह आमतौर पर बहुत तेज था, हालांकि कभी-कभी टाइल्स का एक पैटर्न होगा जो इसे अगले कदम बनाने से पहले 10 या 15 सेकंड तक गिरने का कारण बनता है। (Minesweeper is NP-complete, इसलिए यह आश्चर्य की बात नहीं है कि कुछ इनपुट जल्दी हल नहीं किए जा सकते हैं!)