أحجية 15

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

 التاريخ 

تصغير|يسار|أحجية 15 الغير قابلة للحل لسام لويد.

اخترعت أحجية 15 من قبل نويس بالمر شابمان،The 15 Puzzle, by Jerry Slocum & Dic Sonneveld, 2006. ISBN 1-890980-15-3 وكان مدير مكتب البريد في كاناسوتا، نيويورك أوائل عام 1874، وكانت سريعة الانتشار، حيث نقلت إلى سيراكيوز 15 نسخة منها على يد ابنه فرانك، ومنها إلى وتش هيل، ثم إلى هارتفورد بكونيكتيكوت، حيث بدأ طلاب المدرسة الأمريكية للصم تصنيع الأحجية، وفي ديسمبر 1879 بدأ بيعها محلياً في بوسطن بماساشوستس، وبدأ نجار يدعى ماتياس رايس صناعتها، وأقنع رجل أعمال يدعى يانكي نوشنز ببيعها تحت اسم «أحجية الجوهرة» في أواخر يناير 1880. انتشرت اللعبة في الولايات المتحدة في فبراير، وفي كندا في مارس، وفي أوروبا في أبريل، ولم تدخل أحجية 15 اليابان إلا عام 1889.

قال سام لويد في 1891 أنه هو من اخترع أحجية 15، لكنه لم يتمكن من الوصول لشعبية اللعبة الأصلية.Barry R. Clarke, Puzzles for Pleasure, pp.10-12, Cambridge University Press, 1994 ISBN 0-521-46634-2. لكنه بعد ذلك تمكن من لفت أنظار الناس حيث رصد مكافأة 1000 $ لمن يتمكن من حل أحجية 15 التي اخترعها، حيث بدل بين قطعتي 14 و15، لكن ذلك كان مستحيلاً، فلم يستطع أحد حلها.

 قابلية الحل 

 الخوارزمية 

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

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

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

 آركر 

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

 ويلسون 

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

 مسائل NP صعبة 

في الإصدارات الأكبر لأحجية 15، فإن إيجاد الحل سهل، لكن الصعب هو إيجاد الحل الأسرع، ويعد مسائل NP صعبة. بالنسبة لأحجية 15، فإن أطوال الحلول المثلى تتراوح بين 0-80 حركة فرديةA. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications, Annals of Operations Research 90 (1999), pp. 45–63.  أو 43 حركة متعددة."The Fifteen Puzzle can be solved in 43 "moves"". Domain of the Cube Forum 

 المصادر 

 انظر أيضاً 
 مكعب روبيك

تصنيف:أحجيات منطقية
تصنيف:ألغاز ميكانيكية
تصنيف:استحداثات 1874
تصنيف:اختراعات أمريكية
تصنيف:الرياضات في القرن 19
تصنيف:تبديلات (توافيقيات)
تصنيف:مسائل كثيرة حدود غير قطعية كاملة