ఎందుకు 17 క్లూలు? మీరు ఇంకెంత చిన్నదిగా చేయలేని సుడోకు పజిల్
సుడోకులో నుండి ఒక సంఖ్యను తీసేస్తే అది మరింత కష్టమవ్వొచ్చు. తప్పు సంఖ్యను తీసేస్తే పజిల్కు ఉన్న ఏకైక సమాధానాన్ని పాడుచేయవచ్చు. పూర్తి గ్రిడ్ నుంచి ఖాళీ పేజీ వరకు మధ్య ఎక్కడో ఒక కఠిన పరిమితి ఉంది: 17 ప్రారంభ క్లూలు. సుడోకు ఎందుకు అక్కడే ఆగుతుంది?
దానికి సమాధానం ఒక సులభంగా గమనించకుండా పోయే ప్రశ్నతో మొదలవుతుంది: మీ పజిల్కు ఒకే ఒక పరిష్కారం ఉందా?
ఒక పూర్తైన గ్రిడ్, ఒకే సమాధానం
క్లాసిక్ 9×9 సుడోకులో ప్రతి వరుస, ప్రతి కాలమ్, ప్రతి 3×3 బాక్సులో 1 నుండి 9 వరకు అంకెలు ఒక్కొక్కసారి మాత్రమే ఉండాలి. ఇవే నికోలీ ప్రచురించిన ప్రామాణిక నియమాలు. గ్రిడ్లో ముందే ముద్రించిన సంఖ్యలను givens లేదా క్లూలు అంటారు.
పూర్తి చేసిన ఒక గ్రిడ్ ఆ నియమాలన్నింటినీ పాటించినా, అది ఇచ్చిన క్లూలకు మాత్రమే సరిపడే ఏకైక సమాధానం కావాల్సిన అవసరం లేదు. రెండు వేర్వేరు పూర్తి అమరికలు సరిపోతే, సెట్టర్ ఏదిని ఉద్దేశించాడో ఆటగాడు ఊహించి తెలుసుకోలేడు.
అందుకే ఏకైకత (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
ఇందులో 78 క్లూలు ఉన్నాయి, అలాగే ఒకే ఒక పరిష్కారం ఉంది. పై వరుసకు 7 కావాలి. నాలుగో వరుసకు అయితే నాలుగో కాలమ్లో 7 మరియు ఐదో కాలమ్లో 6 అవసరం.
ఇప్పుడు మొదటి వరుస, నాలుగో కాలమ్లో ఉన్న 6ని తీసేద్దాం. నాలుగు సెల్లు ఖాళీగా మారతాయి, రెండు అమరికలు పనిచేస్తాయి:
| 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 |
ఇతర అంకెలన్నీ అలాగే ఉంటాయి. రెండూ ప్రతి వరుస, కాలమ్, బాక్స్, మిగిలిన క్లూలన్నింటినీ పాటిస్తాయి. ఈ నాలుగు సెల్లు ఒక చతురస్రం (rectangle) లాగా ఏర్పడి, 6లు మరియు 7లను నియమం ఉల్లంఘించకుండా మార్చుకోవచ్చు. మేము సమాధానాల సంఖ్యను లెక్కించాం: మొదటి పజిల్కు కచ్చితంగా ఒకే పూర్తీకరణ ఉంది; తీసేశాక మాత్రం కచ్చితంగా రెండు మాత్రమే ఉన్నాయి.
ఒక క్లూను తీసేయడం, ఇప్పటికే పనిచేసిన సమాధానాన్ని చెల్లనిదిగా చేయదు: అది మిగిలిన క్లూలన్నింటినీ ఇంకా పాటిస్తుంది. కానీ అది చేసే పని ఇంకొక సమాధానాన్ని “అంగీకరించడం” (admit) మాత్రమే. 77 givens ఉన్నప్పటికీ ఈ పజిల్లో అస్పష్టత ఉంది—కాబట్టి క్లూ సంఖ్య ఎక్కువగా ఉండడం ఒక్కటే uniquenessని హామీ ఇవ్వదు.
17 కనీసమని ఎందుకు
Gary McGuire, Bastian Tugemann, మరియు Gilles Civario నిరూపించారు: 16 givens ఉన్న ఏ క్లాసిక్ 9×9 సుడోకుకు కూడా ఖచ్చితంగా ఒకే పరిష్కారం ఉండదు. వారి అసలు పరిశోధనా పత్రం పూర్తిగా కంప్యూటర్తో చేసిన విస్తృత శోధనను వివరిస్తుంది. 17-క్లూ పజిళ్లు ఏకైకంగా పరిష్కరించగలవిగా ఉంటాయి—అందుకే 17 కనీసం.
కానీ ఇది “17 సంఖ్యల ఏ అమరిక అయినా చెల్లుబాటు అయ్యే పజిల్ అవుతుంది” అని కాదు. వాటి స్థానాలు మరియు విలువలు ముఖ్యం. ఈ ఫలితం క్లాసిక్ సుడోకు గురించే; వేరియంట్లలో అదనపు నియమాలు ఉంటే సమస్య స్వభావం మారుతుంది.
16ని తీసివేసి 17 కంటే చిన్నదిని కూడా ఎందుకు తప్పుపెడుతుంది? చిన్న పజిల్కు ఒకే పరిష్కారం ఉంటే, ఆ పరిష్కారంలో ఉన్న సరైన క్లూలను జోడించి దానిని 16కి చేరుస్తూ ఉండొచ్చు. అలా జోడించిన క్లూలు దాని ఏకైక సమాధానాన్ని అలాగే ఉంచుతాయి—ఫలితానికి విరుద్ధంగా ఉంటుంది.
ఇంకా చిన్న పజిల్ ఉండదని మీరు ఎలా నిరూపిస్తారు?
ఒక 17-క్లూ పజిల్ కనుగొంటే “ఏం సాధ్యం” అన్నది తెలుస్తుంది. 16 పనిచేయదని నిరూపించాలంటే “అన్ని అవకాశాలనూ” తప్పించాలి.
పరిశోధకులు పూర్తయిన గ్రిడ్లను పద్ధతిగా వెతికారు, సమానమైన గ్రిడ్లను కూడా పరిగణలోకి తీసుకున్నారు. వారి పద్ధతి unavoidable sets (అనివార్య సమూహాలు)ని ఉపయోగించింది: ఏ ప్రత్యామ్నాయ పూర్తీకరణను అడ్డుకోవడానికి అయినా ఒక క్లూ ఉండాల్సిన సెల్ల సమూహాలు. ఆ సమూహాలను తాకే (intersect) _hitting sets_ని లెక్కించేందుకు వారు ఒక సమర్థవంతమైన ఆల్గోరిథంను రూపొందించారు; తర్వాత ఏ క్లూ-సమూహాలు uniqueness ఇస్తాయో అవి పరీక్షించారు. పేపర్లో పద్ధతిని వివరంగా చెప్పింది.
పైన చెప్పిన rectangle ఆలోచనకు ఒక చిన్న ఉదాహరణ ఇస్తుంది. ఆ నాలుగు సెల్లను క్లూలుగా ఉంచకుండా వదిలేస్తే, రెండు అమరికలూ బ్రతుకుతాయి. ఆ నాలుగు సెల్లలో కనీసం ఒక్కదానినైనా స్థిరంగా (fix) చేస్తే, ఆ నిర్దిష్ట swapని మీరు అడ్డుకుంటారు. తక్కువ క్లూలు ఉన్న పజిల్లో, ఎన్నో సాధ్యమైన ప్రత్యామ్నాయాలను ఒకేసారి అడ్డుకోవాల్సి వస్తుంది.
కనీస క్లూలు అంటే గరిష్ట కష్టత కాదు
క్లూ సంఖ్య “ఎంత సమాచారం ముద్రించారో” చెబుతుంది. కానీ మీరు తర్వాత చూసే డెడక్షన్ ఏది కనిపిస్తుందో అది చెప్పదు. ఎంత givens ఉన్నాయో లెక్కించడం, తదుపరి కదలిక స్పష్టమైన “ఒకే అంకె” (obvious single) అవుతుందా లేదా మీరు ఎప్పుడూ నేర్చుకోని ఒక ప్యాటర్నా అనే విషయాన్ని చెప్పదు.
ఇంకొక ఉపయోగకరమైన భేదం ఉంది: minimum (కనీసం) మరియు minimal (మినిమల్). కనీసం అంటే క్లాసిక్ సుడోకులో సాధ్యమైన అతి చిన్న క్లూ సంఖ్య. మినిమల్ పజిల్ అంటే—ఎక్కడా ఉన్న ఏ givenని తీసేసినా uniqueness పోతుంది. “ఒక పజిల్ మినిమల్” అనడం వల్ల దానికి 17 క్లూలు ఉన్నాయనే అర్థం కాదు.
మీ తదుపరి గేమ్లో, ప్రతి ప్లేస్మెంట్ని ముందుగా వివరించడానికి ప్రయత్నించండి: “ఈ బాక్స్లో 4 పెట్టగలిగే ఏకైక సెల్ ఇదే.” మీరు ఇంకా ఆ కదలికను వివరించలేకపోతే, candidatesని చెక్ చేయండి లేదా మా సుడోకు సాల్వింగ్ గైడ్లో ఉన్న ఒక టెక్నిక్ని ప్రయత్నించండి.
తదుపరి సారి మీరు sparse Sudoku (తక్కువ క్లూలు ఉన్న సుడోకు) చూస్తే—ముందుగా క్లూలు లెక్కించండి; తర్వాత ప్రతి క్లూ ఎందుకు అవసరమో చూడండి.
వ్యాఖ్యలు
మీ ఆలోచనను పంచుకోండి, ప్రశ్న అడగండి లేదా మరో ఆటగాడికి సహాయం చేయండి.
సైన్-ఇన్ను తనిఖీ చేస్తున్నాం…
వ్యాఖ్యలను లోడ్ చేస్తున్నాం…