बचपन से समय का हत्यारा

मुझे यकीन है कि कई पाठकों ने कभी-कभी शिक्षक को सुनने के बजाय कक्षा में बेकार बकवास में लगे हुए थे। मैंने ठीक वैसा ही किया, और समय को मारने का एक तरीका कागज पर खेलना था। पूर्वावलोकन खेल (जिसका नाम अभी भी मेरे लिए अज्ञात है) मुझे विशेष रूप से दिलचस्प लगा, लेकिन इसके दो कारण हैं: इसमें किसी दूसरे व्यक्ति की आवश्यकता नहीं है और इसे पूरा किया जा सकता है! सच है, ऐसा करना बेहद दुर्लभ था। लंबे समय से मैं सोच रहा था कि समाधान कितना सरल हो सकता है, और अब, कई वर्षों के बाद, इसे प्रोग्रामेटिक रूप से ढूंढना मुश्किल नहीं होगा।

नियम

सबसे पहले, यह नियमों का वर्णन करने लायक है। खेल निम्नलिखित क्षेत्र से शुरू होता है:

123456789
111213141
516171819

यहाँ, 1 से 19 तक की सभी संख्याओं को वर्ण द्वारा वर्णित किया जाता है। 10. के अपवाद के साथ संख्याएँ बाएँ से दाएँ स्थित होती हैं, पंक्ति से पंक्ति में। नियम काफी सरल हैं - प्रत्येक चरण में आपको 2 संख्याओं को पार करने की आवश्यकता है जो निम्न मानदंडों के अनुरूप हैं:

• संख्या या तो समान होनी चाहिए या कुल मिलाकर 10 (1 और 1, 3 और 7, 8 और 2, आदि) होनी चाहिए;
• उन्हें या तो एक दूसरे के ऊपर खड़ा होना चाहिए या श्रृंखला में व्यवस्थित होना चाहिए। इस मामले में, पहले से ही पार किए गए नंबरों को अनदेखा किया जाता है।

पहले कुछ चालों के विकल्पों में से एक नीचे दिखाया गया है:

1 23456789
1 11213141
5161718 19

#2345678 9
# 1 1213141
5161718##

#2345678#
##1213141
5161718##

इस समय जब अधिक चालें नहीं होती हैं, तो सभी चिन्हित संख्याएँ अंत में जुड़ जाती हैं। खेल समाप्त हो जाता है जब पूरे क्षेत्र को पार कर जाता है।

#2345678#
##1213141
51 6 171 8 ##
23 4 8 12 4 12
131415161
718

#2345678#
##1213 1 41
5 1 # 1 71###
23#567#12
131415 1 61
718

#2345678#
##1213#41
5###71###
2 3 #567#12 2 3 #567#12
1 3 1415#61
718

...

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

यह वाजिब सवाल उठाता है - आप कितनी तेजी से इस खेल को खत्म कर सकते हैं? बचपन में, नोटबुक शीट पर एक कॉलम में एक समाधान खोजना संभव था - यह लगभग 40 लाइनें या 360 वर्ण हैं।

मैं खेल को पूरा करने के लिए गारंटीकृत तरीका नहीं जानता। यह पूरी तरह से स्पष्ट नहीं है कि रणनीति कैसे चुनें। यदि आप नहीं कर सकते हैं तो आप इसे स्वयं चलाने का प्रयास कर सकते हैं।

निर्णय

ऐसी समस्याओं के समाधान कैसे मांगे जाते हैं? मैं निश्चित रूप से नहीं जानता, लेकिन मैंने सामान्य हलचल को चुना।

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

123456789 #23456789 12345678# 123456789 123456789 123456789 123456789 ...
111213141 #11213141 #11213141 ##1213141 1##213141 11#213141 11121314# ...
516171819 516171819 516171819 516171819 516171819 516#71819 51617181# ...

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

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

जवाब है

यदि सब कुछ सही है, तो यह पता चलता है कि न्यूनतम समाधान में केवल 68 अक्षर या 8 लाइनें हैं!

मैं इसे जिफ-एनीमेशन के रूप में लाऊंगा। फ्रेम की संख्या को कम करने के लिए कुछ चालों को एक में विभाजित किया गया था:

मैं ईमानदार हूं, यह निर्णय कितना छोटा है, इससे मैं स्तब्ध था। लेकिन शायद यह भाग्य और अन्य निर्णय जल्द ही नहीं मिलेंगे और बहुत लंबे होंगे?

नहीं, निर्णय दुर्लभ नहीं हैं। त्वरित उत्तर 72, 74 और 76 की लंबाई में पाए जाते हैं। और 80 की लंबाई के साथ 4 और मौलिक रूप से अलग-अलग समाधान हैं। सामान्य तौर पर, मैं लंबाई (समावेशी) में 90 तक 30 समाधान खोजने में कामयाब रहा, और अगर मैं सीमा को 100 तक बढ़ाता हूं, तो 170 समाधान होंगे। लेकिन उनकी तलाश और अधिक महंगी हो जाती है।

स्पॉइलर के तहत, इष्टतम समाधान को विस्तार से वर्णित किया गया है:

 123456789 111213141 516171819 123456789 111213141 5161718## 123456789 1##213141 5161718## 12345678# 1##21314# 5161718## #2345678# ###21314# 5161718## #234567## ####1314# 5161718## #234567## ####1314# 5161718## 234567131 45161718 #234567## ####1314# 51#1718## 23#567131 45161718 #234567## ####1314# 51#171### #3#567131 45161718 #234567## ####1314# 51#171### #3#567#31 451617#8 #234567## ####1314# 51#171### #3#56###1 451617#8 #234567## ####1314# 5###71### #3#56###1 451617#8 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 571356145 16178 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 57#356145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 5###56145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 345671314 #####6145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 34567131# ######145 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 3456713## #######45 16#78 #234567## ####1314# 5###71### #3#56###1 451617#82 3#56713## #######45 1##78 #234567## ####1314# 5###71### #3#56###1 451617### 3#56713## #######45 1##78 #234567## ####1314# 5###71### #3#56###1 45161#### ##56713## #######45 1##78 #234567## ####1314# 5###7#### #3#56###1 45161#### ##567#3## #######45 1##78 #234567## ####1314# 5######## ###56###1 45161#### ##567#3## #######45 1##78 #234567## ####1314# ######### ####6###1 45161#### ##567#3## #######45 1##78 #234567## ####1314# ######### ####6###1 45161#### ##56##### #######45 1##78 #234567## ####1314# ######### ####6###1 45161#### ##5###### ########5 1##78 #234567## ####1314# ######### ####6###1 45161#### ######### ######### 1##78 #234567## ####131## ######### ########1 45161#### ######### ######### 1##78 #234567## ####13### ######### ######### 45161#### ######### ######### 1##78 #234567## #####3### ######### ######### 4516##### ######### ######### 1##78 #23456### ######### ######### ######### 4516##### ######### ######### 1##78 #2345#### ######### ######### ######### #516##### ######### ######### 1##78 #234##### ######### ######### ######### ##16##### ######### ######### 1##78 #23###### ######### ######### ######### ##1###### ######### ######### 1##78 #23###### ######### ######### ######### ######### ######### ######### ###78 #2####### ######### ######### ######### ######### ######### ######### ####8 ######### ######### ######### ######### ######### ######### ######### ##### 

मेरा जावा समाधान कोड इस लिंक पर देखा जा सकता है, लेकिन मैं आपको चेतावनी देता हूं कि यह भयानक है, क्योंकि मूल रूप से प्रकाशन के लिए नहीं लिखा। अपने वर्तमान स्वरूप में, यह 70 अक्षरों तक के सभी समाधानों को खोजता है (अर्थात केवल एक समाधान)। कोड में शर्तों के साथ खेलकर इसे ठीक करना आसान है।

आपका ध्यान के लिए धन्यवाद!