گەشتی ئەسپ

لە ئینسایکڵۆپیدیای ئازادی ویکیپیدیاوە
گەشتی ئەسپ لەسەر تەختەیەکی شەترەنج
گەشتی ئەسپ لەسەر تەختەیەکی ٥×٥

گەشتی ئەسپ (بە ئینگلیزی: Knight's tour) بریتییە لە پاشیەکییەکی جووڵەی ئەسپ لەسەر تەختەی شەترەنجدا بەشێوەیەک، کە تەنیا جارێک بە ھەر خانەیەکدا بڕوات. ژمارەی ڕێکی گەشتەکان لە تەختە شەترەنجێکی ٨×٨دا ھێشتا دیار نییە. کێشەی گەشتی ئەسپ کێشەیەکی ماتماتیکییە بۆ دۆزینەوەی گەشتی ئەسپێک و دروستکردنی بەرنامەیەک بۆ دۆزینەوەی گەشتی ئەسپ لەناو خوێندکارانی زانستی کۆمپیوتەردا گرفتێکی باوە. لە کاتێکدا ئەسپەکە دەگاتەوە ئەو خانەیەی لە دەستپێکی گشتەکەدا پێیدا ڕۆیشتووە، پێی دەوترێ گەشتی داخراو و پێچەوانەی ئەم حاڵەتە، گەشتی کراوەی پێ دەوترێت .[١]

تیۆری[دەستکاری]

کێشەی گەشتی ئەسپ لە تیۆریی گرافدا حاڵەتێکی تایبەتی کێشەی ڕێڕەوی ھەمیلتۆنییە. بە ھەمان شێوە، کێشەی دۆزینەوەی گەشتێکی داخراو، نموونەیەکە لە کێشەی دەوری ھەمیلتۆنی. بە پێچەوانەی کێشەی ڕێڕەوی ھەمیلتۆنی، لە کاتی ھێڵیدا کێشەی گەشتی ئەسپ دەتوانرێت چارەسەر بکرێت. [٢]

ژمارەی گەشتە داخراوەکان[دەستکاری]

لە تەختەیەکی ٨×٨دا، ڕێک ٢٦٬٥٣٤٬٧٢٨٬٨٢١٬٠٦٤ گەشتی داخراوی ئاڕاستەدار بوونی ھەیە.[٣][٤][٥] ژمارەی گەشتە داخراوە بێ ئاڕاستەکان نیوەی ئەم ژمارەیە. ٩٬٨٦٢ گەشتی داخراوی بێ ئاڕاستە لە تەختەیەکی ٦×٦دا بوونی ھەیە.[٦]

کام یەک لە تەختەکان گەشتیان ھەیە[دەستکاری]

شوێنک[٧] سەلماندی لە ھەر تەختەیەکی m×nدا کە m کەمتر یان یکسانە بە n، ھەمیشە گەشتێکی داخراو بوونی ھەیە، مەگەر ئەوەی کە لانیکەم یەکێک لەم مەرجانە بێتەدی:

  1. m و n ھەردووکیان تاک بن. n یەکسان نەبێت بە ١.
  2. m = ١، ٢ یان ٤. n یەکسان نەبێت بە ١ .
  3. m = ٣ و n = ٤، ٦ یا ٨.

کول و دێ کورتیز سەلماندیان لە ھەر تەختەیەکی چوارگۆشەییدا کە کەمترین ڕەھەندی لانیکەم ٥ بێت، گەشتێکی ئەسپ (لەوانەیە کراوە بێت) بوونی ھەیە.[٨]

دۆزینەوەی گەشتەکان بە کۆمپیوتەر[دەستکاری]

بە بەکارھێنانی کۆمپیوتەر زۆر ڕێگەی جیاواز ھەیە بۆ دۆزینەوەی گەشتی ئەسپێک. ھەندێکیان لە ڕێگەی ئەلگۆریتمەکانەوە دەدۆزرێنەوە و ھەندێک ڕێگەش ھەیە داھێنراون.

یاسای وارنزدرۆف[دەستکاری]

سەرچاوەکان[دەستکاری]

  1. ^ H. M. Deitel, P. J. Deitel. "Java How To Program Fifth Edition." Prentice Hall, Upper Saddle River, New Jersey, pp. 326–328. 2003.
  2. ^ Conrad, A.; Hindrichs, T.; Morsy, H.; Wegener, I. (1994). "Solution of the Knight's Hamiltonian Path Problem on Chessboards". Discrete Applied Mathematics. ٥٠ (٢): ١٢٥–١٣٤. doi:10.1016/0166-218X(92)00170-Q. {{cite journal}}: Unknown parameter |lastauthoramp= ignored (help)
  3. ^ Martin Loebbing; Ingo Wegener (1996). "The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams". The Electronic Journal of Combinatorics. ٣ (١): R5.{{cite journal}}: CS1 maint: multiple names: پێرستی نووسەران (link) Remark: The authors later admitted that the announced number is incorrect. According to McKay's report, the correct number is 13,267,364,410,532 and this number is repeated in Wegener's 2000 book.
  4. ^ Brendan McKay (1997). "Knight's Tours on an 8x8 Chessboard". Technical Report TR-CS-97-03. Department of Computer Science, Australian National University. Archived from the original on 27ی Januaryی 2012. Retrieved 15ی Februaryی 2019. {{cite journal}}: Check date values in: |access-date= و |archive-date= (help); Unknown parameter |بەستەری شکاو= ignored (help); Unknown parameter |ناونیشانی ئەرشیڤ= ignored (help); Unknown parameter |ڕێکەوتی ئەرشیڤ= ignored (help); Unknown parameter |ڕێکەوتی بەدەستھێنان= ignored (help) ٢٧ی کانوونی دووەمی ٢٠١٢ لە وەیبەک مەشین، ئەرشیڤ کراوە.
  5. ^ Wegener, I. (2000). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-89871-458-3.
  6. ^ ئێریک ویستیەن، Knight's Tour لە ماتوۆرڵد.
  7. ^ Allen J. Schwenk (1991). "Which Rectangular Chessboards Have a Knight's Tour?". Mathematics Magazine: ٣٢٥–٣٣٢.
  8. ^ Cull, Paul. "Knight's Tour Revisited" (PDF). Fibonacci Quarterly. Retrieved 5 August 2012.

بەستەرە دەرەکییەکان[دەستکاری]