گەشتی ئەسپ

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

گەشتی ئەسپ (بە ئینگلیزی: 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. (١٩٩٤). "Solution of the Knight's Hamiltonian Path Problem on Chessboards". Discrete Applied Mathematics. ٥٠ (٢): ١٢٥–١٣٤. doi:10.1016/0166-218X(92)00170-Q. 
  3. ^ Martin Loebbing; Ingo Wegener (١٩٩٦). "The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams". The Electronic Journal of Combinatorics. ٣ (١): R5.  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 (١٩٩٧). "Knight's Tours on an 8x8 Chessboard". Technical Report TR-CS-97-03. Department of Computer Science, Australian National University. 
  5. ^ Wegener, I. (٢٠٠٠). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN ٠-٨٩٨٧١-٤٥٨-٣ دڵنیابەرەوە لە دروستیی بەھای |isbn= بەھا: invalid character (یارمەتی). 
  6. ^ داڕێژە:MathWorld
  7. ^ Allen J. Schwenk (١٩٩١). "Which Rectangular Chessboards Have a Knight's Tour?". Mathematics Magazine: ٣٢٥–٣٣٢. 
  8. ^ Cull، Paul. "Knight's Tour Revisited" (PDF). Fibonacci Quarterly. لە ڕێکەوتی ٠٥ی ئابی ٢٠١٢ ھێنراوە. 

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