यह हमें बताता है कि इस द्विघात समीकरण में?

सुडोकू,सुडोकू.

प्रश्नों के उत्तर देने के लिए सुडोकू पहेलियों का गणितीय अध्ययन किया जा सकता है “कितने पूर्ण सुडोकू ग्रिड?”, “वास्तविक पहेली में संकेतों की न्यूनतम संख्या क्या है??” तथा “सुडोकू ग्रिड सममित कैसे हो सकते हैं?” संयोजी और समूह सिद्धांतों का उपयोग करके.

क्लासिक सुडोकू के लिए मुख्य परिणाम हैं, पूर्ण ग्रिड की संख्या है 6,670,903,752,021,072,936,960 (6.67×1021), कौन, परिवर्तन की वैधता को बनाए रखते हुए कम हो जाता है 5,472,730,538 महत्वपूर्ण रूप से भिन्न समूह.

वहां 26 समरूपता के प्रकार, लेकिन वे केवल के बारे में पाए जा सकते हैं 0.005% सभी भरे हुए ग्रिड के.

एक अद्वितीय समाधान वाली पहेली में कम से कम होना चाहिए 17 समाधान, और प्रत्येक हल की गई जाली के लिए इससे अधिक नहीं हैं 21 समाधान. सबसे बड़ी न्यूनतम पाई गई पहेली है 40 सुराग.

इसी तरह के परिणाम वेरिएंट और छोटे ग्रिड के लिए जाने जाते हैं. शास्त्रीय 9×9 ग्रिड से अधिक सटीक परिणाम सुडोकस के लिए ज्ञात नहीं हैं, हालांकि ऐसे अनुमान हैं जो काफी सटीक माने जाते हैं.

सुडोकू के लिए गणना समाधान

एक दिलचस्प सवाल है, ए कितने प्रकार से हो सकता है 9 द्वारा 9 एकल नियम को पूरा करने के लिए सुडोकू ग्रिड भरा जाना चाहिए?

दूसरे शब्दों में, कितने अलग सुडोकू समाधान मौजूद हैं? हम शुरुआत में बर्ट्रम फेलगेनहावर और फ्रेजर जार्विस द्वारा उपयोग की जाने वाली विधि का वर्णन करते हैं 2006 इस संख्या की गणना करने के लिए.

हमारी भाषा के स्तर को बनाए रखने के लिए, हम एक ग्रिड के ब्लॉक स्ट्रिप्स की तीन पंक्तियों और ब्लॉक स्टैक्स के तीन कॉलम कहते हैं. इस पंक्ति में एक सेल और जे-कॉलम पर माना जाता है (मैं,जे).

हम अलग-अलग ग्रिडों की संख्या को सुडोकू एन कहते हैं. प्रथम, हम निम्नानुसार ग्रिड ब्लॉक कहते हैं:

बी 1 को वैध तरीके से भरने के कितने तरीके हैं? क्योंकि वहां हैं 9 वर्ण जो B1 भर सकते हैं, प्रत्येक कोशिका में एक, वह है 9 पहली सेल के लिए विकल्प.

इनमें से प्रत्येक के लिए 9 विकल्प, वहाँ हैं 8 दूसरी सेल के लिए विकल्प. इनमें से प्रत्येक के लिए 8 विकल्प, वहाँ हैं 7 तीसरे सेल के लिए रवाना हुए.

मूल रूप से, हम के क्रमपरिवर्तन की संख्या की गणना करते हैं 9 पात्र: हम कितने तरीकों से रख सकते हैं 9 में वर्ण 9 स्थान, या कितने तरीकों से हम ऑर्डर कर सकते हैं 9 चीज़ें.

वहां 9 बी 1 भरने के तरीके. वैध बी1 ब्लॉक से शुरू, हम संख्याओं को फिर से चिन्हित या पुनर्व्यवस्थित करके कोई अन्य मान्य B1 ब्लॉक प्राप्त कर सकते हैं.

इसलिए, पहली सरल धारणा जो हम बना सकते हैं वह यह है कि B1 संख्याओं से भरा हुआ है 1, 2, 3, …, 9 क्रम में, जैसा कि नीचे दिया गया है.

अब हम गणना कर सकते हैं कि इस विशेष B1 में कितने वास्तविक ग्रिड अंत हैं: आइए हम इसे N1 कहते हैं. वास्तविक सुडोकू ग्रिड की कुल संख्या N1×9 है!, इसलिए N1=N/9!…

आइए B2 और B3 में पहली पंक्तियों को भरने के तरीकों पर विचार करें. तब से 1, 2 तथा 3 बी 1 में पहली पंक्ति में होते हैं, ये संख्याएँ अन्य पंक्तियों में नहीं हो सकतीं.

इसलिए, केवल संख्याएँ 4, 5, 6, 7, 8 तथा 9 B1 की दूसरी और तीसरी पंक्तियों से B2 और B3 में पहली पंक्ति में मिल सकते हैं.

B2 और B3 में पहली पंक्तियों को भरने के सभी संभावित तरीकों की सूची बनाएं, प्रत्येक ब्लॉक में संख्याओं को पुनर्व्यवस्थित करने तक. बख्शीश: ऐसा करने के दस तरीके हैं जिससे कि बी2 और बी3 के आदान-प्रदान से इन दस तरीकों से आपको दस और तरीके मिले, कुल बीस.

हम इनमें से दो संभावनाओं को प्योर टॉप लाइन कहते हैं: जब नंबर {4,5,6}, जैसा कि बी1 की दूसरी पंक्ति में है, B2 में एक साथ संग्रहित होते हैं, और संख्याएँ {7,8,9}, जैसा कि B1 की तीसरी पंक्ति में है, B3 में एक साथ संग्रहीत हैं, और इसका एक परिवर्तित संस्करण.

अन्य संभावनाएं मिश्रित शीर्ष रेखाएं हैं, जैसा कि वे सेट मिलाते हैं {4,5,6} तथा {7,8,9} जब B2 और B3 की पहली पंक्तियों को भरने के लिए उपयोग किया जाता है.

ग्रिड की पहली पंक्ति के लिए इन बीस संभावनाओं को देखते हुए (प्रत्येक ब्लॉक में संख्याओं को पुनर्व्यवस्थित करने तक), हम यह पता लगा सकते हैं कि पहली पंक्ति को कैसे भरना है.

इस बारे में सोचें कि आप शुद्ध शीर्ष पंक्ति से शुरू करते हुए पहले बैंड को कैसे पूरा कर सकते हैं 1,2,3;{4,5,6};{7,8,9}.

(ध्यान दें: हम एक लिख रहे हैं,बी,c संख्याओं के एक क्रमबद्ध ट्रिपल को निरूपित करने के लिए और {ए,बी,कीबोर्ड संशोधक चाबियों का एक समूह है जिसका उपयोग अन्य कुंजियों के व्यवहार को बदलने के लिए किया जा सकता है} किसी भी क्रम में उन्हें निरूपित करने के लिए।)

कुल कितनी संभावनाएं हैं, बी 2 और बी 3 में प्रत्येक पंक्ति के भीतर अलग-अलग संख्या क्रमों की गिनती करना? क्या यह संख्या अन्य शुद्ध शीर्ष पंक्ति के समान है, 1,2,3;{7,8,9};{4,5,6}?

एमआईटी आवेदन निबंध, हम B1 को स्थिर रखना चाहते हैं क्योंकि हमने पहले ही उन ग्रिडों की संख्या का हिसाब कर लिया है जिन्हें इसमें नौ अंकों को पुनः लेबल करके प्राप्त किया जा सकता है।.

यह पता चला है कि वहाँ हैं (3!)⁶ शुद्ध शीर्ष पंक्ति के साथ घूरने वाले पहले बैंड को पूरा करने के तरीके 1,2,3;{4,5,6};{7,8,9}.

ऐसा इसलिए है क्योंकि हम डालने के लिए मजबूर हैं {7,8,9};{1,2,3} बी 2 और बी 3 में दूसरी पंक्ति में और {1,2,3};{4,5,6} तीसरी पंक्ति में, और फिर हम सभी कॉन्फ़िगरेशन प्राप्त करने के लिए B2 और B3 की छह पंक्तियों में से प्रत्येक में तीन अंकों को पुन: व्यवस्थित कर सकते हैं.

उत्तर अन्य शुद्ध शीर्ष पंक्ति के लिए समान है, क्योंकि इस मामले में हमने जो कुछ भी किया है, वह B2 को B3 से बदल दिया है.

मिश्रित शीर्ष पंक्तियों के मामले अधिक जटिल होते हैं. आइए शीर्ष पंक्ति पर विचार करें 1,2,3;{4,6,8};{5,7,9}. इसे निम्न चित्र के अनुसार पहले बैंड तक पूरा किया जा सकता है, जहाँ एक, बी, और c संख्याएँ हैं 1, 2, 3 किसी भी क्रम में.

ए चुनने के बाद, b और c किसी भी क्रम में शेष दो संख्याएँ हैं, के रूप में वे एक ही पंक्ति में हैं.

चूंकि ए के लिए तीन विकल्प हैं, और बी2 और बी3 में छह सेटों में से प्रत्येक में तीन अंकों को अलग-अलग मान्य फ्रंट पेज प्राप्त करने के लिए छोड़ दिया जा सकता है, इस स्थिति में विन्यासों की कुल संख्या 3× है(3!)6.

आप समान संख्या प्राप्त करने के लिए शेष सत्रह फ्रंट रो केस में से प्रत्येक के माध्यम से इसी तरह काम कर सकते हैं.

अब हमारे पास B1 द्वारा परिभाषित संभावित फ्रंट पेजों की संख्या है: यह 2× है(3!)6+18×3×(3!)6=2612736, जहां योग का पहला भाग शुद्ध शीर्ष पंक्तियों से प्रथम पृष्ठ पूर्णताओं की संख्या है और दूसरा मिश्रित शीर्ष पंक्तियों से प्रथम पृष्ठ पूर्णताओं की संख्या है.

गणना करने के बजाय कि इनमें से प्रत्येक की कितनी प्रथम पृष्ठ पूर्णताएं हैं 2612736 विशेषताएँ, Felgenhauer और Jarvis ने निर्धारित किया कि कौन से फ्रंट पेजों में टॉप ब्लैंक से पहले पेज की पूर्णता की संख्या समान है.

यह विश्लेषण गणना करते समय ध्यान में रखे जाने वाले फ्रंट पेजों की संख्या को कम करता है.

यहां कुछ ऑपरेशन दिए गए हैं जो पहली श्रेणी के ग्रिड के अंत की संख्या को अपरिवर्तित छोड़ देते हैं: संख्याओं पर टिप्पणी करना, पहली श्रेणी के किसी भी ब्लॉक को सुनना, किसी भी ब्लॉक में कॉलम सुनना और रेंज की तीन पंक्तियों को सुनना. इनमें से किसी भी B1 परिवर्तन के साथ, हम इसके मानक रूप को पुनर्स्थापित करने के लिए संख्याओं को फिर से चिह्नित कर सकते हैं.

B1 की व्यवस्था करना, बी 2 और बी 3 ग्रिड के अंत की संख्या रखता है, क्योंकि अगर हम किसी वास्तविक सुडोकू ग्रिड से शुरू करते हैं, इसे वास्तविक रखने का एकमात्र तरीका B4 को चिन्हित करना है, बी 5, बी 6 और बी 7, बी 8, B9 क्रमशः ताकि स्टैक समान रहे.

दूसरे शब्दों में, प्रत्येक वास्तविक फ्रंट-पेज ग्रिड टर्मिनेशन वास्तव में एक वास्तविक फ्रंट-पेज ग्रिड टर्मिनेशन देता है, अर्थात. कोई बी 1, बी 2, बी 3 क्रमपरिवर्तन.
सुनिश्चित करें कि जब आप अगले सुडोको ग्रिड में बी2 को बी3 में बदलते हैं, ग्रिड को वैध रखने का एकमात्र तरीका B5 को B6 और B7 को B8 में बदलना है. इससे ढेर समान रहेंगे, हालांकि उनका स्थान बदल गया है.

यदि आपके पास वैध सुडोकू ग्रिड है और आप किसी भी B1, बी 2 और बी 3, इसे वैध रखने के लिए आपको बाकी सुडोकू ग्रिड के कॉलम के साथ क्या करना होगा? उदाहरण के लिए, अगर आपने कॉलम बदल दिए हैं 1 तथा 2 उपरोक्त ग्रिड पर B2 का, आप परिणामी ग्रिड को कैसे ठीक करेंगे ताकि यह एक नियम को पूरा करे?

अंतिम अभ्यास हमें बताता है कि फ्रंट रो ग्रिड की प्रत्येक फिलिंग फ्रंट रो ग्रिड की एक अनूठी फिलिंग देती है जिसमें ब्लॉक्स के अंदर छोड़े गए कॉलम होते हैं.

इस तरह के विचार हमें गिनती करते समय ध्यान में रखे जाने वाले विशिष्ट फ्रंट पेजों की संख्या को कम करने की अनुमति देते हैं.

Felgenhauer और जार्विस के बाद, हम B2 और B3 कॉलम में स्क्रॉल करते हैं ताकि प्रत्येक कॉलम की शीर्ष पंक्ति प्रविष्टियां आरोही क्रम में हों, और यदि आवश्यक हो तो B2 और B3 की अदला-बदली करें ताकि पहली B2 प्रविष्टि B3 प्रविष्टि से छोटी हो.

इसे लेक्सिकोग्राफिक संक्षिप्त नाम कहा जाता है.

चूंकि दोनों ब्लॉकों में से प्रत्येक में है 6 स्तंभों की पुनर्व्यवस्था और ब्लॉकों को पुनर्व्यवस्थित करने के दो तरीके, लेक्सिकोग्राफिकल शॉर्टहैंड हमें बताता है, पहला पेज दिया, ग्रिड अंत की समान संख्या के साथ 62×2=72 अन्य फ्रंट पेज हैं.

तो अब हमारे पास विचार करने के लिए केवल 2612736/72=36288 फ्रंट पेज हैं.

इनमें से प्रत्येक संभावना के लिए आइए तीनों शीर्ष ब्लॉकों की पुनर्व्यवस्था देखें: वहाँ हैं 6. उनमें से प्रत्येक के लिए हैं 63 प्रत्येक ब्लॉक के भीतर स्तंभों की पुनर्व्यवस्था.

इन कार्यों को करने के बाद, हम B1 को उसके मानक रूप में लौटाने के लिए फिर से चिन्हित करते हैं.

उसी प्रकार, हम समूह की शीर्ष तीन पंक्तियों को ओवरराइड कर सकते हैं और B1 को मानक रूप में लौटाने के लिए फिर से चिह्नित कर सकते हैं. ये ऑपरेशन फ्रंट रो ग्रिड पूर्णता की संख्या को बचाते हैं.

Felgenhauer और Jarvis ने यह निर्धारित करने के लिए एक कंप्यूटर प्रोग्राम का उपयोग किया कि ये ऑपरेशन फ्रंट पेजों की संख्या को कम करते हैं जिन पर विचार किया जाना है 36288 केवल के लिए 416.

आइए इस पहले समूह पर विचार करें.

इस पर विभिन्न ऑपरेशन करें जो इसके ग्रिड एंडिंग की संख्या को बचाते हैं. आप निम्न के साथ शुरुआत कर सकते हैं: पहली और दूसरी पंक्ति की अदला-बदली करें. इसे फिर से चिन्हित करें ताकि B1 अपने मानक रूप में हो. लेक्सिकोग्राफिक रूप से इस ग्रिड को कम करें.

मुख्य बात यह है कि आपने जिस समूह के साथ शुरुआत की थी और जिस समूह के साथ आपने समाप्त किया था, उसके पास पूर्ण सुडोकू ग्रिड तक समान संख्या में पूर्णताएं हैं.

इस प्रकार, इन समूहों में से प्रत्येक के लिए ग्रिड के अंत की संख्या की गणना करने के बजाय, हम उनमें से केवल एक के लिए इसकी गणना कर सकते हैं.

ऐसे और भी कदम हैं जो विचार करने के लिए ग्रिड की संख्या को कम करते हैं. यदि हमारे पास अंकों की एक जोड़ी है {ए,बी} iवीं पंक्ति में a और jth पंक्ति में b के साथ एक कॉलम में, और एक ही जोड़ी दूसरे कॉलम में ith पंक्ति में b और jth पंक्ति में है, प्रत्येक जोड़ी में मूल के समान ग्रिड अंत के साथ एक बैंड होगा.

ऐसा इसलिए है क्योंकि प्रत्येक जोड़ी एक ही कॉलम में स्थित है, और जब दोनों एक ही समय में बदल जाते हैं, एक नियम सहेजा गया है, जो शामिल पंक्तियों को भी संतुष्ट करता है.

उदाहरण के तौर पे, संख्याओं को देखो 8 तथा 9 उपरोक्त उदाहरण के छठे और नौवें कॉलम में. इसके सभी संभावित मामलों पर विचार करें, जिसके साथ फेलगेनहावर और जार्विस बचे हैं 174 पहले का 416 जारी रखने के लिए समूह.

उन्होंने दो अलग-अलग कॉलम या पंक्तियों में पड़ी संख्याओं के एक ही समूह के अन्य विन्यासों पर भी विचार किया है, जिसे उनके कॉलम या रो के अंदर छोड़ा जा सकता है, ग्रिड के अंत की संख्या को अपरिवर्तनीय छोड़कर.

इससे फ्रंट पेजों की संख्या घटकर 71, और इनमें से प्रत्येक की खोज करें 71 मामलों ने उन्हें यह स्पष्ट कर दिया कि वास्तव में केवल 44 पहले पन्ने जिनके ग्रिड पूर्णता की संख्या मिलनी है.

इनमें से प्रत्येक 44 बैंड में पूरे ग्रिड के अंत की संख्या समान होती है.

मान लीजिए C इनमें से किसी एक को निरूपित करता है 44 धारियों. फिर आप उन तरीकों की संख्या की गणना कर सकते हैं जिन्हें सी पूर्ण सुडोकू ग्रिड में पूरा कर सकता है: इसे एनसी कहते हैं.

हमें ग्रिड के nC अंत की इस संख्या को साझा करने वाले mC फ्रंट पेजों की संख्या की भी आवश्यकता है. फिर, सुडोकू ग्रिड की कुल संख्या सिर्फ N=ΣCmCnC है, या सभी के लिए mCnC का योग 44 धारियों.

Felgenhauer और Jarvis ने अंतिम गणना करने के लिए एक कंप्यूटर प्रोग्राम लिखा.

उन्होंने मानक रूप में B1 के साथ N1 मान्य पूर्णताओं की संख्या की गणना की, प्रारंभ स्थल 44 गलियों. फिर उन्होंने इस संख्या को इससे गुणा कर दिया 9! उत्तर पाने के लिए.

उन्होंने पाया कि संभव की संख्या 9 द्वारा 9 सुडोकू ग्रिड N=6670903752021072936960 है, जो लगभग 6.671×1021 है.

लेख और छवि क्रेडिट:

एचटीटीपी://pi.math.cornell.edu/~mec/Summer2009/Mahmood/Count.html