أحجية 15

مسائل NP صعبة

المصادر

وفي هذا الصدد، في الإصدارات الأكبر لأحجية 15، فإن إيجاد الحل سهل، لكن الصعب هو إيجاد الحل الأسرع، ويعد مسائل NP صعبة. بالنسبة لأحجية 15، فإن أطوال الحلول المثلى تتراوح بين 0-80 حركة فردية أو 43 حركة متعددة.

انظر كذلك

ويلسون

وفي هذا السياق، في 1974 درس ويلسون تماثلية أحجية 15 على الرسوم البيانية الاعتباطية محدودة الاتصال غير القابلة للفصل، وأوضح أنه باستثناء المضلعات والقمم السبعة للرسوم البيانية، فمن الممكن الحصول على جميع التباديل إلا إذا كان الرسم البياني ثنائياً، وفي هذه الحالة يمكن الحصول على التباديل المتساوية، أما إذا كان الرسم البياني عبارة عن شكل سداسي منتظم مع رسم قطر واحد وإضافة نقطة في المركز، فإنه يمكن الحصول على 1/6 التبديلات فقط.

الخوارزمية

كذلك، توجد الأحجية كذلك في أحجام أخرى أصغر، بحيث يكون حجم الإطار 3×3، فيكون اللغز هو أحجية 8. يمكن أن يكون حجم الإطار أكبر أو أصغر من ذلك، لذا فإنها تعرف كذلك بأحجية ڽ، وتعتبر مشكلة كلاسيكية للخوارزميات النموذجية التي تنطوي على الاستدلال. عادة ما يستعمل الاستدلال لحل هذه المشكلة بعد عدد من القطع التي في غير محلها والعثور على مجموع المسافات بين كل قطعة وموقفها في تكوين الهدف بهندسة سيارة الأجرة.

جونسون وستوري

وفي هذا السياق، جونسون وستوري أظهر كذلك أن الشئ وعكسه يحصل على كل اللوحات التي من الحجم م×م حيث م≥2.

وفي السياق ذاته، في 1879 استعمل جونسون ستوري حجة التكافؤ لإظهار أن نصف الحركات الأولى مستحيل أن تحل الأحجية، بغض النظر عن كيف تتم التحركات يتم ذلك من خلال النظر إلى وظيفة تكوين القطع تحت أي خطوة صالحة، ومن ثم استخدام هذا لتقسيم الفراغ المتكون من جميع القطع المرقمة إلى فئتين متكافئتين من القطع، وهما ممكنة الوصول وغير ممكنة الوصول.

علاوةً على ذلك، الثابت هو تكافؤ التبديل بين جميع المساحات ال16 إلى جانب تعادل مسافة سيارة الأجرة للمربع الفارغ من الزاوية اليمنى السفلى، وهذا ثابت لأن كل خطوة يتغير كل من تكافؤ التبديل وتكافؤ مسافة سيارة الأجرة، وبالتالي فإنه إذا كانت المساحة الفارغة في الزاوية اليمنى السفلى فإن الأحجية كون قابلة للحل إذا وفقط إذا كان التبديل بين القطع المتبقية متساوٍ.

آركر

علاوةً على ذلك، في 1999 وضع آركر طريقة ترتبط بطريقة جونسون وستوري، ولكنه أعطى دليلاً آخر يعتمد على تحديد طبقات التكافؤ عبر المسار الهاملتونياني.

التاريخ

وفي السياق ذاته، اخترعت أحجية 15 من قبل نويس بالمر شابمان، وكان مدير مكتب البريد في كاناسوتا، نيويورك أوائل عام 1874، وكانت سريعة الانتشار، حيث نقلت إلى سيراكيوز 15 نسخة منها على يد ابنه فرانك، ومنها إلى وتش هيل، ثم إلى هارتفورد بكونيكتيكوت، حيث بدأ طلاب المدرسة الأمريكية للصم تصنيع الأحجية، وفي ديسمبر 1879 بدأ بيعها محلياً في بوسطن بماساشوستس، وبدأ نجار يدعى ماتياس رايس صناعتها، وأقنع رجل أعمال يدعى يانكي نوشنز ببيعها تحت اسم «أحجية الجوهرة» في أواخر يناير 1880. انتشرت اللعبة في الولايات المتحدة في فبراير، وفي كندا في مارس، وفي أوروبا في أبريل، ولم تدخل أحجية 15 اليابان إلا عام 1889.

قابلية الحل

ومن جهة أخرى، قال سام لويد في 1891 أنه هو من اخترع أحجية 15، لكنه لم يتمكن من الوصول لشعبية اللعبة الأصلية. لكنه لاحقًا تمكن من لفت أنظار الناس حيث رصد مكافأة 1000 $ لمن يتمكن من حل أحجية 15 التي اخترعها، حيث بدل بين قطعتي 14 و15، لكن ذلك كان مستحيلاً، فلم يستطع أحد حلها.