گەشتی ئەسپ

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

تیۆری

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

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

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

کام یەک لە تەختەکان گەشتیان ھەیە

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

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

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

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

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

یاسای وارنزدرۆف

سەرچاوەکان

^ H. M. Deitel, P. J. Deitel. "Java How To Program Fifth Edition." Prentice Hall, Upper Saddle River, New Jersey, pp. 326–328. 2003.
^ Conrad، A. (١٩٩٤). «Solution of the Knight's Hamiltonian Path Problem on Chessboards». Discrete Applied Mathematics. ٥٠ (٢): ١٢٥–١٣٤. doi:10.1016/0166-218X(92)00170-Q. {{cite journal}}: پارامەتری نەناسراوی |lastauthoramp= چاوپۆشیی لێ کرا (|name-list-style= پێشنیار کراوە) (یارمەتی)
^ 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.{{cite journal}}: ڕاگرتنی شێوازی سەرچاوەی ١: ناوە فرەکان: authors list (بەستەر) 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.
^ Brendan McKay (١٩٩٧). «Knight's Tours on an 8x8 Chessboard». Technical Report TR-CS-97-03. Department of Computer Science, Australian National University. لە ڕەسەنەکە لە ٢٧ی کانوونی دووەمی ٢٠١٢ ئەرشیڤ کراوە. لە ١٥ی شوباتی ٢٠١٩ ھێنراوە. {{cite journal}}: زیاتر لە یەک دانە لە |ناونیشانی ئەرشیڤ= و |archive-url= دیاری کراوە (یارمەتی); زیاتر لە یەک دانە لە |ڕێکەوتی ئەرشیڤ= و |archive-date= دیاری کراوە (یارمەتی); پارامەتری نەناسراوی |بەستەری شکاو= چاوپۆشیی لێ کرا (یارمەتی); پارامەتری نەناسراوی |ڕێکەوتی بەدەستھێنان= چاوپۆشیی لێ کرا (یارمەتی) ٢٧ی کانوونی دووەمی ٢٠١٢ لە وەیبەک مەشین، ئەرشیڤ کراوە.
^ Wegener, I. (٢٠٠٠). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN ٠-٨٩٨٧١-٤٥٨-٣. {{cite book}}: نرخی |isbn= بپشکنە: invalid character (یارمەتی)
^ ئێریک ویستیەن، Knight's Tour لە ماتوۆرڵد.
^ Allen J. Schwenk (١٩٩١). «Which Rectangular Chessboards Have a Knight's Tour?». Mathematics Magazine: ٣٢٥–٣٣٢.
^ Cull، Paul. «Knight's Tour Revisited» (PDF). Fibonacci Quarterly. لە ٥ی ئابی ٢٠١٢ ھێنراوە.

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

ئەم «ماتماتیک» وتارە کۆلکەیەکە. دەتوانیت بە فراوانکردنی یارمەتیی ویکیپیدیا بدەیت.

[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. (١٩٩٤). «Solution of the Knight's Hamiltonian Path Problem on Chessboards». Discrete Applied Mathematics. ٥٠ (٢): ١٢٥–١٣٤. doi:10.1016/0166-218X(92)00170-Q. {{cite journal}}: پارامەتری نەناسراوی |lastauthoramp= چاوپۆشیی لێ کرا (|name-list-style= پێشنیار کراوە) (یارمەتی)

[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.{{cite journal}}: ڕاگرتنی شێوازی سەرچاوەی ١: ناوە فرەکان: authors list (بەستەر) 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. لە ڕەسەنەکە لە ٢٧ی کانوونی دووەمی ٢٠١٢ ئەرشیڤ کراوە. لە ١٥ی شوباتی ٢٠١٩ ھێنراوە. {{cite journal}}: زیاتر لە یەک دانە لە |ناونیشانی ئەرشیڤ= و |archive-url= دیاری کراوە (یارمەتی); زیاتر لە یەک دانە لە |ڕێکەوتی ئەرشیڤ= و |archive-date= دیاری کراوە (یارمەتی); پارامەتری نەناسراوی |بەستەری شکاو= چاوپۆشیی لێ کرا (یارمەتی); پارامەتری نەناسراوی |ڕێکەوتی بەدەستھێنان= چاوپۆشیی لێ کرا (یارمەتی) ٢٧ی کانوونی دووەمی ٢٠١٢ لە وەیبەک مەشین، ئەرشیڤ کراوە.

[5] Wegener, I. (٢٠٠٠). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN ٠-٨٩٨٧١-٤٥٨-٣. {{cite book}}: نرخی |isbn= بپشکنە: invalid character (یارمەتی)

[6] ئێریک ویستیەن، Knight's Tour لە ماتوۆرڵد.

[7] Allen J. Schwenk (١٩٩١). «Which Rectangular Chessboards Have a Knight's Tour?». Mathematics Magazine: ٣٢٥–٣٣٢.

[8] Cull، Paul. «Knight's Tour Revisited» (PDF). Fibonacci Quarterly. لە ٥ی ئابی ٢٠١٢ ھێنراوە.

[١]

[٢]

[٣]

[٤]

[٥]

[٦]

[٧]

[٨]