বিশাল রুবিকস কিউবের জন্য 10⁴⁰-এর একটি ধ্রুবক নেমে এল 30.5-এ
সদ্য 50 বছরে পা দেওয়া রুবিকস কিউব সম্ভবত বিশ্বের সবচেয়ে পরিচিত ধাঁধা, আর এর একটি কেন্দ্রীয় প্রশ্ন বলা সহজ: সবচেয়ে খারাপ ক্ষেত্রে এটি মেলাতে কতগুলো চাল লাগে? ক্লাসিক 3×3×3 কিউবের জন্য উত্তরটি হুবহু জানা: 20টি চাল, একটি ফলাফল যা 2014 সালে প্রকাশ করেছিল একটি দল, যাতে ছিলেন এই নতুন গবেষণাপত্রের অন্যতম লেখক Tomas Rokicki।
বড় কিউবের ক্ষেত্রে, যার প্রতিটি কিনারা বরাবর n স্তর, হুবহু উত্তর নাগালের বাইরে — একটি নির্দিষ্ট n×n×n কিউবকে সর্বোত্তমভাবে মেলানো এমনকি NP-complete। তবে 2011 সালে Erik Demaine ও সহকর্মীরা দেখান সবচেয়ে খারাপ ক্ষেত্রটি কীভাবে বাড়ে: n² / lg n-এর সমানুপাতে, যেখানে lg হলো 2-ভিত্তিক লগারিদম। এটি প্রচলিত পদ্ধতিগুলোর চেয়ে একটি লগারিদমিক গুণক ভালো, যেগুলো মূলত এক এক করে টুকরো মেলায়।
অবিশ্বাস্য ধ্রুবকসহ একটি প্রমাণ
তবে একটা গোলমাল ছিল। 2011 সালের ফলাফল বৃদ্ধির হারের নিশ্চয়তা দিয়েছিল, তার সামনের সংখ্যাটির নয়। সেই অ্যালগরিদমটি খুঁটিয়ে হিসাব করে লেখকেরা দেখেন, এর ধ্রুবক প্রায় 1.01 × 10⁴⁰। দায়ী একটি কম্পিউটার-যাচাই, যা প্রমাণ করেছিল যে নির্দিষ্ট কিছু চাল 24টি টুকরোর একটি দলের প্রতিটি বিন্যাসে পৌঁছাতে পারে, কিন্তু কত দ্রুত তা বলেনি। সেই দৈর্ঘ্যের একমাত্র নিরাপদ সীমা ছিল সেই বিন্যাসগুলোর গোষ্ঠীর (group) আকার, প্রায় 3.1 × 10²³ ধাপ, আর সূত্রটি শেষ পর্যন্ত বিশাল সংখ্যা 24! (1 × 2 × … × 24, প্রায় 6.2 × 10²³) ব্যবহার করে দুই জায়গায়। বিপরীতে, নিম্নসীমার — প্রায় প্রতিটি এলোমেলো কিউবের যতগুলো চাল লাগে — ধ্রুবক সাদামাটা, প্রায় 12.88। তাই এই সম্প্রদায়ের অনেকে বিশ্বাস করতেন, যুক্তিসংগত আকারের জন্য এমন অ্যালগরিদম কখনো ব্যবহারযোগ্য হতে পারবে না।
MIT, TU Munich আর পালো অল্টো থেকে Jeremy Mrzyglocki, Tomas Rokicki, Maxine Perroni-Scharf ও Erik Demaine এবার সেই ধ্রুবকটিকে স্পষ্ট ও ছোট করেছেন।
কিউবের টুকরোর জন্য বাছাই-নেটওয়ার্ক
বড় কিউবে কেন্দ্রের টুকরোগুলোই প্রধান: তাদের সংখ্যা বাড়ে n²-এর মতো, আর কোণ ও কিনারার টুকরোগুলো যোগ করে কেবল n-এর সমানুপাতিক পদ। কেন্দ্রের টুকরোগুলো 24টির এমন পরিবারে ভাগ হয়, যারা কেবল নিজেদের মধ্যেই জায়গা বদলাতে পারে। মূল হাতিয়ার হলো কমিউটেটর (commutator), A B A′ B′ আকারের একটি ক্রম, যা প্রায় সবকিছু জায়গামতো রেখে কেবল একটি পরিবারের তিনটি টুকরোর বিন্যাস বদলায়। দলটি ব্যবহারযোগ্য 4,000টি তিন-টুকরো অদলবদলের সবগুলোর জন্য চালের ক্রম খুঁজে পেয়েছে, প্রতিটি সর্বোচ্চ 12 চাল দীর্ঘ।
দুটি ধারণা গণনাটিকে নামিয়ে আনে। প্রথমত, একই কমিউটেটর একসঙ্গে অনেক পরিবারে প্রয়োগ করা যায়, সারি ও কলামের পুরো দল জুড়ে। দ্বিতীয়ত, প্রতিটি পরিবারকে আলাদাভাবে মেলানোর বদলে, প্রতিটি পরিবার অদলবদলের একটিই স্থির সার্বজনীন ক্রম (universal sequence) অনুসরণ করে, যে অদলবদলগুলো তার দরকার নেই সেগুলো স্রেফ বাদ দিয়ে। একটি লেমা সবকিছুকে বেঁধে রাখে: L ধাপের একটি সার্বজনীন ক্রম দেয় L/2-এর একটি মুখ্য ধ্রুবক (leading constant)।
সেই ক্রম ছোট করতে হাতিয়ার ধার নেওয়া হয় কম্পিউটার বিজ্ঞানের বাছাই-নেটওয়ার্ক (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 সংস্করণের জন্য, যা প্রস্তুতি-অনুশীলন (warm-up) হিসেবে ব্যবহৃত, ধ্রুবকটি 12 বা 18 থেকে নেমে আসে 1.5-এ।

প্রতি পাশে 256 স্তরের একটি কিউব মেলানোর সমান ব্যবধানে নেওয়া আটটি ফ্রেম: এলোমেলো মুখগুলো নিরেট রঙে পরিণত হয়। — চিত্র 1.1, Mrzyglocki et al. (2026), arXiv:2611.11018.
অ্যালগরিদমটি টুকরোর সংখ্যার সমানুপাতিক সময়ে চলে, আর লেখকেরা একটি ওপেন-সোর্স সমাধানকারী দিয়েছেন, সঙ্গে এমন স্ক্রিপ্ট যা এটি যে প্রতিটি নেটওয়ার্কের ওপর নির্ভর করে তা পূর্ণাঙ্গভাবে যাচাই করে। তাঁদের নিজস্ব তুলনায় এটি প্রায় n = 840 থেকে বিদ্যমান সমাধানকারীগুলোর চেয়ে এগিয়ে; তাঁরা প্রতি পাশে 256 ও 65,536 স্তরের কিউব মেলানোর দৃশ্য তৈরি (render) করেছেন।
2.37 একটি অসীমতটীয় (asymptotic) বক্তব্য: সূত্রের ছোট পদগুলো নির্দিষ্ট করা হয়নি, তাই এটি কোনো নির্দিষ্ট কিউবের জন্য হুবহু চাল-সংখ্যা দেয় না। লেখকদের মতে, ভবিষ্যৎ উন্নতি আসতে পারে টুকরোগুলোকে বাছাই-নেটওয়ার্কে দলবদ্ধ করার অন্য উপায় থেকে আর আরও ভালো তিন-টুকরো অদলবদল থেকে — আর একই কৌশল-যন্ত্র অন্যান্য বিশাল ধাঁধা, কিংবা চার ও পাঁচ মাত্রার হাইপারকিউব সামলাতে পারে।
