अच्छा सुडोकू कैसे बनता है: 17 संकेत, एक ही हल और असली कठिनाई

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

कुल कितने सुडोकू ग्रिड हैं?

पहले पूरी तरह भरे ग्रिड की बात करें: ऐसी 9×9 तालिकाएँ जिनकी हर पंक्ति, हर स्तंभ और हर 3×3 बॉक्स में 1 से 9 तक के अंक ठीक एक-एक बार आते हैं। बर्ट्राम फ़ेल्गेनहाउर और फ़्रेज़र जार्विस ने कंप्यूटर से इन्हें गिना और 2006 में Mathematical Spectrum पत्रिका में परिणाम प्रकाशित किया। ऐसे ठीक 6,670,903,752,021,072,936,960 ग्रिड हैं, यानी लगभग 6.67 × 10²¹।

लेकिन इनमें से बहुत-से ग्रिड असल में एक ही ग्रिड के अलग-अलग रूप हैं। आप अंकों के नाम बदल सकते हैं (जैसे हर 1 को 7 बना देना), तीन पंक्तियों की एक पट्टी के भीतर पंक्तियाँ बदल सकते हैं, पूरी पट्टियों की अदला-बदली कर सकते हैं, स्तंभों के साथ भी यही कर सकते हैं, या ग्रिड को विकर्ण पर पलट सकते हैं। एड रसेल और फ़्रेज़र जार्विस ने समूह सिद्धांत की बर्नसाइड लेम्मा की मदद से गिना कि इन सभी बदलावों के बाद वास्तव में कितने ग्रिड अलग बचते हैं। मैकगायर और उनके साथियों के अनुसार यह गणना ख़ुद केवल लगभग एक सेकंड में पूरी हो गई। नतीजा: 5,472,730,538 “मूल रूप से अलग” ग्रिड।

पूरे सुडोकू ग्रिड की गिनती

क्या गिना गया	संख्या	स्रोत
पूरे 4×4 ग्रिड (2×2 बॉक्स)	288	मैकगायर, टुगेमान और सिवारियो
पूरे 9×9 ग्रिड	6,670,903,752,021,072,936,960	फ़ेल्गेनहाउर और जार्विस (2006)
मूल रूप से अलग 9×9 ग्रिड	5,472,730,538	रसेल और जार्विस (2007)

कम से कम 17 संकेत: 16 क्यों असंभव है

पहेली असल में एक हल किया हुआ ग्रिड है जिसके ज़्यादातर अंक मिटा दिए गए हैं। अगर बहुत ज़्यादा अंक मिटा दिए जाएँ, तो बचे हुए संकेत किसी एक उत्तर तक नहीं पहुँचाते। तो एक सही पहेली कम से कम कितने संकेतों से बन सकती है? शौकीनों ने 17 संकेतों वाली दसियों हज़ार पहेलियाँ खोजीं। गॉर्डन रॉयल ने इन्हें एक सूची में इकट्ठा किया और उनकी सूची आगे चलकर 49,151 अलग-अलग 17-संकेत वाली पहेलियों तक पहुँच गई। 16 संकेतों वाली कोई मान्य पहेली कभी नहीं मिली, लेकिन “किसी को नहीं मिली” कहना प्रमाण नहीं है।

प्रमाण गैरी मैकगायर, बास्टियन टुगेमान और जिल सिवारियो ने दिया। उनका प्रीप्रिंट जनवरी 2012 में आया और समीक्षित संस्करण 2014 में Experimental Mathematics पत्रिका में प्रकाशित हुआ। उनका तरीका कहने में सरल पर करने में बेहद कठिन था: हर संभव हल-ग्रिड को एक-एक करके जाँचना कि उसमें कोई 16-संकेत वाली पहेली छिपी तो नहीं।

इसकी कुंजी है अपरिहार्य समूह (unavoidable set)। चार ऐसे खानों की कल्पना करें जो दो पंक्तियों, दो स्तंभों और दो बॉक्सों में फैले हों और जिनमें 3-8 / 8-3 का पैटर्न हो। इन चार खानों में 3 और 8 की अदला-बदली कर दें, तो एक और पूरी तरह मान्य ग्रिड बन जाता है। यानी अगर इन चारों में से कोई भी खाना संकेत के रूप में न दिया गया हो, तो पहेली के दो हल होंगे। हर पूरे ग्रिड में ऐसे कई छोटे-बड़े समूह होते हैं, और सही पहेली को हर समूह में कम से कम एक संकेत रखना ही पड़ता है। गणित में इसे हिटिंग सेट (hitting set) समस्या कहते हैं। टीम ने checker नाम का एक बहुत तेज़ प्रोग्राम लिखा, जो किसी ग्रिड के सभी 16-खाने वाले हिटिंग सेट गिनता है और जाँचता है कि क्या उनमें से कोई एक ही हल देता है।

फिर उन्होंने इसे सभी 5,472,730,538 मूल रूप से अलग ग्रिड पर चलाया। यह खोज जनवरी से दिसंबर 2011 तक आयरिश सेंटर फ़ॉर हाई-एंड कंप्यूटिंग (ICHEC) के Stokes क्लस्टर पर चली। इसमें लगभग 71 लाख कोर-घंटे लगे, यानी औसतन प्रति ग्रिड करीब 3.6 सेकंड। लेखकों के अनुसार उनके प्रोग्राम का 2006 वाला पहला संस्करण यही काम करने में अनुमानित 3,00,000 प्रोसेसर-वर्ष लेता। बेहतर एल्गोरिद्म ने इसे घटाकर लगभग 800 कर दिया। कोई भी 16-संकेत वाली पहेली नहीं मिली, इसलिए 17 ही असली न्यूनतम है।

एक और सरल तथ्य है जिसका प्रमाण एक वाक्य में हो जाता है: सही पहेली में नौ में से कम से कम आठ अंक संकेत के रूप में दिखने चाहिए। अगर, मान लीजिए, 4 और 6 दोनों संकेतों में न हों, तो आप हल में सारे 4 और 6 आपस में बदलकर दूसरा मान्य उत्तर पा सकते हैं।

एक ही हल क्यों ज़रूरी है (और अनुमान लगाने की ज़रूरत क्यों नहीं)

पीटर नॉरविग ने सुडोकू हल करने पर अपने प्रसिद्ध लेख में लिखा है: “Puzzles that appear in books and newspapers always have one unique solution.” (किताबों और अख़बारों में छपने वाली पहेलियों का हमेशा एक ही हल होता है।) यह सिर्फ़ एक परंपरा नहीं है। यही विशिष्टता सुडोकू को किस्मत का नहीं, तर्क का खेल बनाती है।

जब पहेली का ठीक एक हल होता है, तो हर खाने का मान संकेतों से तय हो जाता है। यानी शुरुआत से अंत तक तर्क की एक कड़ी हमेशा मौजूद होती है, चाहे वह लंबी और ढूँढने में कठिन हो। अगर पहेली के दो हल हों, तो कभी न कभी आप ऐसी जगह पहुँचेंगे जहाँ किसी खाने में 2 और 5 दोनों फिट होते हैं और ग्रिड में कुछ भी नहीं बताता कि कौन-सा चुनें। आपको अनुमान लगाना पड़ेगा, और आधे मामलों में किताब के पीछे छपा “सही” उत्तर आपके पूरी तरह तार्किक नतीजे से मेल नहीं खाएगा।

नॉरविग का लेख यह भी दिखाता है कि विशिष्टता को जान-बूझकर जाँचना क्यों पड़ता है। उनका सरल रैंडम जनरेटर तब तक खाने भरता है जब तक कम से कम 17 खाने और 8 अलग-अलग अंक न आ जाएँ। तरीका तेज़ है, लेकिन वे बताते हैं कि इससे एक ही हल की गारंटी नहीं मिलती: उनकी कुछ रैंडम पहेलियों के कई हल हैं और एक छोटे हिस्से का कोई हल ही नहीं है।

सममिति और हाथ से बनी पहेलियाँ

जिस पहेली को आज हम सुडोकू कहते हैं, वह पहले अमेरिका में सामने आई। इसका श्रेय आमतौर पर हॉवर्ड गार्न्स को दिया जाता है और 1979 में Dell Magazines ने इसे Number Place नाम से छापा। जापानी प्रकाशक निकोली अपनी वेबसाइट पर बताता है कि उसे यह पहेली एक अमेरिकी पत्रिका में मिली, उसने 1984 में इसे जापानी पाठकों से परिचित कराया और बाद में लंबे जापानी नाम को छोटा करके “Sudoku” कर दिया। निकोली के अनुसार शुरू में यह ज़्यादा लोकप्रिय नहीं हुई। 1986 में संपादकों ने नियम बनाया कि संकेत एक सममित पैटर्न में रखे जाएँ, और उसके बाद यह बड़ी हिट बन गई।

सबसे आम पैटर्न 180 डिग्री की घूर्णन सममिति है: ग्रिड को उल्टा घुमाने पर संकेत वाले खाने फिर से संकेत वाले खानों पर ही आते हैं। इसका तर्क पर कोई असर नहीं होता, यह पूरी तरह सौंदर्य की बात है। हाँ, इसकी एक छोटी कीमत है: माना जाता है कि ऐसी सममिति वाली पहेली में कम से कम 17 नहीं, 18 संकेत चाहिए।

निकोली आज भी अपनी पहेलियाँ हाथ से बनाता है। इसकी वजह बताने वाले पेज पर मुख्य संपादक नोबुहिको कानामोतो कहते हैं: “Good Sudoku authors are always considering a solver’s feelings.” (अच्छे सुडोकू लेखक हमेशा हल करने वाले की भावनाओं का ध्यान रखते हैं।) इंसानी लेखक एक संतोषजनक रास्ता सोच सकता है: आसान शुरुआत, बीच में एक चतुर कदम और साफ़ अंत। कंप्यूटर अनगिनत मान्य पहेलियाँ बना सकता है, लेकिन उनमें डिज़ाइन का वह एहसास है या नहीं, यह इस पर निर्भर करता है कि उन्हें कितनी सावधानी से छाँटा गया है।

कंप्यूटर जनरेटर आमतौर पर कैसे काम करते हैं

ज़्यादातर सुडोकू वेबसाइटें, ऐप और किताबें जनरेटर पर निर्भर होती हैं। बारीकियाँ अलग-अलग होती हैं, पर सामान्य तरीका कुछ ऐसा है:

1. पूरा ग्रिड बनाना। रैंडम फ़ैसले लेने वाला बैकट्रैकिंग सॉल्वर खाली बोर्ड को भरता है और इस तरह एक रैंडम मान्य हल बनता है।
2. संकेत हटाना। खाने एक-एक करके खाली किए जाते हैं (या अगर सममिति चाहिए तो सममित जोड़ों में)।
3. हर बार हटाने के बाद विशिष्टता जाँचना। एक सॉल्वर हल गिनता है और दूसरा हल मिलते ही रुक जाता है। अगर एक से ज़्यादा हल हों, तो आख़िरी हटाया गया संकेत वापस रख दिया जाता है।
4. नतीजे को ग्रेड देना। इंसानी तकनीकों की नकल करने वाला दूसरा सॉल्वर आसान से कठिन कदमों की ओर पहेली हल करता है और सबसे कठिन ज़रूरी तकनीक दर्ज करता है।

Ozerlyn Games की पहेलियाँ भी इन्हीं सिद्धांतों पर चलती हैं: हर पहेली का एक ही हल होता है और उसे एक कठिनाई स्तर दिया गया है, ताकि उसे सिर्फ़ तर्क से हल किया जा सके।

कठिनाई तकनीक से आती है, संकेतों की संख्या से नहीं

यह मान लेना आसान है कि कम संकेत यानी कठिन पहेली। मोटे तौर पर इसमें थोड़ी सच्चाई है, पर यह भरोसेमंद नहीं है। 2012 में Scientific Reports में प्रकाशित एक अध्ययन में मारिया एरसे-रावास और ज़ोल्टान टोरोत्सकाई ने गणितीय मॉडल से पहेलियों की कठिनाई मापी। उन्होंने पाया कि उनकी जाँची गई 17 और 18 संकेतों वाली पहेलियाँ, 21 या 22 संकेतों वाली सबसे कठिन पहेलियों से आसान थीं। उनका निष्कर्ष: कठिनाई केवल इस पर निर्भर नहीं करती कि कितने संकेत हैं, बल्कि इस पर भी कि वे कहाँ रखे गए हैं।

शब्दों में एक तुलना देखें। पहेली A में केवल 24 संकेत हैं, लेकिन वे इस तरह फैले हैं कि हर चरण में किसी अंक के लिए किसी पंक्ति, स्तंभ या बॉक्स में सिर्फ़ एक ही जगह बचती है। ग्रिड भरने तक बस हिडन सिंगल (hidden single) ढूँढते रहिए। पहेली B में 30 संकेत हैं, फिर भी दर्जन भर आसान अंक भरने के बाद हर बचे खाने में दो या तीन उम्मीदवार रह जाते हैं और कोई सिंगल नहीं बचता। आगे बढ़ने के लिए X-Wing या कोई चेन चाहिए। संकेतों की संख्या के बावजूद A आसान है और B कठिन।

इसीलिए गंभीर रेटिंग प्रणालियाँ ज़रूरी तकनीकों को मापती हैं। सबसे प्रसिद्ध है Sudoku Explainer (SE) रेटिंग, जो पहेली को हल करने के लिए ज़रूरी सबसे कठिन कदम के आधार पर अंक देती है: सिंगल को कम, पेयर और X-Wing को ज़्यादा, और चेन व फ़ोर्सिंग नेट को उससे भी ज़्यादा। हमारा लेख सुडोकू SE रेटिंग क्या है? इस पैमाने को विस्तार से समझाता है, और SE रेटिंग कैलकुलेटर से आप किसी भी पहेली की रेटिंग ख़ुद निकाल सकते हैं।

खिलाड़ी के रूप में आपके लिए इसका क्या मतलब है

• पहेली उसकी रेटिंग देखकर चुनें, इस पर नहीं कि वह कितनी खाली दिखती है। कम संकेतों वाला ग्रिड ज़रूरी नहीं कि कठिन हो, और भरा-भरा ग्रिड ज़रूरी नहीं कि आसान हो।
• अगर “आसान” पहेली कठिन लग रही है, तो शायद आप सिर्फ़ नेकेड सिंगल (एक ही उम्मीदवार वाले खाने) ढूँढ रहे हैं। आसान पहेलियाँ अक्सर हिडन सिंगल पर टिकी होती हैं। “इस खाने में क्या आ सकता है?” की जगह पूछें “इस बॉक्स में 7 कहाँ जा सकता है?”
• अगर लगे कि अनुमान लगाना पड़ेगा, तो आपसे कुछ छूट गया है। एक ही हल होने पर हमेशा अगला तार्किक कदम मौजूद होता है। कोई जोखिम लेने से पहले अपने नोट्स दोबारा जाँचें।
• विशिष्टता भी एक औज़ार है। अनुभवी खिलाड़ी इस तथ्य का इस्तेमाल करते हैं कि पहेली का एक ही हल है, ताकि ऊपर बताए 3-8 / 8-3 आयत जैसे पैटर्न को खारिज कर सकें। “यूनिक रेक्टेंगल” (unique rectangle) तकनीक इसी विचार पर आधारित है।

इसे आज़माने के लिए हमारे ऑनलाइन सुडोकू पेज पर अपने स्तर की पहेली खेलें, या प्रिंट करने योग्य सुडोकू से कुछ पहेलियाँ छापकर पेंसिल से हल करें। हर पहेली में ध्यान दें कि सबसे कठिन कदम कौन-सा था।

स्रोत

1. Gary McGuire, Bastian Tugemann, Gilles Civario: There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration, Experimental Mathematics 23(2), 2014, पृ. 190–217।
2. यही लेख मुफ़्त प्रीप्रिंट के रूप में: arXiv:1201.0749 (ग्रिड की गिनती, रॉयल की 49,151 पहेलियों की सूची और गणना का विवरण सहित)।
3. Bertram Felgenhauer, Frazer Jarvis: Mathematics of Sudoku I, Mathematical Spectrum 39(1), 2006। विधि का सार: Cornell University, “Counting Sudoku solutions”।
4. Ed Russell, Frazer Jarvis: Mathematics of Sudoku II, Mathematical Spectrum 39(2), 2007। अवलोकन: Mathematics of Sudoku (Wikipedia)।
5. María Ercsey-Ravasz, Zoltán Toroczkai: The Chaos Within Sudoku, Scientific Reports 2, 725, 2012।
6. Peter Norvig: Solving Every Sudoku Puzzle।
7. Nikoli: Sudoku (पहेली का इतिहास) और Why hand made?
8. Sudoku (Wikipedia): इतिहास, हॉवर्ड गार्न्स और Dell की Number Place।