أحجية 15 هي أحجية انزلاقية تتكون من إطار مساحته 4×4 به قطع خشبية أو حجرية مرتبة ترتيباً عشوائياً مع مساحة فارغة لقطعة واحدة. توجد الأحجية أيضاً في أحجام أخرى أصغر، بحيث يكون حجم الإطار 3×3، فيكون اللغز هو أحجية 8. هدف اللغز هو تنظيم القطع وإعادة ترتيبها بشكل صحيح بتحريكك القطع بانزلاقها بواسطة المساحة الفارغة.
التاريخ
اخترعت أحجية 15 من قبل نويس بالمر شابمان،[1] وكان مدير مكتب البريد في كاناسوتا، نيويورك أوائل عام 1874، وكانت سريعة الانتشار، حيث نقلت إلى سيراكيوز 15 نسخة منها على يد ابنه فرانك، ومنها إلى وتش هيل، ثم إلى هارتفورد بكونيكتيكوت، حيث بدأ طلاب المدرسة الأمريكية للصم تصنيع الأحجية، وفي ديسمبر 1879 بدأ بيعها محلياً في بوسطن بماساشوستس، وبدأ نجار يدعى ماتياس رايس صناعتها، وأقنع رجل أعمال يدعى يانكي نوشنز ببيعها تحت اسم "أحجية الجوهرة" في أواخر يناير 1880.[1] انتشرت اللعبة في الولايات المتحدة في فبراير، وفي كندا في مارس، وفي أوروبا في أبريل، ولم تدخل أحجية 15 اليابان إلا عام 1889.
قال سام لويد في 1891 أنه هو من اخترع أحجية 15، لكنه لم يتمكن من الوصول لشعبية اللعبة الأصلية.[1][2] لكنه بعد ذلك تمكن من لفت أنظار الناس حيث رصد مكافأة 1000 $ لمن يتمكن من حل أحجية 15 التي اخترعها، حيث بدل بين قطعتي 14 و15،[3] لكن ذلك كان مستحيلاً، فلم يستطع أحد حلها.
قابلية الحل
الخوارزمية
توجد الأحجية أيضاً في أحجام أخرى أصغر، بحيث يكون حجم الإطار 3×3، فيكون اللغز هو أحجية 8. يمكن أن يكون حجم الإطار أكبر أو أصغر من ذلك، لذا فإنها تعرف أيضاً بأحجية ڽ، وتعتبر مشكلة كلاسيكية للخوارزميات النموذجية التي تنطوي على الاستدلال. عادة ما يستخدم الاستدلال لحل هذه المشكلة بعد عدد من القطع التي في غير محلها والعثور على مجموع المسافات بين كل قطعة وموقفها في تكوين الهدف بهندسة سيارة الأجرة.
جونسون وستوري
في 1879 استخدم جونسون ستوري حجة التكافؤ لإظهار أن نصف الحركات الأولى مستحيل أن تحل الأحجية، بغض النظر عن كيف تتم التحركات يتم ذلك من خلال النظر إلى وظيفة تكوين القطع تحت أي خطوة صالحة، ومن ثم استخدام هذا لتقسيم الفراغ المتكون من جميع القطع المرقمة إلى فئتين متكافئتين من القطع، وهما ممكنة الوصول وغير ممكنة الوصول.[4] الثابت هو تكافؤ التبديل بين جميع المساحات ال16 بالإضافة إلى تعادل مسافة سيارة الأجرة للمربع الفارغ من الزاوية اليمنى السفلى، وهذا ثابت لأن كل خطوة يتغير كل من تكافؤ التبديل وتكافؤ مسافة سيارة الأجرة، وبالتالي فإنه إذا كانت المساحة الفارغة في الزاوية اليمنى السفلى فإن الأحجية كون قابلة للحل إذا وفقط إذا كان التبديل بين القطع المتبقية متساوٍ.[4] جونسون وستوري أظهر أيضاً أن الشئ وعكسه يحصل على كل اللوحات التي من الحجم م×م حيث م≥2.[4]
آركر
في 1999 وضع آركر طريقة ترتبط بطريقة جونسون وستوري، ولكنه أعطى دليلاً آخر يعتمد على تحديد طبقات التكافؤ عبر المسار الهاملتونياني.[5]
ويلسون
في 1974 درس ويلسون تماثلية أحجية 15 على الرسوم البيانية الاعتباطية محدودة الاتصال غير القابلة للفصل، وأوضح أنه باستثناء المضلعات والقمم السبعة للرسوم البيانية، فمن الممكن الحصول على جميع التباديل إلا إذا كان الرسم البياني ثنائياً، وفي هذه الحالة يمكن الحصول على التباديل المتساوية، أما إذا كان الرسم البياني عبارة عن شكل سداسي منتظم مع رسم قطر واحد وإضافة نقطة في المركز، فإنه يمكن الحصول على 1/6 التبديلات فقط.[6]
مسائل NP صعبة
في الإصدارات الأكبر لأحجية 15، فإن إيجاد الحل سهل، لكن الصعب هو إيجاد الحل الأسرع، ويعد مسائل NP صعبة.[7] بالنسبة لأحجية 15، فإن أطوال الحلول المثلى تتراوح بين 0-80 حركة فردية[8] أو 43 حركة متعددة.[9]
المصادر
- The 15 Puzzle, by Jerry Slocum & Dic Sonneveld, 2006.
- Barry R. Clarke, Puzzles for Pleasure, pp.10-12, Cambridge University Press, 1994 .
- Korf, Richard E. (2000), "Recent progress in the design and analysis of admissible heuristic functions" ( كتاب إلكتروني PDF ), Recent Progress in the Design and Analysis of Admissible Heuristic Functions, 1864, Springer, صفحات 45–55, doi:10.1007/3-540-44914-0_3, ,26 أبريل 2010
- Johnson, Wm. Woolsey; Story, William E. (1879), "Notes on the "15" Puzzle", American Journal of Mathematics, The Johns Hopkins University Press, 2, صفحات 397–404, doi:10.2307/2369492, ISSN 0002-9327, JSTOR 2369492
- Archer, Aaron F. (1999), "A modern treatment of the 15 puzzle", The American Mathematical Monthly, 106, صفحات 793–799, doi:10.2307/2589612, ISSN 0002-9890, MR = 1732661 1732661
- Wilson, Richard M. (1974), "Graph puzzles, homotopy, and the alternating group", Journal of Combinatorial Theory. Series B, 16, صفحات 86–96, doi:10.1016/0095-8956(74)90098-7, ISSN 0095-8956, MR = 0332555 0332555
- Ratner, Daniel; Warmuth, Manfred (1990). "The (n2−1)-puzzle and related relocation problems". Journal of Symbolic Computation. 10 (2): 111–137. doi:10.1016/S0747-7171(08)80001-6.
- 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. نسخة محفوظة 11 نوفمبر 2017 على موقع واي باك مشين.
- "The Fifteen Puzzle can be solved in 43 "moves"". Domain of the Cube Forum نسخة محفوظة 12 نوفمبر 2017 على موقع واي باك مشين.