رایانش و هوش مصنوعیپیش‌چاپنظریه۴ دقیقه مطالعه

ثابتی 10⁴⁰ که برای مکعب‌های روبیک غول‌پیکر به 30.5 کاهش یافت

مکعب روبیک، که به‌تازگی 50 ساله شده، شاید شناخته‌شده‌ترین پازل جهان باشد، و یکی از پرسش‌های محوری‌اش را ساده می‌توان بیان کرد: در بدترین حالت، حل آن چند حرکت لازم دارد؟ برای مکعب کلاسیک 3×3×3، پاسخ دقیقاً معلوم است: 20 حرکت، نتیجه‌ای که در سال 2014 تیمی منتشر کرد که تامس روکیکی (Tomas Rokicki)، یکی از نویسندگان این مقالهٔ تازه، عضو آن بود.

برای مکعب‌های بزرگ‌تر، با n لایه در امتداد هر یال، پاسخ دقیق دست‌نیافتنی است — حل بهینهٔ یک مکعب n×n×n مشخص حتی NP-کامل است. اما در سال 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 دارد. از این رو بسیاری در این جامعه باور داشتند که چنین الگوریتمی هرگز برای اندازه‌های معقول کاربردی نخواهد بود.

جرمی مژیگلوکی (Jeremy Mrzyglocki)، تامس روکیکی، ماکسین پرونی-شارف (Maxine Perroni-Scharf) و اریک دمین، از MIT، دانشگاه فنی مونیخ و پالو آلتو (Palo Alto)، اکنون این ثابت را صریح و کوچک کرده‌اند.

شبکه‌های مرتب‌سازی برای قطعه‌های مکعب

روی یک مکعب بزرگ، قطعه‌های مرکزی غالب‌اند: تعدادشان به نسبت n² رشد می‌کند، در حالی که گوشه‌ها و یال‌ها تنها جمله‌هایی متناسب با n می‌افزایند. قطعه‌های مرکزی به خانواده‌هایی 24تایی تقسیم می‌شوند که تنها می‌توانند میان خودشان جابه‌جا شوند. ابزار پایه جابه‌جاگر (commutator) است، دنباله‌ای به شکل A B A′ B′ که تقریباً همه‌چیز را سر جایش باقی می‌گذارد و تنها سه قطعه از یک خانواده را جایگشت می‌دهد. تیم برای همهٔ 4,000 جابه‌جایی سه‌قطعه‌ایِ قابل استفاده، دنباله‌هایی از حرکت‌ها یافت که هر کدام حداکثر 12 حرکت طول دارند.

دو ایده شمار حرکت‌ها را پایین می‌آورد. نخست، همان جابه‌جاگر را می‌توان هم‌زمان روی خانواده‌های بسیاری، در سراسر گروه‌های کاملی از سطرها و ستون‌ها، به کار برد. دوم، به جای حل هر خانواده به‌تنهایی، همهٔ خانواده‌ها از یک دنبالهٔ سراسری (universal sequence) ثابت از جابه‌جایی‌ها پیروی می‌کنند و صرفاً آن‌هایی را که لازم ندارند نادیده می‌گیرند. یک لم همه‌چیز را به هم پیوند می‌دهد: یک دنبالهٔ سراسری با 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 و همکاران (2026)، arXiv:2611.11018.

الگوریتم در زمانی متناسب با تعداد قطعه‌ها اجرا می‌شود، و نویسندگان یک حل‌کنندهٔ متن‌باز ارائه می‌دهند، همراه با اسکریپت‌هایی که هر شبکه‌ای را که حل‌کننده بر آن تکیه دارد به‌طور کامل بررسی می‌کنند. مقایسهٔ خودشان نشان می‌دهد که از حدود n = 840 به بعد از حل‌کننده‌های موجود جلوتر است؛ آن‌ها حل مکعب‌هایی با 256 و 65,536 لایه در هر ضلع را به تصویر درآورده‌اند.

عدد 2.37 گزاره‌ای مجانبی است: جمله‌های کوچک‌تر فرمول دقیقاً تعیین نشده‌اند، پس برای یک مکعب مشخص شمارش دقیقی به دست نمی‌دهد. به گفتهٔ نویسندگان، پیشرفت‌های آینده ممکن است از راه‌های دیگرِ گروه‌بندی قطعه‌ها در شبکه‌های مرتب‌سازی و از جابه‌جایی‌های سه‌قطعه‌ایِ بهتر به دست آید — و همین سازوکار می‌تواند به سراغ پازل‌های غول‌پیکر دیگر، یا ابرمکعب‌های چهار و پنج‌بعدی برود.