الحوسبة والذكاء الاصطناعينسخة أوليةنظريةمدة القراءة: 3 د

ثابت قدره 10⁴⁰ يُخفَّض إلى 30.5 لمكعبات روبيك العملاقة

مكعب روبيك، الذي بلغ لتوّه 50 عامًا، ربما يكون أشهر لغز في العالم، وأحد أسئلته المحورية سهل الصياغة: في أسوأ الحالات، كم حركة يلزم لحله؟ بالنسبة إلى المكعب الكلاسيكي 3×3×3، الجواب معروف بدقة: 20 حركة، وهي نتيجة نشرها عام 2014 فريق ضمّ توماس روكيكي (Tomas Rokicki)، أحد مؤلفي هذه الورقة الجديدة.

أما المكعبات الأكبر، ذات n طبقة على امتداد كل حافة، فالجواب الدقيق فيها بعيد المنال — بل إن حل مكعب n×n×n معيّن على النحو الأمثل مسألة NP-كاملة (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. لذا اعتقد كثيرون في هذا الوسط أن خوارزمية كهذه لا يمكن أن تكون عملية أبدًا لأحجام معقولة.

وقد جعل الآن جيريمي مرجيغلوكي (Jeremy Mrzyglocki) وتوماس روكيكي (Tomas Rokicki) ومكسين بيروني-شارف (Maxine Perroni-Scharf) وإريك ديمين (Erik Demaine)، من MIT وTU Munich وبالو ألتو، هذا الثابت صريحًا وصغيرًا.

شبكات فرز لقطع المكعب

على المكعب الكبير، تهيمن القطع المركزية: فعددها ينمو بما يتناسب مع 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 وآخرون (2026)، arXiv:2611.11018.

تعمل الخوارزمية في زمن متناسب مع عدد القطع، ويوفر المؤلفون حلّالًا مفتوح المصدر، مع نصوص برمجية تتحقق على نحو شامل من كل شبكة يعتمد عليها. وتجد مقارنتهم الخاصة أنه يتقدم على الحلّالات الموجودة ابتداءً من نحو n = 840؛ وقد أنتجوا عروضًا مصوّرة لعمليات حل مكعبات ذات 256 و65,536 طبقة في كل جانب.

إن الرقم 2.37 عبارة مقارِبة (asymptotic): فالحدود الأصغر في الصيغة غير محددة بدقة، لذا لا تعطي عددًا دقيقًا لمكعب بعينه. ويقترح المؤلفون أن المكاسب المستقبلية قد تأتي من طرائق أخرى لتجميع القطع في شبكات الفرز ومن عمليات تبديل ثلاثية أفضل — وأن الأدوات نفسها قد تتصدى لألغاز عملاقة أخرى، أو لمكعبات فائقة (hypercubes) رباعية وخماسية الأبعاد.