१७ क्ल्यूज का? सुडोकूची अशी कोडी जी तुम्ही अजिबात लहान करू शकत नाही
सुडोकूमधून एक संख्या काढून टाकल्यास ते कठीण होऊ शकते. चुकीची संख्या काढली तर कोड्याचे एकमेव उत्तरच नष्ट होऊ शकते. पूर्ण ग्रिड आणि रिकाम्या पानाच्या मध्ये कुठेतरी एक कठोर मर्यादा आहे: १७ सुरूवातीचे क्ल्यूज. सुडोकू इथेच का थांबते?
उत्तर एका सोप्या प्रश्नापासून सुरू होते—कदाचित जो दुर्लक्षित होतो: तुमच्या कोड्याला फक्त एकच उत्तर आहे का?
एक पूर्ण ग्रिड, एकच उत्तर
क्लासिक ९×९ सुडोकूमध्ये प्रत्येक ओळ (row), स्तंभ (column), आणि ३×३ बॉक्समध्ये १ ते ९ ही अंकं अगदी एकदाच असायला हवीत. निकोलीद्वारे प्रकाशित केलेले मानक नियम हेच आहेत. ग्रिडमध्ये आधीच छापलेले अंक givens (दिलेल्या संख्या) किंवा क्ल्यूज म्हणतात.
पूर्ण ग्रिड हे सर्व नियम पाळते तरीही, त्या दिलेल्या क्ल्यूजपासून तयार होणारे तेच एकमेव उत्तर असेलच असे नाही. जर दोन वेगवेगळ्या पूर्णता (completions) शक्य असतील, तर खेळाडूला setter ने नेमकं कोणती पूर्णता अभिप्रेत होती ते ठरवता येत नाही.
म्हणूनच uniqueness (एकमेवता) महत्त्वाची आहे. नीट मांडलेले क्लासिक सुडोकू तुम्हाला इतकी माहिती देते की नेमके एकच पूर्ण ग्रिड ओळखता येईल. तुम्ही नियमांमध्ये नवीन असाल, तर आमचा सुडोकू खेळण्याचा मार्गदर्शक सुरूवातीसाठी उत्तम आहे.
एक क्ल्यू बदलला की सगळं बदलतं
इथे जाणूनबुजून जवळजवळ पूर्ण झालेली कोडी आहे. एका डॉटने रिकामी सेल दर्शवली आहे.
5 3 4 | 6 . 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | . . 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9
यामध्ये ७८ क्ल्यूज आहेत आणि एकच उपाय (solution) आहे. वरच्या ओळीस (top row) ७ लागतो. मग चौथ्या ओळीत (fourth row) चौथा स्तंभ (column four) मध्ये ७ आणि पाचवा स्तंभ (column five) मध्ये ६ लागतो.
आता पहिली ओळ, चौथा स्तंभ येथील ६ पुसून टाका. चार सेल रिकामे होतील, आणि दोन मांडणी (arrangements) चालतील:
| Cell | Completion A | Completion B |
|---|---|---|
| Row 1, column 4 | 6 | 7 |
| Row 1, column 5 | 7 | 6 |
| Row 4, column 4 | 7 | 6 |
| Row 4, column 5 | 6 | 7 |
इतर सर्व संख्या तशाच राहतात. दोन्ही मांडणी प्रत्येक ओळ, स्तंभ, बॉक्स आणि उरलेल्या क्ल्यूजसाठी नियम पाळतात. ही चार सेल्स अशी रचना करतात की ६ आणि ७ परस्पर अदलाबदल (swap) करता येते आणि नियम मोडत नाहीत. आम्ही solution counts तपासले: पहिल्या कोडीत नेमकं एकच पूर्णता होती; आणि पुसल्यानंतर नेमकी दोन पूर्णता झाल्या.
एखादा क्ल्यू काढून टाकल्याने असा उपाय (solution) बाद होत नाही जो आधीच कार्यरत होता: तो उपाय अजूनही उरलेल्या सर्व क्ल्यूजना जुळतो. पण काढून टाकण्याने दुसरे उत्तर स्वीकारले जाऊ शकते. अगदी ७७ givens असलेली ही कोडीही ambiguous (गोंधळात टाकणारी, एकमेव नसलेली) आहे, त्यामुळे क्ल्यूजची संख्या जास्त असली तरी uniquenessची हमी देता येत नाही.
१७ ही किमान संख्या का?
Gary McGuire, Bastian Tugemann, आणि Gilles Civario यांनी सिद्ध केले की १६ givens असलेली कोणतीही क्लासिक ९×९ सुडोकू नेमके एकच उपाय देत नाही. त्यांच्या मूळ संशोधन पेपरमध्ये संपूर्ण (exhaustive) संगणकीय शोधाची माहिती आहे. १७-क्ल्यूज असलेल्या एकमेव-सोडवता येणाऱ्या कोड्या अस्तित्वात आहेत, म्हणून १७ ही किमान मर्यादा आहे.
याचा अर्थ असा नाही की १७ संख्यांची कोणतीही मांडणी वैध कोडीच बनेल. त्यांच्या स्थानांबरोबरच त्यांच्या मूल्यांनाही अर्थ असतो. हे निष्कर्ष क्लासिक सुडोकूबद्दल आहेत; variant मध्ये अतिरिक्त नियम असतील तर समस्या बदलते.
१६ ला बाद केल्याने १६ पेक्षा कमी संख्यादेखील का बाद होतात? समजा १६ पेक्षा कमी क्ल्यूज असलेल्या कोड्याला एकच उपाय असेल, तर त्या उपायातील योग्य क्ल्यूज तुम्ही जोडू शकता—ज्यामुळे अखेरीस ती कोडी १६ givens पर्यंत जाईल. असे जोडलेले क्ल्यूज त्या कोड्याचे एकमेव उत्तर जपतील, त्यामुळे वरचा निष्कर्ष विरोधी ठरेल.
मग तुम्ही कसं सिद्ध कराल की याहून लहान कोडी अस्तित्वात नाही?
एक १७-क्ल्यूजची कोडी सापडली की काय शक्य आहे ते कळते. १६ चालतच नाही हे सिद्ध करण्यासाठी मात्र प्रत्येक शक्यताच बाद करावी लागते.
संशोधकांनी पूर्ण झालेल्या ग्रिड्सचा क्रमवार (systematically) शोध घेतला आणि समतुल्य (equivalent) ग्रिड्सचा विचार केला. त्यांच्या पद्धतीत unavoidable sets (अटळ संच) वापरले: अशा सेल्सच्या गटांना जो पर्यायी पूर्णता रोखण्यासाठी क्ल्यू असणेच आवश्यक असते. त्यांनी hitting sets मोजण्यासाठी एक कार्यक्षम अल्गोरिदम विकसित केला—जे त्या गटांशी छेद (intersect) करतात—आणि uniqueness साठी उमेदवार क्ल्यू संच तपासले. पेपरमध्ये ही पद्धत स्पष्ट केली आहे.
वरची आयताकृती रचना (rectangle) या कल्पनेचे छोटे उदाहरण देते. चारही सेल्सना क्ल्यू देऊ नका आणि दोन्ही मांडणी टिकतात. त्यापैकी किमान एक सेल फिक्स (ठरवा) करा, आणि त्या विशिष्ट अदलाबदलवर (swap) अटकाव होतो. कमी क्ल्यूज असलेल्या कोड्यात, अनेक संभाव्य पर्याय एकाच वेळी रोखावे लागतात.
किमान क्ल्यूज म्हणजे कमाल कठीणपणा नाही
क्ल्यूजची संख्या उत्तर देते: “किती माहिती छापली आहे?” पण पुढची तुम्ही कोणती डिडक्शन (निष्कर्ष/चाचणी) लगेच पकडाल ते सांगत नाही. givens मोजल्याने पुढचा move (पाऊल) सरळ-साधा obvious single असेल की एखादा असा पॅटर्न असेल जो तुम्ही अजून शिकलातच नाही, हे कळत नाही.
आणखी एक उपयुक्त फरक आहे: minimum आणि minimal. minimum म्हणजे क्लासिक सुडोकूमध्ये शक्य असलेली सर्वात कमी क्ल्यू-गणती. minimal कोडी अशी जिथे कोणताही given काढला तरी uniqueness निघून जाते. एखादे कोडे minimal म्हणणे म्हणजे त्यात १७ क्ल्यूज आहेतच असे नाही.
तुमच्या पुढच्या खेळासाठी, प्रत्येक placement (सेलमध्ये संख्या ठेवणे) करण्यापूर्वी ते समजावून पाहा: “हा बॉक्समधला ४ ठेवता येणारा एकमेव सेल आहे.” अजून एखादा move समजावून सांगता आला नाही, तर candidates (संभाव्य संख्या) तपासा किंवा आमच्या सुडोकू सॉल्विंग गाईड मधून एखादी technique वापरून पाहा.
पुढच्या वेळेस तुम्हाला sparse Sudoku (कमी क्ल्यूज असलेली सुडोकू) दिसली, तर आधी क्ल्यूज मोजा—आणि मग प्रत्येक क्ल्यू इतका का महत्त्वाचा आहे, त्यामागचं कारण शोधा.
टिप्पण्या
तुमचे विचार मांडा, प्रश्न विचारा किंवा दुसऱ्या खेळाडूला मदत करा.
साइन-इन तपासत आहे…
टिप्पण्या लोड होत आहेत…