پازێلی ١٥
 | ئەم وتارە ھەتیوە، چونکە ھیچ وتارێکی تر بەستەری پێی نەداوە. تکایە لە وتارە پەیوەندیدارەکانەوە بەستەرەکان بەم پەڕە ئاشنا بکە؛ بۆ پێشنیارەکان ئامرازی دۆزینەوەی بەستەر تاقی بکەرەوە. (تشرینی دووەمی ٢٠٢٥) |
پازێلی ١٥ (بە ئینگلیزی: 15 puzzle) بریتییە لە پازێلێکی خزان یان خلیسکان کە لە چوارچێوەیەکی ٤*٤ی چوارگۆشەیی پێکھاتووە، تێیدا ژمارەکان بە شێوەی ھەڕەمەکی ڕیز کراون و یەکێک لە خانەکانی بەتاڵە. مەبەست لە شیکردنەوەی پازێلەکە، ئەوەیە کە بەجۆرێک بە خلیسکاندن و خزاندن، ژمارەکان ڕیز بکرێن. پازێلەکە لە سایزی تریشدا ھەیە، بۆ نموونە پازێلی ٣*٣، پازێلی ٨ یان پازێلی ٩ی پێ دەوترێت و بە پازێلی ٤*٤، پازێلی ١٥ یان پازێلی ١٦ دەوترێت.
مێژوو
[دەستکاری]یاری پازڵی ١٥ لەلایەن نویس پاڵمەر چاپمان، بەڕێوەبەری پۆستەی کاناستۆتا، نیوویۆرک لە سەرەتای ساڵی ١٨٧٤دا داھێنرا، و زۆر بە خێرایی بڵاو بووەوە. ١٥ دانەی لێ گوازرایەوە بۆ سیراکیوز لەلایەن کوڕەکەی فرانکەوە، پاشان بۆ وۆچ ھیڵ، و دواتر بۆ ھارتفۆرد لە کۆنێتیکت، لەوێ خوێندکارانی قوتابخانەی ئەمریکی بۆ کەڕەکان دەستیان بە دروستکردنی پازڵەکە کرد. لە کانوونی یەکەمی ١٨٧٩، دەستیان بە فرۆشتنی ناوخۆیی کرد لە بۆستن، ماساچوسیتس، و دارتاشێک بە ناوی ماتیاس ڕایس دەستی بە دروستکردنی کرد. پیاوێکی بازرگان بە ناوی یانکی نۆشنز قایەل کرا کە لە کۆتایی مانگی یەکەمی ١٨٨٠دا بە ناوی «پازڵی گەوھەر» بیفرۆشێت. یارییەکە لە مانگی شوباتدا لە ئەمریکا، لە مانگی ئازاردا لە کەنەدا، و لە مانگی نیساندا لە ئەورووپا بڵاو بووەوە، بەڵام پازڵی ١٥ تا ساڵی ١٨٨٩ نەگەیشتە ژاپۆن.
سام لۆید لە ساڵی ١٨٩١دا وتی کە ئەو داھێنەری پازڵی ١٥ بووە، بەڵام نەیتوانی بگاتە ئاستی ناوبانگی یارییە ڕەسەنەکە؛ بەڵام دواتر توانی سەرنجی خەڵک ڕابکێشێت کاتێک خەڵاتێکی ١٠٠٠ دۆلاری دانا بۆ ھەر کەسێک کە بتوانێت ئەو پازڵی ١٥یەی ئەو دای ھێنابوو چارەسەر بکات، کە تێیدا پارچەکانی ١٤ و ١٥ی گۆڕیبوو؛ بەڵام ئەمە مەحاڵ بوو، بۆیە ھیچ کەسێک نەیتوانی چارەسەری بکات.[١]
توانای چارەسەرکردن
[دەستکاری]ئەلگۆریتم (خەواریزمییەت)
[دەستکاری]پازڵەکە لە قەبارەی بچووکتردا، وەک چوارچێوەی ٣×٣، واتە پازڵی ٨، بوونی ھەیە. قەبارەی چوارچێوەکە دەتوانێت گەورەتر یان بچووکتر بێت، بۆیە بە "پازڵی N" ناسراوە، و وەک کێشەیەکی کلاسیکی ئەلگۆریتمی نموونەیی دادەنرێت کە پشت بە ھیوریستیک دەبەستێت. بەزۆری ھیوریستیک بەکاردێت بۆ چارەسەرکردنی ئەم کێشەیە بە ژماردنی ژمارەی پارچەکان کە لە شوێنی خۆیاندا نین و دۆزینەوەی کۆی مەودای نێوان ھەر پارچەیەک و شوێنی خۆی لە پێکھاتەی ئامانجدا بە "تاکسی جیۆمەتری".
جۆنسن و ستۆری
[دەستکاری]لە ساڵی ١٨٧٩دا، جۆنسن ستۆری بەڵگەیەکی ھاوتابوونی بەکارھێنا بۆ ئەوەی پیشان بدات کە نیوەی جووڵە سەرەتایییەکان مەحاڵە پازڵەکە چارەسەر بکەن، بەبێ گوێدانە ئەوەی جووڵەکان چۆن ئەنجام دەدرێن. ئەمە بە لەبەرچاوگرتنی کارکردی پێکھاتەی پارچەکان لەژێر ھەر ھەنگاوێکی دروست دا دەکرێت، و پاشان بەکارھێنانی ئەمە بۆ دابەشکردنی بۆشایی پێکھاتوو لە ھەموو پارچە ژمارەیییەکان بۆ دوو پۆلی ھاوتا لە پارچەکان: گەیشتوو پێیان و نەگەیشتوو پێیان. نەگۆڕەکە بریتییە لە ھاوتابوونی گۆڕانکاری لە نێوان ھەموو ١٦ بۆشایییەکەدا، لەگەڵ ھاوتابوونی مەودای تاکسی بۆ چوارگۆشە بەتاڵەکە لە گۆشەی خوارەوەی ڕاست. ئەمە نەگۆڕە چونکە لە ھەر ھەنگاوێکدا، ھەردوو ھاوتابوونی گۆڕانکاری و ھاوتابوونی مەودای تاکسی دەگۆڕێن. بەم شێوەیە، ئەگەر بۆشایی بەتاڵ لە گۆشەی خوارەوەی ڕاستدا بێت، پازڵەکە چارەسەر دەکرێت تەنھا ئەگەر گۆڕانکاری نێوان پارچە ماوەکان یەکسان بێت. جۆنسن و ستۆری ئەوەشیان پیشان دا کە ھەمان شت و پێچەوانەکەی لە ھەموو تەختەکانی قەبارەی m×m دا ڕوو دەدات کە m≥2.[٢]
ئارکەر
[دەستکاری]لە ساڵی ١٩٩٩دا، ئارکەر ڕێگەیەکی خستەڕوو کە پەیوەستە بە ڕێگەکەی جۆنسن و ستۆری، بەڵام بەڵگەیەکی دیکەی خستەڕوو کە پشت بە دیاریکردنی چینەکانی ھاوتابوون لە ڕێگەی ڕێڕەوی ھامیلتۆنییەوە دەبەستێت.[٣]
ویلسۆن
[دەستکاری]لە ساڵی ١٩٧٤دا، ویلسۆن ھاوتابوونی پازڵی ١٥ی لەسەر گرافی ئاربیتراری سنووردار و بێ پەیوەندی و جیا نەکراوەدا تاوتوێ کرد، و ڕوونی کردەوە کە جگە لە فرەگۆشەکان و حەوت لووتکەی گرافەکان، دەتوانرێت ھەموو گۆڕانکارییەکان بەدەست بھێنرێن تەنھا ئەگەر گرافەکە دوولایەنە بێت، لەم حاڵەتەدا دەتوانرێت گۆڕانکارییە ھاوتاکان بەدەست بھێنرێن؛ بەڵام ئەگەر گرافەکە شێوەی شەشگۆشەیەکی ڕێک بێت لەگەڵ یەک قوتر و زیادکردنی خاڵێک لە ناوەنددا، تەنھا ١/٦ی گۆڕانکارییەکان دەتوانرێت بەدەست بھێنرێن.[٤]
کێشە سەختەکانی NP
[دەستکاری]لە وەشانی گەورەتری پازڵی ١٥دا، دۆزینەوەی چارەسەر ئاسانە، بەڵام دۆزینەوەی خێراترین چارەسەر قورسە، و بە کێشەی سەختی NP دادەنرێت. بۆ پازڵی ١٥، درێژی چارەسەرە باشترینەکان لە نێوان ٠–٨٠ جووڵەی تاکەکەسی یان ٤٣ جووڵەی فرە-بلۆکدایە.[٥][٦][٧]
ئەمانەش ببینە
[دەستکاری]سەرچاوەکان
[دەستکاری]- ↑ The 15 Puzzle, by Jerry Slocum & Dic Sonneveld, 2006. ISBN 1-890980-15-3
- ↑ 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
- ↑ 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
- ↑ 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.
- ↑ https://www.iro.umontreal.ca/~gendron/Pisa/References/BB/Brungger99.pdf
- ↑ https://web.archive.org/web/20171112212134/http://cubezzz.duckdns.org/drupal/?q=node/view/223
- بەشداربووانی ویکیپیدیا، «15 puzzle»، ویکیپیدیای ئینگلیزی. سەردان لە ٢٣ی شوباتی ٢٠١٩.
