फिर से "समुद्र युद्ध"। हम संभावित जहाज स्थानों की संख्या गिनते हैं

जब से हैबे पर "सी लड़ाई" का सप्ताह जारी है, मैं अपने दो सेंट जोड़ूंगा।
कंप्यूटर के लिए खेलने के लिए इष्टतम रणनीति खोजने की कोशिश करते समय, हम जल्दी से इस अनुमान पर आते हैं:

मान लीजिए कि हम पहले से ही कुछ कोशिकाओं की स्थिति जानते हैं, और हम एक ऐसा कदम उठाना चाहते हैं जो हमें जीत के करीब लाए। इस मामले में, यह एक सेल चुनने के लिए समझ में आता है जो दुश्मन के जहाज के कब्जे में सबसे अधिक संभव स्थानों पर उपलब्ध है जो उपलब्ध जानकारी का खंडन नहीं करते हैं

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


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

पहली नज़र में, कार्य असहनीय लगता है। विन्यास की संख्या 10 ²⁰ के क्रम की प्रतीत होती है (वास्तव में, उनमें से कुछ कम हैं - 10 ^{15 के} करीब), इसलिए बहुत अधिक समय संपूर्ण खोज पर खर्च किया जाएगा। क्षेत्र के रंग को छांटना और केवल स्वीकार्य लोगों को छोड़ना बेहतर नहीं है: वैसे भी, हमें प्रत्येक संयोजन को देखना होगा।

और क्या प्रयास करना है? कोई भी ओलंपियाड तुरंत जवाब देगा - गतिशील प्रोग्रामिंग। लेकिन इसे व्यवस्थित कैसे करें?

हम ऊपर से नीचे तक जाते हैं। हमें क्या जानकारी चाहिए?

तो, हम ऊपर से नीचे तक जाएंगे। मान लीजिए कि हमारे क्षेत्र को दो भागों में विभाजित किया गया है - भाग A में पहली k लाइनें शामिल हैं, और भाग B में सभी शेष हैं। मैदान के भाग को भरना इसकी कोशिकाओं का दो रंगों में रंगना है। पूरे क्षेत्र को भरना सही कहा जाता है यदि काली कोशिकाएं जहाजों का एक सेट बनाती हैं जो नियमों को संतुष्ट करती हैं (जहाज सीधे होते हैं, स्पर्श नहीं करते हैं, उनकी लंबाई वांछित सेट बनाते हैं)। भाग A के दो भरण S1 और S2 को समतुल्य कहा जाएगा, यदि भाग B के किसी भी भरण T के लिए, संपूर्ण क्षेत्र S1 | T और S2 | T की संयुक्त भरण एक ही समय में सही या गलत है।

समस्या को हल करने के लिए, यह हमारे लिए पर्याप्त है:

• भाग ए के लिए सभी पैडिंग समकक्ष वर्गों का वर्णन करें
• प्रत्येक वर्ग के लिए, अलग-अलग भरावों की संख्या की गणना करें, और क्षेत्र A के प्रत्येक सेल के लिए, यह इंगित करें कि यह कितना भराव काला था (हम इस जानकारी को इस वर्ग का मानचित्र कहते हैं)
• क्षेत्र ए में एक नई लाइन जोड़ते समय वर्गों और उनके नक्शे के रूपांतरण का वर्णन करें।

मान लीजिए कि हमारे पास क्षेत्र A का एक अज्ञात भरने वाला S और क्षेत्र B का ज्ञात फिलिंग T है। S के बारे में हमें क्या जानने की आवश्यकता है?

सबसे पहले, अंतिम पंक्ति का पूर्ण राज्य होना अच्छा है। केवल इस मामले में हम यह निर्धारित करने में सक्षम होंगे कि क्षेत्र B की पहली पंक्ति के कौन से सेल हम अभी भी कब्जा कर सकते हैं और कौन से नहीं।

दूसरे, आपको यह जानना होगा कि क्षेत्र ए में कितने और कौन से पूर्ण जहाज पहले से मौजूद हैं। समाप्त होने का मतलब है कि एक ऐसा जहाज है जिसे अब क्षेत्र बी तक नहीं बढ़ाया जा सकता है। हमारे मामले में, यह या तो ऐसे जहाज हैं जिनमें अंतिम पंक्ति में कोशिकाएँ नहीं होती हैं, या ऐसे जहाज होते हैं जो इसमें पूरी तरह से झूठ बोलते हैं (और दो या अधिक कक्षों पर कब्जा कर लेते हैं)

तीसरा, प्रत्येक जहाज के बारे में जो अभी भी क्षेत्र बी तक बढ़ाया जा सकता है, हमें इसकी वर्तमान लंबाई जानने की आवश्यकता है। इन जहाजों को खुद को अंतिम पंक्ति द्वारा पहचानना आसान है: वे इसमें एक काले सेल पर कब्जा कर लेते हैं, जो सफेद क्षेत्रों से घिरा हुआ है।

और वह यह है। समतुल्यता वर्ग पूरी तरह से इस डेटा द्वारा निर्धारित किया जाता है, और उनके सभी संयोजन भी मान्य नहीं हैं। आइए गणना करें कि यह कितना निकला:

• अंतिम पंक्ति: 10 बिट, और सभी विकल्प संभव नहीं हैं: एक पंक्ति में 4 से अधिक इकाइयां नहीं जा सकती हैं, और 4 इकाइयों (0111101111) के दो समूह नहीं हो सकते हैं। कुल 909 विकल्प।
• पहले से ही उजागर जहाज। 0 से 4 एक-डेक से, 0 से 3 दो-डेक से, 0 से 2 तीन-डेक, 0 या 1 चार-डेक से। केवल 120 विकल्प।
• पंक्ति के प्रत्येक अलग-थलग बिट के लिए - संबंधित ऊर्ध्वाधर जहाज में कोशिकाओं की संख्या जो ए में गिर गई: 1 से 4 तक। ऐसे 5 से अधिक जहाज नहीं हैं, कुल में 1024 से अधिक विकल्प नहीं हैं।

प्रत्येक वर्ग को इस प्रकार 27 बिट्स द्वारा वर्णित किया गया है, और उनकी कुल संख्या 120 मिलियन से अधिक नहीं है। वास्तव में, यह अनुमान बहुत अधिक था, और कार्यक्रम 1053,612 कक्षाएं खोजने में सक्षम था।

एक नई पंक्ति जोड़ें

मान लीजिए कि हमारे पास एस भरने है, जिसके बारे में हम केवल ऊपर वर्णित जानकारी जानते हैं। हम इसे एक और पंक्ति द्वारा विस्तारित करना चाहते हैं: प्राप्त होने वाले सभी भत्तों को सूचीबद्ध करें, उनके लिए कक्षाएं परिभाषित करें, और प्रत्येक नए वर्ग के लिए एक घनत्व मानचित्र बनाएं।

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


सभी लाइनों को जोड़ा जा सकता है। यदि एक पंक्ति में एक पंक्ति में एक से अधिक इकाई होती है, तो वे एक क्षैतिज जहाज बनाते हैं - हम तुरंत तैयार जहाजों के काउंटरों में इसे ध्यान में रखते हैं। पृथक इकाइयों के साथ तीन स्थितियां हैं:

• अंतिम पंक्ति S में एक पृथक इकाई थी, लेकिन इस स्थान पर एक नई पंक्ति में यह नहीं है। तो जहाज समाप्त हो गया है, और इसकी लंबाई काउंटर में जोड़ दी गई है।
• नई लाइन में एक अलग इकाई है, लेकिन S की अंतिम पंक्ति में इस स्थान पर कोई भी नहीं है। तो, एक नया ऊर्ध्वाधर जहाज दिखाई दिया है, और इसकी लंबाई अब 1 के बराबर है।
• एक पृथक इकाई S की अंतिम पंक्ति में है, और एक नई पंक्ति में है। इसका मतलब है कि ऊर्ध्वाधर जहाज जारी है, और इसकी लंबाई 1 से बढ़ जाती है।

अब जांचें कि क्या लंबाई का एक सेट वैध है। बता दें कि s1, s2, s3, s4 लंबाई के पूर्ण किए गए जहाजों की संख्या क्रमशः 1,2,3,4 है, और n1, n2, n3, n4 इसी लंबाई वाले अधूरे जहाजों की संख्या है। यह सुनिश्चित करने के लिए कि किट शर्तों का खंडन न करे, निम्नलिखित आवश्यक है:

s1<=4 && s2<=3 && s3<=2 && s4+n4<=1 && (s3+s4+n3+n4)<=3 && (s2+s3+s4+n2+n3+n4)<=6 && (s1+s2+s3+s4+n1+n2+n3+n4)<=10 

नए वर्ग के लिए जानकारी तैयार है। इसके लिए एक मानचित्र बनाने के लिए, बस पुराने नक्शे की पहली पंक्तियों को कॉपी करें, और अगली पंक्ति में संयोजनों की संख्या से गुणा की गई बिट लाइन को दर्ज करें। एक ही वर्ग के कार्ड, अलग-अलग कॉन्फ़िगरेशन से प्राप्त किए जाते हैं, जोड़ते हैं।

कालफ़न

प्रारंभिक खाली कॉन्फ़िगरेशन में 10 पंक्तियों को जोड़ने के बाद, हमें 1053612 वर्गों की सूची मिली है, जिनमें से प्रत्येक का अपना नक्शा है। क्षेत्र के सभी विन्यासों का एक नक्शा प्राप्त करने के लिए, हमें इन सभी वर्गों से गुजरने की जरूरत है, अधूरे जहाजों को "खत्म" करें, प्रत्येक आकार के परिणामी जहाजों की संख्या की गणना करें, और यदि यह सही है, तो कक्षा के नक्शे को कुल में जोड़ें।

खाली 10x10 फ़ील्ड के लिए, 1855545978831780 कॉन्फ़िगरेशन चालू हो गए, और भरण मानचित्र इस तरह दिखता है (सभी संख्याएं 10 ^{9 से} विभाजित होती हैं):

 438487 418064 475795 466986 459000 459000 466986 475795 418064 438487
 418064 273993 311381 287231 287065 287065 287231 311381 273993 418064
 475795 311381 378334 357367 361127 361127 357367 378334 311381 475795
 466986 287231 357367 330652 334756 334756 330652 357367 287231 466986
 459000 287065 361127 334756 338709 338709 334756 361127 287065 459000
 459000 287065 361127 334756 338709 338709 334756 361127 287065 459000
 466986 287231 357367 330652 334756 334756 330652 357367 287231 466986
 475795 311381 378334 357367 361127 361127 357367 378334 311381 475795
 418064 273993 311381 287231 287065 287065 287231 311381 273993 418064
 438487 418064 475795 466986 459000 459000 466986 475795 418064 438487

तथ्य यह है कि यह सममित रूप से अप्रत्यक्ष रूप से पुष्टि करता है कि कार्यक्रम में कोई सकल त्रुटियां नहीं हैं :) सबसे अधिक आबादी वाला सेल सी 1 है, सबसे अधूरा सेल बी 2 है।
C1 में जाने के बाद, कार्ड निम्नलिखित फॉर्म लेगा:

 334039 316782 362205 354834 348680 348723 354859 362278 316825 334105
 316847 204441 234170 214857 214919 214952 214721 234125 204338 316830
 362174 234066 286949 270246 273421 273609 270199 287338 234109 362286
 354993 215372 270082 249099 252049 252445 248433 270251 214694 354875
 347443 215675 272189 252807 255040 256554 252272 273744 214977 3436464
 344351 216423 272030 253365 252114 255722 251441 273431 214746 348625
 351029 226597 265572 262005 251178 255339 249502 271093 215027 354867
 347356 238783 245635 276238 258889 268837 266947 286297 234182 362174
 342552 273993 227511 287231 237138 226857 216325 233431 20463 31794
 292453 231475 0 269650 316361 349490 359545 360275 316193 333632

लगातार याद करने के साथ "सर्वश्रेष्ठ चाल" का क्रम इस तरह दिखता है (चित्र देखें):
सी 1, जे 8, ए 8, एच 1, ए 4, जे 4, डी 10, जी 10, ई 1, डी 2, बी 3, ए 2, सी 9, बी 10, एच 9, आई 10, आई 7, जे 6, आई 5, एच 6, जे 2, आई 3, एच 4, जी 5, जी 2, जी 2, जी 2 एफ 3, ई 4, बी 7, ए 6, बी 5, सी 6, सी 3, डी 4, डी 5, एफ 6।
यह देखा जा सकता है कि युद्धपोतों को पकड़ने के लिए कार्यक्रम को कोई जल्दी नहीं है। 24 वीं चाल से, जब "विकर्ण" एल्गोरिथ्म ने एक गारंटीकृत हिट से पहले अंतिम चाल छोड़ दी होगी, शेष जहाज के स्थानों की संख्या लगभग 240 * 10 ^{9 है} , और "विकर्ण" एल्गोरिथ्म के लिए यह 260 * 10 ^{9 है} । अंतर छोटा है। इन एल्गोरिदम के बीच एक टूर्नामेंट की व्यवस्था करना आवश्यक होगा ताकि यह पता लगाया जा सके कि यह कितना महत्वपूर्ण है।

सी बैटल वीक

समुद्री युद्ध GORKOFF खेलने के लिए इष्टतम एल्गोरिथ्म
"समुद्र की लड़ाई" में खेल की एल्गोरिथ्म: दुश्मन को अवैयक्तिक रूप से गोलाबारी करना

और पुराने प्रकाशन:
खेल "सी लड़ाई" का सिद्धांत और अभ्यास - ईमानदारी से पैदा हुआ 2 क्रिस्टल
आर्टिफिशियल इंटेलिजेंस नेवल लड़ाई - ईमानदारी से मिचुरिन