కంప్యూటింగ్ & ఏఐప్రీప్రింట్సిద్ధాంతంచదవడానికి 3 నిమిషాలు

భారీ రూబిక్స్ క్యూబ్‌లకు 10⁴⁰ స్థిరాంకం 30.5కు తగ్గింది

ఇప్పుడే 50 ఏళ్లు నిండిన రూబిక్స్ క్యూబ్ బహుశా ప్రపంచంలో అత్యంత ప్రసిద్ధ పజిల్, దాని కేంద్ర ప్రశ్నలలో ఒకటి చెప్పడానికి సులభం: అత్యంత చెడ్డ సందర్భంలో, దాన్ని పరిష్కరించడానికి ఎన్ని కదలికలు పడతాయి? సంప్రదాయ 3×3×3 క్యూబ్‌కు, సమాధానం కచ్చితంగా తెలుసు: 20 కదలికలు, ఈ కొత్త పత్ర రచయితలలో ఒకరైన టోమాస్ రోకికి (Tomas Rokicki) సభ్యులుగా ఉన్న ఒక బృందం 2014లో ప్రచురించిన ఫలితం ఇది.

పెద్ద క్యూబ్‌లకు, అంటే ప్రతి అంచు వెంబడి n పొరలు ఉన్నవాటికి, కచ్చితమైన సమాధానం అందుబాటులో లేదు — ఇచ్చిన ఒక n×n×n క్యూబ్‌ను అనుకూలతమంగా (optimally) పరిష్కరించడం NP-complete కూడా. కానీ 2011లో, ఎరిక్ డెమెయిన్ (Erik Demaine), సహచరులు అత్యంత చెడ్డ సందర్భం ఎలా పెరుగుతుందో చూపించారు: n² / lg nకు అనులోమానుపాతంలో, ఇక్కడ lg అనేది 2 ఆధారంగా గల లాగరిథమ్. ఇది ముక్కలను ప్రాథమికంగా ఒక్కొక్కటిగా పరిష్కరించే ప్రామాణిక పద్ధతుల కంటే ఒక లాగరిథమిక్ కారకం మేర మెరుగైనది.

అసంబద్ధమైన స్థిరాంకంతో ఒక నిరూపణ

ఒక చిక్కు ఉంది. 2011 ఫలితం పెరుగుదల రేటుకు హామీ ఇచ్చింది, దాని ముందున్న సంఖ్యకు కాదు. ఆ అల్గారిథమ్‌ను వివరంగా పరిశీలిస్తే, దాని స్థిరాంకం సుమారు 1.01 × 10⁴⁰ అని రచయితలు కనుగొన్నారు. దోషి ఒక కంప్యూటర్ తనిఖీ: కొన్ని కదలికలు 24 ముక్కల సమూహం యొక్క ప్రతి అమరికను చేరుకోగలవని అది నిరూపించింది, కానీ ఎంత త్వరగా అనేది చెప్పలేదు. ఆ పొడవుకు సురక్షితమైన ఏకైక హద్దు ఆ అమరికల సమూహం యొక్క పరిమాణం, సుమారు 3.1 × 10²³ దశలు, చివరకు సూత్రం 24! (1 × 2 × … × 24, సుమారు 6.2 × 10²³) అనే భారీ సంఖ్యను రెండు చోట్ల ఉపయోగిస్తుంది. దీనికి భిన్నంగా, దిగువ హద్దు — దాదాపు ప్రతి కలగాపులగమైన క్యూబ్‌కూ అవసరమయ్యే కదలికల సంఖ్య — సుమారు 12.88 అనే నిరాడంబరమైన స్థిరాంకాన్ని కలిగి ఉంది. అందుకే ఇలాంటి అల్గారిథమ్ సహేతుకమైన పరిమాణాలకు ఎప్పటికీ ఆచరణీయం కాదని ఈ సముదాయంలో చాలామంది నమ్మారు.

MIT, TU Munich, పాలో ఆల్టోలకు చెందిన జెరెమీ మ్ర్జిగ్లోకి (Jeremy Mrzyglocki), టోమాస్ రోకికి, మాక్సిన్ పెరోనీ-షార్ఫ్ (Maxine Perroni-Scharf), ఎరిక్ డెమెయిన్ ఇప్పుడు ఆ స్థిరాంకాన్ని స్పష్టంగా, చిన్నదిగా చేశారు.

క్యూబ్ ముక్కల కోసం సార్టింగ్ నెట్‌వర్క్‌లు

ఒక పెద్ద క్యూబ్‌పై, మధ్య ముక్కలదే (centre pieces) ఆధిపత్యం: వాటి సంఖ్య n²గా పెరుగుతుంది, మూలలు, అంచులు మాత్రం n కి అనులోమానుపాతంలో ఉండే పదాలను మాత్రమే జోడిస్తాయి. మధ్య ముక్కలు 24 చొప్పున కుటుంబాలుగా విభజించబడతాయి, అవి తమలో తాము మాత్రమే స్థానాలు మార్చుకోగలవు. ప్రాథమిక సాధనం కమ్యుటేటర్ (commutator), A B A′ B′ రూపంలో ఉండే ఒక క్రమం, ఇది దాదాపు అన్నింటినీ యథాస్థానంలో ఉంచి, ఒక కుటుంబంలోని కేవలం మూడు ముక్కలను మాత్రమే స్థానభ్రంశం చేస్తుంది. ఉపయోగించగల మొత్తం 4,000 మూడు-ముక్కల మార్పిడులకు బృందం కదలికల క్రమాలను కనుగొంది, ప్రతిదీ గరిష్ఠంగా 12 కదలికల పొడవు.

రెండు ఆలోచనలు లెక్కను తగ్గిస్తాయి. మొదటిది, ఒకే కమ్యుటేటర్‌ను అనేక కుటుంబాలకు ఒకేసారి, వరుసలు, నిలువు వరుసల మొత్తం సమూహాల అంతటా వర్తింపజేయవచ్చు. రెండవది, ప్రతి కుటుంబాన్ని విడిగా పరిష్కరించడానికి బదులు, ప్రతి కుటుంబం మార్పిడుల యొక్క ఒకే స్థిరమైన సార్వత్రిక క్రమాన్ని (universal sequence) అనుసరిస్తుంది, తనకు అవసరం లేనివాటిని కేవలం దాటవేస్తూ. ఒక లెమ్మా (lemma) అన్నింటినీ కలుపుతుంది: L దశల సార్వత్రిక క్రమం L/2 అనే ప్రధాన స్థిరాంకాన్ని ఇస్తుంది.

ఆ క్రమాన్ని కుదించడానికి కంప్యూటర్ సైన్స్ నుంచి సార్టింగ్ నెట్‌వర్క్‌ల (sorting networks) సాధనాలను అరువు తీసుకుంటారు; ఇవి ఏ ఇన్‌పుట్‌నైనా క్రమబద్ధీకరించే స్థిరమైన పోలికల నమూనాలు. ఆరు ఇన్‌పుట్‌ల అనుకూలతమ సార్టింగ్ నెట్‌వర్క్ 96 దశలను ఇస్తుంది, తద్వారా 48 అనే స్థిరాంకం. 24 స్థానాలను 12 చొప్పున, ఆ తర్వాత 4 చొప్పున సమూహాలుగా విభజించే, కంప్యూటర్ శోధన ద్వారా కనుగొన్న నెట్‌వర్క్‌లు దాన్ని 72 దశలకు (36) తెస్తాయి. చివరగా, ఒకేసారి మూడు కంటే ఎక్కువ ముక్కలను కలగలిపే కదలికలను అనుమతించి, స్థానాలను వేరే విధంగా విభజిస్తే అది 61 దశలకు చేరుతుంది.

ముప్పై పాయింట్ ఐదు

సిద్ధాంతం: ఏ n×n×n క్యూబ్‌నైనా గరిష్ఠంగా 30.5 n²/lg n కదలికలలో పరిష్కరించవచ్చు, అదనంగా పెద్ద n కోసం నగణ్యమయ్యే పదాలు. స్థిరాంకం 3.30 × 10³⁸ కంటే ఎక్కువ రెట్లు మెరుగుపడుతుంది, దిగువ హద్దుకు 2.37 రెట్ల పరిధిలో ఉంటుంది (30.5 / 12.88). సన్నాహకంగా ఉపయోగించిన చదునైన n×n×1 రూపానికి, స్థిరాంకం 12 లేదా 18 నుంచి 1.5కు పడిపోతుంది.

256 పొరల క్యూబ్ పరిష్కరించబడుతున్న ఎనిమిది చిత్రాలు, విప్పిన ముఖాలుగా, చిన్న క్యూబ్‌లుగా, కలగాపులగమైన గందరగోళం నుంచి ఏకవర్ణ రంగుల వరకు.

ప్రతి వైపున 256 పొరలు గల ఒక క్యూబ్ పరిష్కారం నుంచి సమాన వ్యవధుల్లో తీసిన ఎనిమిది చిత్రాలు: కలగాపులగమైన ముఖాలు ఏకవర్ణ రంగులుగా మారతాయి. — చిత్రం 1.1, Mrzyglocki et al. (2026), arXiv:2611.11018.

అల్గారిథమ్ ముక్కల సంఖ్యకు అనులోమానుపాతంలో ఉండే సమయంలో నడుస్తుంది, రచయితలు ఒక ఓపెన్-సోర్స్ సాధకాన్ని అందిస్తున్నారు, అది ఆధారపడే ప్రతి నెట్‌వర్క్‌ను సమగ్రంగా తనిఖీ చేసే స్క్రిప్ట్‌లతో సహా. వారి సొంత పోలిక ప్రకారం, సుమారు n = 840 నుంచి ఇది ఇప్పటికే ఉన్న సాధకాల కంటే ముందుంది; ప్రతి వైపున 256, 65,536 పొరలు గల క్యూబ్‌ల పరిష్కారాలను వారు దృశ్యరూపంలో (rendered) రూపొందించారు.

2.37 అనేది ఒక అనంతస్పర్శీయ (asymptotic) ప్రకటన: సూత్రంలోని చిన్న పదాలు నిర్ధారించబడలేదు, కాబట్టి అది ఒక నిర్దిష్ట క్యూబ్‌కు కచ్చితమైన లెక్కను ఇవ్వదు. భవిష్యత్ మెరుగుదలలు ముక్కలను సార్టింగ్ నెట్‌వర్క్‌లుగా సమూహపరిచే ఇతర మార్గాల నుంచి, మెరుగైన మూడు-ముక్కల మార్పిడుల నుంచి రావచ్చని రచయితలు సూచిస్తున్నారు — అదే యంత్రాంగం ఇతర భారీ పజిల్‌లను, లేదా నాలుగు, ఐదు-మితీయ హైపర్‌క్యూబ్‌లను కూడా ఎదుర్కోగలదు.