🚬 🈯️ 💇🏼 खेल का इतिहास ट्रिपल एक्स, या आपको अपने सिर को तोड़ने के लिए कितने वर्गों की आवश्यकता है 🛋️ 🕵🏿 🤵🏿

वेब प्रोग्रामिंग की मूल बातें सीखने के लिए, मैंने एक HTML5 गेम लिखने का फैसला किया - ट्रिपलएक्स ( www.quadpuzzle.ru ) नामक एक पहेली। अपने लिए और दोस्तों के लिए खेल लिखना आधी लड़ाई है। मैं इस परियोजना को दिमाग में लाना चाहता था, जिससे उत्पाद को उपयोगकर्ताओं की एक विस्तृत श्रृंखला के लिए तैयार किया जा सके। यह आप पर निर्भर करता है कि आप कितना न्याय करते हैं।

खेल के नियम सरल हैं। खेल के मैदान पर, चौकों से आंकड़े रखे गए हैं। गेम का लक्ष्य सभी आकृतियों को निर्दिष्ट आयत में रखना है। आप केवल एक ही आकार को घुमा सकते हैं, यदि कोई है, तो एक सर्कल के साथ चिह्नित किया गया है। प्रत्येक समस्या का समाधान अद्वितीय है।

कार्य

यह निम्न ब्राउज़रों के नए संस्करणों में काम करता है: ओपेरा, ओपेरा-मोबाइल, सफारी (विंडोज, आईपैड 2), एंड्रॉइड (एचटीसी डिजायर, सैमसंग गैलेक्सी टैब 10.1), क्रोम, फायरफॉक्स और आईई 9।

निम्नलिखित विचारों को लागू किया गया है:

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

इसी तरह के खेल

चुप रहना बेईमानी होगी कि यह मैं नहीं था जिसने खेल का आविष्कार किया था। ट्रिपलएक्स का प्रोटोटाइप एक बहुत ही समान गेम ब्लॉकपॉश 500 ( www.mtoy.biz ) था, जिसे मुझे अपने पहले एंड्रॉइड फोन पर खेलने का मौका मिला था।

संक्षेप में, ट्रिपलएक्स निम्नलिखित में से अलग है:

आकृतियों का आकार:
ब्लॉकपॉज़ 2, 3, 4 और 5 वर्गों के आंकड़ों का उपयोग करता है; ट्रिपलएक्स में केवल 2 और 3 के आंकड़े;
ट्रिपलएक्स में समान स्तर पर कई समान आंकड़े हो सकते हैं, जबकि ब्लॉकपॉज सभी अलग हैं;
ब्लॉकपॉच में कोई घुमाए गए आंकड़े नहीं हैं, ट्रिपलएक्स में कुछ स्तरों पर एक घुमाया गया आंकड़ा है;
ब्लॉकपॉश केवल एंड्रॉइड के लिए है, और ट्रिपलएक्स को किसी भी डिवाइस पर खेला जा सकता है अगर इसमें एचटीएमएल 5 समर्थन वाला ब्राउज़र है।
ईमानदारी से, एंड्रॉइड पर यह ब्लॉकपॉज़ खेलने के लिए अधिक सुखद है - इंटरफ़ेस अधिक उत्तरदायी है। मुझे खुशी होगी अगर कोई ट्रिपल एक्स को एंड्रॉइड या किसी अन्य प्लेटफॉर्म पर पोर्ट करना चाहता है। आप सभी की जरूरत triplex.html में है।

कार्य कहां से आए

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

जनरेटर ने निम्न स्तर खोजे:

खेतों में सभी संयोजनों के माध्यम से चला गया 3x2, 3x3, 4x3, ... 2 और 3 वर्गों से 3 या अधिक आंकड़े के साथ;
सभी समान लोगों को छोड़ दिया (ऊपर और प्रतिबिंब तक);
उनमें से मैंने उन्हें चुना जिसमें केवल एक ही उपाय है;
यदि यह अन्य समाधान नहीं जोड़ता है तो एक सड़ने योग्य आकार को चुना।

कम्प्यूटेशनल एल्गोरिथम जटिलता

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

बता दें कि सॉल्यूशन फिगर WxH के आकार का एक आयताकार आंकड़ा है, जिसमें अन्य आंकड़े (समस्या की स्थिति के आंकड़े) शामिल हैं। स्पर्श करने वाले वर्गों के सभी जोड़े पर विचार करें (एक आम चेहरे के साथ वर्ग) जो समाधान बनाते हैं। ऐसे सभी चेहरे (2 * डब्ल्यू * एच - डब्ल्यू - एच)।

प्रत्येक चेहरा दो अवस्थाओं में से एक में हो सकता है:
0. बंद - पड़ोसी वर्ग अलग-अलग आकार के हो सकते हैं;
1. खुला - दो आसन्न वर्ग एक ही आकृति के हैं।

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

राज्यों के कई संभावित सेटों में 2 ^{(2 * डब्ल्यू * एच - डब्ल्यू - एच)} तत्व होते हैं। यही है, सभी संभावित विभाजनों के माध्यम से सॉर्ट करने के लिए, यह 0 से 2 तक चक्र शुरू करने के लिए पर्याप्त है ^{(2 * डब्ल्यू * एच - डब्ल्यू - एच)} -1, और आई-थ फेस की स्थिति के साथ सूचकांक चर के द्विआधारी प्रतिनिधित्व के प्रत्येक आई-वें पर विचार करें। यदि चक्र शरीर की जटिलता एक स्थिर द्वारा सीमित है, तो सभी संयोजनों को मानने की कुल जटिलता समाधान के क्षेत्र से घातीय होगी। आइए जानें कि आपको कितने पुनरावृत्तियों मिलते हैं।

आयामी स्वरूप	संख्या पुनरावृत्तियों
1x1	2 ^{(2 * 1 * 1 - 1 - 1)} = 2 ⁰ = 1
2x1	2 ^{(2 * 2 * 1 - 2 - 1)} = 2 ¹ = 2
2x2	2 ^{(2 * 2 * 2 - 2 - 2)} = 2 ⁴ = 16
2x3	2 ^{(2 * 2 * 3 - 2 - 3)} = 2 ⁷ = 128
2x4	2 ^{(2 * 2 * 4 - 2 - 4)} = 2 ¹⁰ = 1024
3x3	2 ^{(2 * 3 * 3 - 3 - 3)} = 2 ¹² = 4096
...	...
6x6	2 ^{(2 * 6 * 6 - 6 - 6)} = 2 ⁶⁰

यही है, 6x6 कार्य के लिए लूप इंडेक्स अभी भी 64-बिट पूर्णांक प्रकार में रखा गया है। यदि आप 3 जीएचजेड की आवृत्ति के साथ प्रोसेसर पर 1 प्रोसेसर चक्र प्रति पुनरावृत्ति की गति से खाली शरीर के साथ इस तरह के चक्र की शुरुआत करते हैं, तो कार्यक्रम 12 साल = 2 ⁶⁰ / (3 * 10 ⁹ * 3600 * 24 * 365) के लिए काम करेगा।

जानवर बल फ़िल्टरिंग

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

सामान्य मामले में, एक मनमाना फिल्टर के लिए, यह अनुमान लगाना मुश्किल है कि इस तरह विभाजन की संख्या को कम करना कितना संभव है। हालांकि, एक बहुत ही सरल उदाहरण से पता चलता है कि कभी-कभी महत्वपूर्ण रूप से। तो, फिल्टर के लिए धन्यवाद, जो अलग-अलग वर्गों (वर्गों, जो एक वर्ग से एक स्वतंत्र आंकड़ा है) के साथ विभाजन को छोड़ता है, पहले चरण में विभाजन की संख्या 25% कम हो जाती है: सबसे पुराने वर्ग में दो पड़ोसियों में से एक के लिए कम से कम एक आम चेहरा होना चाहिए। यही कारण है कि 12 साल के बजाय, यह 9 हो जाता है। यदि 4 कोने वर्ग पड़ोसी नहीं हैं, तो "पृथक वर्ग" फ़िल्टर उनमें से प्रत्येक के लिए 25% की खोज को कम कर देता है, और यह पहले से ही है (1 - (3/4) ⁴ ) - 68 %। शेष छोटे वर्गों के लिए समान विचार आदेश ओ (2 ^{डब्ल्यू * एच} ) की गणना में कमी तक जोड़ते हैं।

ट्रिपलएक्स स्तर उत्पन्न करने के लिए निम्नलिखित फिल्टर का उपयोग किया गया था:

1. 2x2Duplicates
- एक फ़िल्टर जो विभाजन को अलग करता है जिसमें चार वर्ग (2x2) होते हैं जो एक ही आकृति के होते हैं, लेकिन चार आम चेहरों में से कम से कम एक आम नहीं है।

2. 1x1Cell
- ऊपर वर्णित पृथक वर्गों का फ़िल्टर।
3. स्ट्रेटकूट
- एक फिल्टर जो सीधे क्षैतिज या ऊर्ध्वाधर खंडों के साथ विभाजन को जोड़ता है। इस तरह की कटौती विभाजन को दो भागों में विभाजित करती है, जिसे पुनर्व्यवस्थित करते हुए, हम दूसरा समाधान प्राप्त करते हैं। यह नियम केवल तब संतुष्ट नहीं होता है जब विभाजन के दोनों हिस्सों में समान सेट होते हैं। इस मामले में, दूसरा समाधान काम नहीं करता है, लेकिन विभाजन हमारे खेल के लिए दिलचस्प नहीं है, क्योंकि विभाजन का प्रत्येक भाग एक छोटे आयाम का एक स्वतंत्र कार्य है।
4. आकार 3
- एक फ़िल्टर जो 3 से कम आंकड़ों के साथ काम करता है। दो आंकड़ों से समस्याओं को हल करना बिल्कुल भी दिलचस्प नहीं है।
5. आकार 23
- एक फ़िल्टर जो विभाजन को अलग करता है जिसमें 4 या अधिक वर्गों के आंकड़े हैं। यह फ़िल्टर ट्रिपल एक्स के लिए विशिष्ट है।
6. RotatedAndReflected
- एक फिल्टर जो समान विभाजनों को त्यागता है - ऐसे विभाजन जो एक दूसरे से 90, 180 या 270 डिग्री और / या दर्पण प्रतिबिंब द्वारा रोटेशन द्वारा प्राप्त किए जाते हैं। इस प्रकार, प्रत्येक समान विभाजन 8 समान विभाजन के साथ जुड़ा हुआ है। चूंकि हमने विभाजन के सेट पर रैखिक आदेश दिया है, इसलिए हम प्रत्येक आठ से न्यूनतम विभाजन चुन सकते हैं। यदि फ़िल्टर किया गया विभाजन न्यूनतम नहीं है, तो हम इसे छोड़ देते हैं। इसका मतलब है कि हम पहले ही इस आठ से विभाजन पर विचार कर चुके हैं।
7. सॉल्वर
- एक ऐसा फ़िल्टर जो विभाजन को अलग करता है जिसके लिए एक से अधिक समाधान हैं। यह फिल्टर शायद सबसे दिलचस्प है, लेकिन मैं इसके काम के एल्गोरिथ्म का वर्णन नहीं करना चाहता हूं, ताकि उन प्रोग्रामरों के लिए कार्य को सुविधाजनक न बना सके जो खेल को पूरा करने के लिए अपने स्वयं के सॉल्वर को लिखना चाहते हैं। मैं कहना चाहता हूं, हालांकि, सॉल्वर शाखा और बाध्य पद्धति का उपयोग करके समाधानों का चयन करता है। 'शाखाओं' (संयोजनों की संख्या) पर पत्तियों की संख्या की गणना सूत्र द्वारा की जाती है
सी! / (सी ₁ ! सी ₂ ! ... सी _एम !)।
जहां C विभाजन में आंकड़ों की संख्या है, m विभाजन में विभिन्न आंकड़ों की संख्या है (समान आंकड़ों के समूहों की संख्या), C _i प्रत्येक समूह में समान आंकड़ों की संख्या है। उदाहरण के लिए, यदि सभी आंकड़े समान हैं, तो संयोजन केवल एक है: एम = 1 और सी = सी ₁ । पहला स्तर (3 अलग-अलग आंकड़े, जब तक हम घूर्णन आकृति पर ध्यान नहीं देते) 3 देता है! / (1! 1! 1) = 6 संयोजन। दसवें स्तर (चार समूहों में 6 आंकड़े) 6 /! (2! 2! 1! 1!) = 180 संयोजन देता है। सौवें स्तर (पांच समूहों में 9 के आंकड़े) 9 देता है! / (3! 3! 1! 1! 1!) = 10080 संयोजन। छह सौवां स्तर लगभग 10 ¹¹ संयोजन देता है। इस तथ्य के बावजूद कि कई संयोजन हैं, सॉल्वर ट्रिपल सेकंड की सभी समस्याओं को 1-2 सेकंड में हल करता है। इससे पता चलता है कि कार्यों को खोजना उन्हें हल करने की तुलना में बहुत अधिक कठिन है। इसलिए, उदाहरण के लिए, 6x6 कार्यों की खोज करते समय, सॉल्वर ने 5887655 कार्यों को हल किया, उनमें से केवल 46 का चयन किया।

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

जनरेटर की रिपोर्ट

6x6 के आयाम के लिए कार्यों की पीढ़ी पर एक रिपोर्ट पर विचार करें। निम्न तालिका से पता चलता है कि कितने विभाजन संसाधित किए गए और कौन से फ़िल्टर।

परीक्षण किया	प्राप्त	अस्वीकृत	% गिरा	% गिरा कुल से संख्या	फिल्टर
596745944245	295317406559	301428537686	50.51	50.51	2x2Duplicates
295317406559	110686580321	184630826238	62.52	30.94	1x1Cell
110686580321	79876633976	30809946345	27.84	5.16	StraightCut
79876633976	79875530828	1103148	0.00	0.00	Shapes3
79875530828	47094698	79828436130	99.94	13.38	Shape23
47094698	5887701	41206997	87.50	0.01	RotatedAndReflected
5887701	46	5887655	100.00	0.00	सॉल्वर
596745944245	46	596745944199	100.00	100.00	संपूर्ण

पहली बात जिस पर मैं ध्यान देना चाहता हूं वह है कुल चेक किए गए विभाजन की संख्या - 596745944245 <2 ⁴⁰ । यही है, 'सीमाओं' तंत्र के लिए धन्यवाद, चेक को 2 ⁶⁰ से घटाकर 2 ⁴⁰ करना संभव था। अगर हम मानते हैं कि इस कार्य को पूरा होने में 12 दिन लगे, तो 'सीमा' तंत्र के बिना, यह 12 * 2 ²⁰ ~ 12 * 10 ⁶ दिन काम करेगा या एक के बजाय एक लाख प्रोसेसर कोर का उपयोग करना होगा। इस तालिका में एक बहुत ही दिलचस्प कॉलम का अभाव है, जो दिखाता है कि प्रत्येक फ़िल्टर ने खोज को कम कर दिया है, यह समझने के लिए कि विभाजक 2 ^{20 में} क्या है।
जैसा कि अपेक्षित था, RotatedAndReflected ने इसके लिए दिए गए सभी विभाजनों का 7/8 = 87.5% फेंक दिया, प्रत्येक आठ समान कार्यों में से केवल एक को चुनना। यह ध्यान रखना दिलचस्प है कि जांच किए गए विभाजन में से, Shapes3 फ़िल्टर - दो-आंकड़ा विभाजन विकल्पों द्वारा छोड़े गए एक लाख से अधिक विभिन्न विकल्प थे। यह भी कल्पना करना मुश्किल है कि ट्रिपल एक्स के लिए एक क्विंटलियन (2 ⁶⁰ ~ 10 ¹⁸ ) 6x6 विभाजन में से केवल 46 का चयन किया गया था। जैसा कि वे कहते हैं, "सभी बेहतरीन"।

समय सारणी

तो 6x6 कार्य के लिए, समय पर (पाया दिनों में) माना जाने वाले विभाजन (कार्य दिवस) के समय और स्तर के पाया स्तरों की संख्या की निर्भरता के ग्राफ (दिन)।

मैं दो बिंदुओं पर ध्यान देना चाहता हूं:

सबसे पहले, ऊपर वर्णित के रूप में, ऊपरी बाएं वर्ग पर लागू पृथक वर्गों के फिल्टर के लिए धन्यवाद, काम 25% से शुरू होता है।
दूसरे, इस तथ्य के बावजूद कि कार्यक्रम ने 12 काम किया
दिन, सभी स्तरों को पहले 4 दिनों में 25% से 40% तक काम किया गया था। अन्य आयामों के साथ, एक ही चीज़ - खोज के आरंभ में पाए गए अधिकांश स्तर पाए गए। यह RotatedAndReflected फ़िल्टर के कारण होता है, जिसमें न्यूनतम आठ समान कार्यों का चयन किया जाता है।

कार्य आयाम तालिका

यह तालिका गेम में गिरे सभी कार्यों का डेटा प्रदान करती है।

क्षेत्र समाधान	आयामी स्वरूप	संख्या स्तरों	समय	संपूर्ण संख्या स्तरों	संपूर्ण समय
8	4x2	2	0	2	0
9	3x3	1	0	3	0
10	5x2	1	0	4	0
12	4x3	4	0	8	0
15	5x3	6	0	14	0
16	4x4	5	0	19	0
18	6x3	8	0	27	0
20	5x4	48	0	75	0
21	7x3	16	0	91	0
24	6x4	27	2 मिनट	118	2 मिनट
24	8x3	16	1min	134	3min
25	5x5	22	3min	156	6min
27	9x3	19	12min	175	17min
28	7x4	45	41min	220	59min
30	6x5	55	3 घंटे	275	4 घंटे
30	10x3	19	2 घंटे	294	6 घंटे
32	8x4	112	17 घंटे	406	23 घंटे
33	11x3	22	20 घंटे	428	2 डी
35	7x5	158	7 दिन	586	9d
36	6x6	46	12d	632	21d
	9x4	69	16D	701	37dn
	12x3	20+	8 दिन +	720+	45 दिन +

यह ध्यान देने योग्य है कि:

जनरेटर ने 45 दिनों से अधिक काम किया।
पहले दिन क्षेत्र 32 तक के कार्य उत्पन्न हुए।
36 के क्षेत्र के साथ कार्यों की खोज में 36 दिन लग गए।
क्रमशः 8x4 और 7x5: 112 और 158 के आयामों के लिए अप्रत्याशित रूप से बड़ी संख्या में कार्य पाए गए। यह अन्य आयामों की तुलना में काफी अधिक है।

विभाजित रंग

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

int color = 1; for(int i = 0; i < H; ++i) { for(int j = 0; j < W; ++j) { if (painted[i][j] == 0) { flood(i, j, color++); } } }

यहां, बाढ़ फ़ंक्शन एक आकृति को पेंट करता है, जो सेल (i, j) से शुरू होता है, उसी आकृति से संबंधित आसन्न कोशिकाओं के अनुक्रम का उपयोग करता है। इस रंग एल्गोरिथ्म की समग्र जटिलता वर्गों की संख्या में रैखिक है - O (W * H)।

रोटेशन आकार

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

कार्यों का आदेश कैसे दिया जाता है

सॉल्वर एक प्राकृतिक तरीके से समस्याओं को हल करता है, क्रमिक रूप से संभव संयोजनों के माध्यम से छंटनी करता है। समस्या हल करने के बाद, सॉल्वर इसे एक कठिनाई स्तर प्रदान करता है - पूर्ण किए गए पुनरावृत्ति चक्रों की संख्या, जो संभव संयोजनों की संख्या से ऊपर से सीमित है, सूत्र C द्वारा गणना की जाती है! / (C ₁ ! C ₂ ! ... C _m !)। ट्रिपलएक्स कार्यों को वर्णित कठिनाई स्तर बढ़ाकर आदेश दिया जाता है। जटिलता का ऐसा मूल्यांकन उस जटिलता से मेल नहीं खाता है जो एक व्यक्ति अनुभव करता है। खिलाड़ी के दृष्टिकोण से प्रत्येक कार्य की जटिलता का आकलन करने के लिए, प्रत्येक कार्य को हल करने के समय के अनाम आँकड़े सर्वर पर रखे जाते हैं। भविष्य में, मुझे उम्मीद है कि ऐसे आँकड़े कार्यों को बेहतर बनाने में मदद करेंगे।

पीढ़ी एल्गोरिथ्म के लिए अन्य विकल्प

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

समस्या 6x6 = 36 के लिए, आंकड़ों की अधिकतम संख्या 18 है, न्यूनतम 12. है। इस प्रकार, सेट की संख्या का अनुमान 8 ¹⁸ / (2! ⁶ 3! 3) के मूल्य से ऊपर से लगाया जा सकता है! = 2 ^48/9 <2 ⁴⁵ (18 के प्रत्येक आंकड़े! 8 में से एक संभव हो सकता है, और क्रमपरिवर्तन की न्यूनतम संख्या से विभाजित) और नीचे से 8 ¹² / (8! 4!)> 2 ¹⁶ (12 आंकड़ों में से एक 8 में से एक हो सकता है, और क्रमपरिवर्तन की अधिकतम संख्या से विभाजित)। आदेशित सेट के लिए, सूत्र समान हैं, लेकिन केवल विभाजक के बिना। एक तरफ, अधिक ऑर्डर किए गए विकल्प होंगे, लेकिन सबसे अधिक संभावना है, सीमाओं के अधिक इष्टतम बाईपास के साथ आना संभव होगा।
आप सभी आठ संख्याओं ( ₁ , ₂ , ... ₈ ) पर टाइप कर सकते हैं, जहां _मैं समाधान में i-th आंकड़े की संख्या है। इस तरह के आठ के लिए, आंकड़ों के कुल क्षेत्र पर एक रैखिक प्रतिबंध लागू होता है:
2 * एक ₁ + 2 * एक ₂ + 3 * एक ₃ + 3 * एक ₄ + ... + 3 * एक ₈ = 36
इस एल्गोरिदम पर काम करने वाले एक कार्यक्रम ने 2 घंटे में ट्रिपलएक्स के सभी स्तरों को पाया। यह विभाजन पर पुनरावृति करने के लिए आवश्यक से 500 गुना अधिक तेज है। सच है, यह ध्यान देने योग्य है कि जटिलता तेजी से बढ़ जाती है। अगले दो हफ्तों में, इस विधि में कुल 1300 स्तर पाए गए।

खेल के ग्राहक पक्ष

खेल का एक महत्वपूर्ण हिस्सा कार्यक्रम है, जो खिलाड़ी को उत्पन्न कार्यों को हल करने का अवसर प्रदान करता है। गेम को HTML, CSS और JavaScript (कुल 2100 लाइनों) में लिखा गया है। सभी तर्क, सभी संसाधन, और यहां तक कि सभी 700+ स्तर एक HTML फ़ाइल में फिट होते हैं। इसलिए, एक बार जब आप गेम डाउनलोड करते हैं, तो आप नेटवर्क कनेक्शन के बिना, इसके अंत तक जा सकते हैं।

ग्राफिक डिजाइन

खेल में ग्राफिक्स बहुत सरल हैं, चित्रों के बिना, पृष्ठभूमि की गिनती नहीं। वर्गों को बहु-रंग के रूप में बनाया जाता है <div> s ढाल के साथ भरें। घुमाए गए वर्ग के अंदर का सर्कल भी एक वर्ग है, केवल अधिकतम गोल सीमाओं और रिवर्स ग्रेडिएंट फिल के साथ। यह पता चला कि IE9 इस तरह की चाल प्रदान नहीं करता है और सर्कल का ग्रेडिएंट फिल अभी भी चौकोर बना है।
मैं खेल में पृष्ठभूमि को जीवंत बनाना चाहता था। इस पर दिवाओं से धीरे-धीरे उड़ने वाले भूरे रंग के गोले होने चाहिए। स्पष्ट रूप से एचटीसी सेंस के डिजाइन से प्रेरित है। हालाँकि, मुझे दो बाधाएँ आईं।
सबसे पहले: यह उन्हें उड़ाने के लिए बहुत अच्छी तरह से काम नहीं करता था: एक कारण से, प्रति सेकंड एक पिक्सेल की आवाजाही अचानक, हिलती हुई दिखती थी। मैंने 1.0 से कम की वेतन वृद्धि में अधिक बार शिफ्ट करने की कोशिश की, लेकिन वे वैसे भी शिफ्ट हो गए।
दूसरी बात: एंड्रॉइड के लिए कुछ ब्राउज़रों में, यहां तक कि कुछ बड़े सर्कल ने सिस्टम को बहुत अधिक लोड किया। इसलिए, मैंने बस पृष्ठभूमि से एक स्थिर चित्र बनाया और इसे सीएसएस फ़ाइल में सीएसएस में इस सीएसएस मंत्र के साथ बनाया: पृष्ठभूमि-छवि: url (डेटा: छवि / png; base64, / 9j / 4AAQSkZ ... =);
ताकि चौकों का आकार स्क्रीन के आकार और रिज़ॉल्यूशन पर समायोजित हो जाए, मैंने स्प्राइट्स का उपयोग नहीं किया, क्योंकि जब उन्हें स्केल किया जाता है, तो वे फ़ज़ी हो जाते हैं।
शायद कोई पूछेगा कि मैंने 2D ग्राफिक्स के लिए HTML5 कैनवास का उपयोग क्यों नहीं किया? मैं मानता हूं कि ऐसे सरल ग्राफिक्स के लिए, कैनवस की कार्यक्षमता बहुत अच्छी तरह से काम करेगी। लेकिन ऐसा हुआ कि जब मैंने प्रोटोटाइप लिखा, मुझे कैनवस समन्वय ग्रिड की एक अप्रिय विशेषता के बारे में पता था: पूर्णांक निर्देशांक पिक्सेल के बीच के अंतराल को इंगित करते हैं। इसके अलावा, मेरे नए टैबलेट पर कैनवस का प्रदर्शन उत्साहजनक नहीं था। इसलिए, पहले प्रोटोटाइप ने HTML डोम का उपयोग किया और DIV तत्वों के वर्ग जो अंतिम संस्करण के लिए बच गए।

पारित स्तरों को सहेजना

अधिकांश लोगों के लिए एचटीएमएल गेम की धारणा जिनके बारे में मैंने ट्रिपलएक्स को दिखाया था, ने उन्हें पारित होने के परिणामों को बचाने के बारे में चिंता की। आमतौर पर उन्होंने 15-30 वें स्तर पर कहीं पूछा: "और अगर नेटवर्क बंद हो जाता है या कंप्यूटर फ्रीज हो जाता है, तो क्या सब कुछ फिर से चल सकता है?"
यह ध्यान रखना महत्वपूर्ण है कि गेम आपकी हार्ड ड्राइव पर आपके ब्राउज़र प्रोफ़ाइल में हर 10 सेकंड में स्वचालित रूप से सहेजा जाता है। इसलिए, कंप्यूटर को बंद करने या पृष्ठ को ताज़ा करने से डरो मत। स्टोरेज इंजन HTML5 लोकलस्टोरेज का उपयोग करता है। यह, साथ ही तथ्य यह है कि सभी स्तरों को खेल में ही संग्रहीत किया जाता है, आपको नेटवर्क कनेक्शन के बिना खेलने की अनुमति देता है।
हालाँकि, लोकलस्टोरेज में सिक्के का एक फ्लिप साइड भी होता है, जिसे मैंने बीटा परीक्षण के दौरान खोजा, एक नए डोमेन नाम को पंजीकृत करने और गेम को एक नए पते पर स्थानांतरित करने का निर्णय लिया। तथ्य यह है कि लोकलस्टोरेज साइट के डोमेन नाम से जुड़ा हुआ है। यह पता चला है कि यदि खिलाड़ी किसी अन्य साइट से गेम डाउनलोड करता है, तो आपको फिर से शुरू करना होगा। समस्या को व्यवस्थित रूप से देखने के लिए, आइए स्पष्ट करते हैं कि लोकलस्टोरीज को और किस चीज से जोड़ा गया है। स्थानीय ड्राइव पर, जिसका अर्थ है कि आप किसी अन्य डिवाइस (या तो काम पर, या घर पर, अच्छी तरह से, या फोन पर) नहीं खेल सकते हैं। ब्राउज़र के लिए एक बाइंडिंग भी है, लेकिन हमें यह नहीं पता है कि लोकलस्टोरेज को कहाँ और किस प्रारूप में संग्रहीत किया गया है। फिर मेरे हाथ अच्छी पुरानी कुकीज़, लॉगिन, पासवर्ड और परिष्कृत स्क्रिप्ट के साथ सर्वर समर्थन के लिए पहुंच गए। और जब आलस का विरोध किया गया, तो उस समय की एक और प्राचीन पद्धति का सहारा लेने का फैसला किया गया था जब हमारे महान-दादाओं ने अभी भी लोगों को काले और सफेद टीवी सेट और बांका के सेट-टॉप बॉक्स के पीछे खींच लिया था। हां, आपने अनुमान लगाया, मैं कागज के टुकड़े पर पेंसिल में स्तर संख्या और उसका कोड लिखने की बात कर रहा हूं। कोड गेम के विकल्पों में पाया जा सकता है।

अंतर्राष्ट्रीयकरण और स्थानीयकरण

मैंने अपनी चाची से वादा किया कि मैं खेल खत्म कर दूंगा और वह खेल सकती है। इसलिए, मैंने खेल को रूसी या किसी अन्य भाषा में अनुवाद करने का अवसर महसूस करने का फैसला किया। इस तरह के अवसर को अंतर्राष्ट्रीयकरण कहा जाता है, और i18n को डेवलपर्स के घेरे में नामित किया जाता है, क्योंकि अंग्रेजी शब्द इंटर्नकैसिलेशन में, पहले i और अंतिम n के बीच 18 वर्ण हैं।
I18n को लागू करने का विचार इतना सरल था कि मुझे इसके लिए तैयार समाधान भी नहीं देखना पड़ा। प्रत्येक HTML तत्व के लिए जिसमें भाषा पाठ है, वर्ग 'i18n' निर्दिष्ट किया गया था। उदाहरण के लिए: <span class = 'i18n'> सरल ग्राफिक्स </ span>। गेम कोड में, I18N संरचना दर्ज की गई है, जिसमें सभी वाक्यांशों के अनुवाद शामिल हैं:

  //   var I18N = { "OK": { ru: "OK", fr: "bon", de: "OK", zh: "??" }, "simple graphics": { ru: " ", fr: "graphiques simple", de: "einfache Graphik", zh: "????" }, ... }

I18n वर्ग के सभी तत्वों के लिए पहले भाषा परिवर्तन में, उनकी मूल सामग्री को मूल HTML फ़ील्ड में संग्रहीत किया गया है और I18N संरचना में निर्दिष्ट अनुवाद के साथ बदल दिया गया है।
वाक्यांश 'एन सेकंड / मिनट / घंटे / दिन पहले' को एक संदर्भ-संवेदनशील अनुवाद की आवश्यकता थी। ऐसा करने के लिए, मुझे तर्क को थोड़ा जटिल करना पड़ा। I18N संरचना में, अनुवाद के बजाय, आप एक फ़ंक्शन निर्दिष्ट कर सकते हैं जो संदर्भ के आधार पर अनुवाद करता है:

  "seconds ago": { en: i18nSecondsAgoEn, ru: <b>i18nSecondsAgoRu</b>, fr: " il ya quelques seconds", de: i18nSecondsAgoDe, zh: " ???" }, ... function <b>i18nSecondsAgoRu</b>(context) { return i18nNumberRu(context, '', '', ''); } ... function i18nNumberRu(context, num0, num1, num2) { var num = +context; var result; if (num >= 20) { num = num % 10; } if (num == 1) { result = num1; } else if (2 <= num && num <= 4) { result = num2; } else { result = num0; } return context + ' ' + result + ' '; }

मैंने रूसी स्थानीयकरण (l10n = स्थानीयकरण) किया, फ्रांसीसी, जर्मन और चीनी मेरे दोस्तों द्वारा किए गए थे: जूलिया, सेर्गा और एलेक्सी के साथ माशा।

उपलब्धि तालिका

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

सभी खिलाड़ी देखते हैं कि वर्तमान स्तर को हल करने के लिए सबसे पहले कौन और कितनी देर पहले था;
प्रत्येक स्तर को पारित करने के बाद, स्तर को पारित करने का समय सर्वर को भेजा जाता है, और यदि किसी ने इस स्तर को अभी तक पारित नहीं किया है, तो आप तालिका में अपना नाम भी दर्ज कर सकते हैं।

गेम कैसे हैक करें

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

सभी इनपुट मापदंडों के लिए चेक हैं;
एसक्यूएल प्रश्नों में विशेष पात्रों से बचना;
उच्च स्कोर तालिका में विशेष HTML वर्णों से बचना।

पारित होने के समय पर आंकड़े खराब करना आसान है, लेकिन यह किसी भी तरह से खेल को प्रभावित नहीं करता है, और केवल स्तरों की कठिनाई के अनुमानित अनुमान के लिए बनाया गया है।

साइट को तैयार करने और गेम को इंटरनेट पर रखने के बारे में प्रश्न

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

धन का मुद्दा

यह पता चला कि इस दुनिया में सब कुछ मुफ्त में नहीं किया जा सकता है। जबकि खेल की लागत काफी मामूली है: एक डोमेन नाम के लिए 150 रूबल / वर्ष, एक साधारण होस्टिंग के लिए 300 रूबल / वर्ष, विज्ञापन द्वारा बोझ नहीं। हाल ही में, मैंने गेम को दोस्तों ( अलेक्सईज़ावजालोव , विट्रोओट ) द्वारा मुफ्त में प्रदान की गई होस्टिंग में स्थानांतरित किया और उस पर phpBB3 फोरम इंजन स्थापित किया। मैं ट्रिपलएक्स को वाणिज्यिक पटरियों पर स्थानांतरित करने की योजना नहीं बनाता हूं, और मैं खेल को स्वतंत्र और विज्ञापन से मुक्त रखने की कोशिश करूंगा। भविष्य में, मैं स्तर जनरेटर के स्रोत को पोस्ट कर सकता हूं। हालांकि, मुझे लगता है, किसी भी प्रोग्रामर के लिए इस लेख को पढ़कर स्वतंत्र रूप से लिखना मुश्किल नहीं होगा।

निष्कर्ष

खैर, यह सब, ऐसा लगता है, जिसके लिए अभी भी बताने का समय था। मुझे उम्मीद है कि आप इस खेल का उतना ही आनंद लेंगे जितना कि इसे बनाने में मेरी दिलचस्पी थी।

खेल का इतिहास ट्रिपल एक्स, या आपको अपने सिर को तोड़ने के लिए कितने वर्गों की आवश्यकता है