عبد العزيز: بوت:نقل من تصنيف:القرن 19 في الرياضات إلى تصنيف:الرياضات في القرن 19

2023-08-26T03:03:19Z

بوت:نقل من تصنيف:القرن 19 في الرياضات إلى تصنيف:الرياضات في القرن 19

صفحة جديدة

[[ملف:15-puzzle.svg|تصغير|يسار|أحجية 15 محلولة.]]

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

== التاريخ ==

[[ملف:15-puzzle-loyd.svg|تصغير|يسار|أحجية 15 الغير قابلة للحل لسام لويد.]]

اخترعت أحجية 15 من قبل نويس بالمر شابمان،<ref name="slocum-sonneveld">''The 15 Puzzle'', by Jerry Slocum & Dic Sonneveld, 2006. ISBN 1-890980-15-3</ref> وكان مدير مكتب البريد في كاناسوتا، [[نيويورك (ولاية)|نيويورك]] أوائل عام [[1874]]، وكانت سريعة الانتشار، حيث نقلت إلى [[سيراكيوز (نيويورك)|سيراكيوز]] 15 نسخة منها على يد ابنه فرانك، ومنها إلى وتش هيل، ثم إلى هارتفورد ب[[كونيتيكت|كونيكتيكوت]]، حيث بدأ طلاب المدرسة الأمريكية للصم تصنيع الأحجية، وفي ديسمبر [[1879]] بدأ بيعها محلياً في بوسطن ب[[ماساتشوستس|ماساشوستس]]، وبدأ نجار يدعى ماتياس رايس صناعتها، وأقنع رجل أعمال يدعى يانكي نوشنز ببيعها تحت اسم «أحجية الجوهرة» في أواخر يناير [[1880]].<ref name="slocum-sonneveld"/> انتشرت اللعبة في [[الولايات المتحدة]] في [[فبراير]]، وفي [[كندا]] في [[مارس]]، وفي [[أوروبا]] في [[أبريل]]، ولم تدخل أحجية 15 [[اليابان]] إلا عام [[1889]].

قال سام لويد في [[1891]] أنه هو من اخترع أحجية 15، لكنه لم يتمكن من الوصول لشعبية اللعبة الأصلية.<ref name="slocum-sonneveld"/><ref>Barry R. Clarke, ''Puzzles for Pleasure'', pp.10-12, Cambridge University Press, 1994 ISBN 0-521-46634-2.</ref> لكنه بعد ذلك تمكن من لفت أنظار الناس حيث رصد مكافأة 1000 [[دولار أمريكي|$]] لمن يتمكن من حل أحجية 15 التي اخترعها، حيث بدل بين قطعتي 14 و15،<ref>{{استشهاد| الأول=Richard E. | الأخير=Korf | مسار الفصل=https://www.aaai.org/Papers/AAAI/2000/AAAI00-212.pdf | doi=10.1007/3-540-44914-0_3 | الفصل=Recent progress in the design and analysis of admissible heuristic functions | سلسلة=SARA 2000. Abstraction, reformulation, and approximation: 4th international symposium, Texas, USA. LNCS 1864 | صفحات=45–55 | ناشر=Springer | سنة=2000 | isbn=978-3-540-67839-7 | تاريخ الوصول=2010-04-26 | عنوان=Recent Progress in the Design and Analysis of Admissible Heuristic Functions | المجلد=1864}}</ref> لكن ذلك كان مستحيلاً، فلم يستطع أحد حلها.

== قابلية الحل ==

=== الخوارزمية ===

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

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

في [[1879]] استخدم جونسون ستوري حجة التكافؤ لإظهار أن نصف الحركات الأولى مستحيل أن تحل الأحجية، بغض النظر عن كيف تتم التحركات يتم ذلك من خلال النظر إلى وظيفة تكوين القطع تحت أي خطوة صالحة، ومن ثم استخدام هذا لتقسيم الفراغ المتكون من جميع القطع المرقمة إلى فئتين متكافئتين من القطع، وهما ممكنة الوصول وغير ممكنة الوصول.<ref name="JohnsonStory">{{استشهاد| الأخير1=Johnson | الأول1=Wm. Woolsey | الأخير2=Story | الأول2=William E. | عنوان=Notes on the "15" Puzzle | ناشر=The Johns Hopkins University Press | سنة=1879 | صحيفة=[[American Journal of Mathematics]] | issn=0002-9327 | المجلد=2 | العدد=4 | صفحات=397–404 | jstor=2369492 | doi=10.2307/2369492}}</ref>
الثابت هو تكافؤ التبديل بين جميع المساحات ال16 بالإضافة إلى تعادل [[هندسة سيارة الأجرة|مسافة سيارة الأجرة]] للمربع الفارغ من الزاوية اليمنى السفلى، وهذا ثابت لأن كل خطوة يتغير كل من تكافؤ التبديل وتكافؤ مسافة سيارة الأجرة، وبالتالي فإنه إذا كانت المساحة الفارغة في الزاوية اليمنى السفلى فإن الأحجية كون قابلة للحل إذا وفقط إذا كان التبديل بين القطع المتبقية متساوٍ.<ref name="JohnsonStory"/>
جونسون وستوري أظهر أيضاً أن الشئ وعكسه يحصل على كل اللوحات التي من الحجم م×م حيث م≥2.<ref name="JohnsonStory"/>

=== آركر ===

في [[1999]] وضع آركر طريقة ترتبط بطريقة جونسون وستوري، ولكنه أعطى دليلاً آخر يعتمد على تحديد طبقات التكافؤ عبر [[مسار هاملتونياني|المسار الهاملتونياني]].<ref>{{استشهاد| الأخير1=Archer | الأول1=Aaron F. | عنوان=A modern treatment of the 15 puzzle | mr=1732661 | سنة=1999 | صحيفة=[[الرياضيات الأمريكية الشهرية|The American Mathematical Monthly]] | issn=0002-9890 | المجلد=106 | العدد=9 | صفحات=793–799 | doi=10.2307/2589612}}</ref>

=== ويلسون ===

في [[1974]] درس ويلسون تماثلية أحجية 15 على الرسوم البيانية الاعتباطية محدودة الاتصال غير القابلة للفصل، وأوضح أنه باستثناء المضلعات والقمم السبعة للرسوم البيانية، فمن الممكن الحصول على جميع التباديل إلا إذا كان الرسم البياني ثنائياً، وفي هذه الحالة يمكن الحصول على التباديل المتساوية، أما إذا كان الرسم البياني عبارة عن شكل سداسي منتظم مع رسم قطر واحد وإضافة نقطة في المركز، فإنه يمكن الحصول على 1/6 التبديلات فقط.<ref name="Wilson">{{استشهاد| الأخير1=Wilson | الأول1=Richard M. | عنوان=Graph puzzles, homotopy, and the alternating group | doi=10.1016/0095-8956(74)90098-7 | mr=0332555 | سنة=1974 | صحيفة=Journal of Combinatorial Theory. Series B | issn=0095-8956 | المجلد=16 | صفحات=86–96}}</ref>

=== [[مسائل NP صعبة]] ===

في الإصدارات الأكبر لأحجية 15، فإن إيجاد الحل سهل، لكن الصعب هو إيجاد الحل الأسرع، ويعد [[مسائل NP صعبة]].<ref name=ratner+warmuth>{{استشهاد بدورية محكمة|الأخير=Ratner|الأول=Daniel|مؤلف2=Warmuth, Manfred|عنوان=The (n<sup>2</sup>−1)-puzzle and related relocation problems|صحيفة=Journal of Symbolic Computation|سنة=1990|المجلد=10|العدد=2|صفحات=111–137|doi=10.1016/S0747-7171(08)80001-6}}</ref> بالنسبة لأحجية 15، فإن أطوال الحلول المثلى تتراوح بين 0-80 حركة فردية<ref>A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, [http://www.iro.umontreal.ca/~gendron/Pisa/References/BB/Brungger99.pdf The parallel search bench ZRAM and its applications], ''Annals of Operations Research'' '''90''' (1999), pp. 45–63. {{Webarchive|url=https://web.archive.org/web/20171111193526/http://www.iro.umontreal.ca/~gendron/Pisa/References/BB/Brungger99.pdf |date=11 نوفمبر 2017}}</ref> أو 43 حركة متعددة.<ref name="multi-tile">[http://cubezzz.duckdns.org/drupal/?q=node/view/223 "The Fifteen Puzzle can be solved in 43 "moves""]. Domain of the Cube Forum {{Webarchive|url=https://web.archive.org/web/20171112212134/http://cubezzz.duckdns.org/drupal/?q=node/view/223 |date=12 نوفمبر 2017}}</ref>

== المصادر ==

{{مراجع}}

== انظر أيضاً ==
* [[مكعب روبيك]]

{{تصنيف كومنز|15 puzzle}}
{{شريط بوابات|ألعاب|ألعاب تقمص أدوار|القرن 19|رياضيات}}

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

أحجية 15 - تاريخ المراجعة

عبد العزيز: بوت:نقل من تصنيف:القرن 19 في الرياضات إلى تصنيف:الرياضات في القرن 19