books solvability
If you do not find what you're looking for, you can use more accurate words.
قابلية الحل (Info)
الخوارزمية
توجد الأحجية أيضاً في أحجام أخرى أصغر، بحيث يكون حجم الإطار 3×3، فيكون اللغز هو أحجية 8. يمكن أن يكون حجم الإطار أكبر أو أصغر من ذلك، لذا فإنها تعرف أيضاً بأحجية ڽ، وتعتبر مشكلة كلاسيكية للخوارزميات النموذجية التي تنطوي على الاستدلال. عادة ما يستخدم الاستدلال لحل هذه المشكلة بعد عدد من القطع التي في غير محلها والعثور على مجموع المسافات بين كل قطعة وموقفها في تكوين الهدف بهندسة سيارة الأجرة.
جونسون وستوري
في 1879 استخدم جونسون ستوري حجة التكافؤ لإظهار أن نصف الحركات الأولى مستحيل أن تحل الأحجية، بغض النظر عن كيف تتم التحركات يتم ذلك من خلال النظر إلى وظيفة تكوين القطع تحت أي خطوة صالحة، ومن ثم استخدام هذا لتقسيم الفراغ المتكون من جميع القطع المرقمة إلى فئتين متكافئتين من القطع، وهما ممكنة الوصول وغير ممكنة الوصول. الثابت هو تكافؤ التبديل بين جميع المساحات ال16 بالإضافة إلى تعادل مسافة سيارة الأجرة للمربع الفارغ من الزاوية اليمنى السفلى، وهذا ثابت لأن كل خطوة يتغير كل من تكافؤ التبديل وتكافؤ مسافة سيارة الأجرة، وبالتالي فإنه إذا كانت المساحة الفارغة في الزاوية اليمنى السفلى فإن الأحجية كون قابلة للحل إذا وفقط إذا كان التبديل بين القطع المتبقية متساوٍ. جونسون وستوري أظهر أيضاً أن الشئ وعكسه يحصل على كل اللوحات التي من الحجم م×م حيث م≥2.
آركر
في 1999 وضع آركر طريقة ترتبط بطريقة جونسون وستوري، ولكنه أعطى دليلاً آخر يعتمد على تحديد طبقات التكافؤ عبر المسار الهاملتونياني.
ويلسون
في 1974 درس ويلسون تماثلية أحجية 15 على الرسوم البيانية الاعتباطية محدودة الاتصال غير القابلة للفصل، وأوضح أنه باستثناء المضلعات والقمم السبعة للرسوم البيانية، فمن الممكن الحصول على جميع التباديل إلا إذا كان الرسم البياني ثنائياً، وفي هذه الحالة يمكن الحصول على التباديل المتساوية، أما إذا كان الرسم البياني عبارة عن شكل سداسي منتظم مع رسم قطر واحد وإضافة نقطة في المركز، فإنه يمكن الحصول على 1/6 التبديلات فقط.
مسائل NP صعبة
في الإصدارات الأكبر لأحجية 15، فإن إيجاد الحل سهل، لكن الصعب هو إيجاد الحل الأسرع، ويعد مسائل NP صعبة. بالنسبة لأحجية 15، فإن أطوال الحلول المثلى تتراوح بين 0-80 حركة فردية أو 43 حركة متعددة.
