نمایش مبدأ برای سفر اسب

{{Hide in print|[[پرونده:Knight's tour anim 2.gif|چپ|بندانگشتی|250px|سفر اسب در صفحهٔ شطرنج]]}}{{Only in print|[[پرونده:Knight's tour.svg|راست|بندانگشتی|250px|An open knight's tour of a chessboard]]}}
{{Hide in print|[[پرونده:Knights-Tour-Animation.gif|چپ|بندانگشتی|250px|سفر اسب در یک صفحهٔ ۵×۵]]}}

'''سفر اسب''' به دنباله‌ای از حرکات یک [[اسب (شطرنج)|مهرهٔ اسب]] در یک [[صفحه شطرنج|صفحهٔ شطرنج]] گفته می‌شود به طوری که از هر خانه دقیقاً یک بار بگذرد. اگر اسب به خانه‌ای برسد که از ابتدای سفر از آن گذشته‌است، سفر ''بسته'' است. در غیر این صورت، سفر ''باز'' است. تعداد دقیق سفرها در یک [[صفحهٔ شطرنج]] ۸×۸ هنوز مشخص نیست.

'''مسئلهٔ سفر اسب''' یک مسئلهٔ ریاضیات شطرنجی برای پیدا کردن یک سفر اسب است. ساخت یک برنامه برای پیدا کردن یک سفر اسب یک مسئلهٔ رایج برای دانشجویان [[علوم کامپیوتر]] است.<ref>H. M. Deitel, P. J. Deitel. "Java How To Program Fifth Edition." ''Prentice Hall'', Upper Saddle River, New Jersey, pp. 326–328. 2003.</ref> انواع مختلف مسئلهٔ سفر اسب به خاطر تفاوت در اندازهٔ صفحه‌های شطرنج و هم‌چنین صفحه‌های غیرمربعی است.

== نظریه ==
[[پرونده:Knight's graph showing number of possible moves.svg|راست|بندانگشتی|270px|[[گراف اسب]] تمام مسیرهای ممکن برای یک سفر اسب را در یک صفحهٔ شطرنج استاندارد ۸×۸ نشان می‌دهد. عددهای هر رأس بیان‌گر تعداد حرکات ممکن که می‌توانند از آن رأس شروع شوند هستند.]]

مسئلهٔ سفر اسب نمونه‌ای از مسئلهٔ کلّی‌تر [[مسیر همیلتونی]] در [[نظریهٔ گراف]] است. مشابهاً، مسئلهٔ پیدا کردن یک سفر بسته برای اسب، یک نمونه از [[مسیر همیلتونی|مسئلهٔ دور همیلتونی]] است. برخلاف [[مسیر همیلتونی|مسئلهٔ مسیر همیلتونی]]، مسئلهٔ سفر اسب می‌تواند در [[زمان اجرای خطی|زمان خطی]] حل شود.<ref>{{Cite journal |first=A. |last=Conrad |first2=T. |last2=Hindrichs |first3=H. |last3=Morsy |name-list-style=amp|first4=I. |last4=Wegener |title=Solution of the Knight's Hamiltonian Path Problem on Chessboards |url=https://archive.org/details/sim_discrete-applied-mathematics_1994-05-06_50_2/page/n26 |journal=Discrete Applied Mathematics |volume=50 |issue=2 |pages=125–134 |year=1994 |doi=10.1016/0166-218X(92)00170-Q}}</ref>
{{clear}}

== تعداد سفرهای بسته ==
در یک صفحهٔ ۸×۸، دقیقاً ۲۶٬۵۳۴٬۷۲۸٬۸۲۱٬۰۶۴ سفر بستهٔ جهت‌دار وجود دارد. (برای مثال دو سفر در طول مسیر یکسان که دارای جهت‌های مخالف هستند جداگانه شمارش می‌شوند، چرخش‌ها و تقارن‌ها هم به همین صورت هستند)<ref>{{cite journal
 | author=Martin Loebbing; Ingo Wegener
 | title=The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams
 | journal=The Electronic Journal of Combinatorics
 | volume=3
 | issue=1
 | pages=R5
 | year=1996
 | url=http://www.combinatorics.org/Volume_3/Abstracts/v3i1r5.html
}} '''Remark:''' The authors later [http://www.combinatorics.org/Volume_3/Comments/v3i1r5.html 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.</ref><ref>{{cite journal
 | authorlink=Brendan McKay
 | author=Brendan McKay
 | title=Knight's Tours on an 8x8 Chessboard
 | journal=Technical Report TR-CS-97-03
 | publisher=Department of Computer Science, Australian National University
 | year=1997
 | url=http://www.combinatorics.org/Volume_3/Comments/v3i1r5.01.ps
 | access-date=۲۴ ژوئن ۲۰۱۳
 | archive-url=https://web.archive.org/web/20120127042807/http://www.combinatorics.org/Volume_3/Comments/v3i1r5.01.ps
 | archive-date=۲۷ ژانویه ۲۰۱۲
 | dead-url=yes
 }}</ref><ref>{{cite book
 | author= Wegener, I.
 | title=Branching Programs and Binary Decision Diagrams
 | publisher=Society for Industrial & Applied Mathematics
 | year=2000
 | isbn=0-89871-458-3
 | url=http://books.google.com/?id=-DZjVz9E4f8C&pg=PA369&dq=532}}</ref> تعداد سفرهای بستهٔ غیرجهت‌دار نصف این عدد است زیرا هر سفر می‌تواند در جهت عکس نیز به‌حساب‌بیاید. ۹٬۸۶۲ سفر بستهٔ غیرجهت‌دار در یک صفحهٔ ۶×۶ وجود دارد.<ref>{{MathWorld|urlname=KnightsTour|title=Knight's Tour}}</ref>

== کدام صفحه‌ها دارای سفر هستند ==
شْوِنْک<ref>{{cite journal
 | author=Allen J. Schwenk
 | title=Which Rectangular Chessboards Have a Knight’s Tour?
 | journal=Mathematics Magazine
 | year=1991
 | pages=325–332
}}</ref>
ثابت کرد برای هر صفحهٔ m×n که در آن m کم‌تر یا مساوی n است، یک سفر بستهٔ اسب همیشه وجود دارد مگر این که حداقل یکی از این شروط برقرار باشند:
# ''m'' و ''n'' هر دو فرد باشند. n مساوی ۱ نباشد.
# ''m'' = ۱، ۲ یا ۴. n مساوی ۱ نباشد.
# ''m'' = ۳ و ''n'' = ۴، ۶ یا ۸.
کول و د کورتینز اثبات کردند در هر صفحهٔ مربعی که کوچک‌ترین بعد آن حداقل ۵ باشد، یک سفر (احتمالاً باز) اسب وجود دارد.<ref>{{cite web|last=Cull|first=Paul|title=Knight's Tour Revisited|url=http://www.fq.math.ca/Scanned/16-3/cull.pdf|work=Fibonacci Quarterly|accessdate=5 August 2012}}</ref>

== پیدا کردن سفرها با کامپیوتر ==
راه‌های مختلفی برای پیدا کردن یک سفر اسب در یک صفحه با یک کامپیوتر وجود دارد. برخی از این راه‌ها [[الگوریتم]] هستند در حالی که بقیه ابتکاری هستند.

=== الگوریتم‌های جامع ===
یک [[جستجوی جامع]] برای یک سفر اسب برای تمامی صفحه‌ها غیر از صفحه‌های کوچک غیرعملی است. برای مثال، در یک صفحهٔ ۸x۸ تقریباً ۴x10<sup>۵۱</sup> دنبالهٔ حرکت ممکن وجود دارد<ref>{{cite web |url=http://www.josiahland.com/?p=781 |title = Enumerating the Knight's Tour}}</ref> و انجام عملیات روی چنین مجموعهٔ بزرگی فرای ظرفیت کامپیوترهای امروزی (یا شبکه‌هایی از کامپیوترها) است.

=== الگوریتم‌های تقسیم و حل ===
با تقسیم صفحه به قسمت‌های کوچک‌تر، ساخت سفر در هر قسمت و وصل کردن قسمت‌ها به یکدیگر، می‌توان در بیش‌تر صفحه‌های مربعی در زمان چندجمله‌ای سفرها را پیدا کرد.<ref>{{cite journal|last = Cull|first = P.|coauthors=DeCurtins, J.|title = Knight's Tour Revisited|url = https://archive.org/details/sim_fibonacci-quarterly_1978-06_16_3/page/276|journal = Fibonacci Quarterly|volume = 16|date = June 1978|pages = 276–285}}</ref><ref>{{cite journal|last = Parberry|first = Ian|title = An Efficient Algorithm for the Knight's Tour Problem|journal = Discrete Applied Mathematics|volume = 73|year = 1997|pages = 251–260|doi = 10.1016/S0166-218X(96)00010-8|url = http://larc.unt.edu/ian/pubs/algoknight.pdf|access-date = ۲۴ ژوئن ۲۰۱۳|archive-url = https://web.archive.org/web/20130927194856/http://larc.unt.edu/ian/pubs/algoknight.pdf|archive-date = ۲۷ سپتامبر ۲۰۱۳|dead-url = yes}}</ref>

=== راه حل شبکه‌های شبکه عصبی ===
مسئلهٔ سفر اسب با یک [[شبکه عصبی|شبکهٔ عصبی]] نیز قابل حل است.<ref>Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." ''Neurocomputing'', 4(5):249–254, 1992.</ref> شبکه به صورتی ساخته می‌شود که هر حرکت مجاز اسب با یک [[نرون مصنوعی|نرون]] نمایش داده‌می‌شود، و به هر نرون به صورت تصادفی مقدار اولیهٔ «فعال» یا «غیرفعال» (خروجی ۱ یا ۰) داده می‌شود، که ۱ نشان‌دهندهٔ این است که نرون قسمتی از [[راه حل نهایی]] است. هر نرون یک تابع وضعیت نیز دارد (در زیر توضیح داده شده) که مقدار اولیهٔ ۰ را دارد.

وقتی شبکه اجازهٔ اجرا دارد، طبق قوانین گذار مرحله زیر، هر نرون می‌تواند وضعیت خودش، خروجی بسته به خروجی‌های خودش و همسایه‌هایش را تغییر دهد (آن‌هایی که دقیقاً به اندازهٔ یک حرکت با اسب فاصله دارند).

::<math>
U_{t+1} (N_{i,j}) = U_t(N_{i,j}) + 2 - \sum_{N \in G(N_{i,j})} V_t(N)
</math>

::<math>
V_{t+1} (N_{i,j}) = \left\{
\begin{array}{ll}
1 & \mbox{if}\,\, U_{t+1}(N_{i,j})> 3\\
0 & \mbox{if}\,\, U_{t+1}(N_{i,j}) <0\\
V_t(N_{i,j}) & \mbox{otherwise},
\end{array} \right.
</math>

که <math>t</math> نشان‌دهندهٔ وقفه‌های مجزای زمان، <math>U(N_{i,j})</math> وضعیت نرونی که خانهٔ <math>i</math> را به خانهٔ <math>j</math> وصل می‌کند، <math>V(N_{i,j})</math> خروجی نرونِ از <math>i</math> تا <math>j</math> و <math>G(N_{i,j})</math> مجموعه‌ای از همسایه‌های نرون است.

گرچه ممکن است [[سری واگرا]] باشد، اما شبکه باید در نهایت همگرا شود که این هنگامی رخ می‌دهد که هیچ نرونی وضعیتش را از زمان <math>t</math> تا <math>t+1</math> تغییر ندهد. هنگامی که شبکه همگرا می‌شود، شبکه یا یک سفر اسب یا یک سری از دو یا بیش‌تر از دورهای مستقل در همان صفحه را رمز می‌کند.

=== قانون وارنزدروف ===
{{Chess diagram
| tleft
|
|=
 ۸ | | | | | | | | |=
 ۷ | | | | | | | | |=
 6 |x3| |x7| | | | | |=
 5 | | | |x7| | | | |=
 4 | |nl| | | | | | |=
 3 | | | |x7| | | | |=
 2 |x2| |x5| | | | | |=
 ۱ | | | | | | | | |=
  a b c d e f g h
|یک نمایش از قانون وارنزدروف. هر خانه حاوی یک عدد صحیح است که بیان‌گر تعداد حرکاتی است که اسب می‌تواند از ان خانه انجام دهد. در این صورت، قانون به ما می‌گوید به خانه‌ای برویم که کوچک‌ترین عدد صحیح در آن قرار دارد، یعنی ۲.
}}

قانون وارنزدروف یک شیوهٔ ابتکاری برای پیدا کردن یک سفر اسب است. ما اسب را طوری حرکت می‌دهیم که همیشه به خانه‌ای برسم که طی آن مسیر اسب «کم‌ترین» حرکات رو به جلو را داشته باشد. هنگام محاسبهٔ تعداد حرکات رو به جلو برای هر خانهٔ موردنظر، حرکت‌هایی را که خانه‌های قبلاً پیموده‌شده‌اند را می‌پیمایند، نمی‌شماریم. هنگامی که تعداد حرکت‌های رو به جلو برابر است، ممکن است بیش‌تر از یک انتخاب داشته‌باشیم؛ روش‌های گوناگونی برای انتخاب مسیر مناسب وجود دارد. از جملهٔ آن‌ها می‌توان به روشی که توسط پل<ref name="pohl"/> و روشی دیگر که به وسیلهٔ اسکیرل و کول<ref>{{cite web|url=https://github.com/douglassquirrel/warnsdorff/blob/master/5_Squirrel96.pdf?raw=true |title=A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards |accessdate=2011-08-21 |last=Squirrel |first=Douglas |coauthors=Cull, P. |year=1996}}</ref> ابداع شد اشاره کرد.

این قانون همچنین ممکن است به‌طور کلّی برای هر گرافی به کار رود. در ... هر حرکت به رأس مجاور با کم‌ترین [[درجه|درجه (گراف)]] انجام می‌شود. گرچه [[مسیر همیلتونی|مسئلهٔ مسیر همیلتونی]] به‌طور کلّی [[ان‌پی سخت]] است، امّا در بسیاری از گراف‌ها این شیوهٔ ابتکاری قادر است یک راه حل در [[زمان اجرای خطی|زمان خطی]] پیدا کند.<ref name="pohl">{{cite journal|last = Pohl|first = Ira|title = A method for finding Hamilton paths and Knight's tours|journal = Communications of the ACM|volume = 10|issue = 7|date = July 1967|pages = 446–449|url =http://portal.acm.org/citation.cfm?id=363463|doi = 10.1145/363427.363463}}</ref> سفر اسب یک مورد خاص است.<ref name="alwan-waters">{{cite conference| first=Karla |last=Alwan| coauthors=Waters, K.| title=Finding Re-entrant Knight's Tours on N-by-M Boards|conference=ACM Southeast Regional Conference| publisher=[[Association for Computing Machinery|ACM]]| location=New York, New York| pages=377–382| year=1992| url=http://portal.acm.org/citation.cfm?id=503806| format=[[PDF]]| accessdate=2008-10-28| doi = 10.1145/503720.503806}}</ref>

== منابع ==
{{پانویس|۲}}

== پیوند به بیرون ==
{{ویکی‌انبار-رده|Knight's Tours}}
* [https://web.archive.org/web/20050420054300/http://web.telia.com/~u85905224/knight/eWarnsd.htm Warnsdorff's Rule] and [https://web.archive.org/web/20060504070805/http://web.telia.com/~u85905224/knight/bWarnsd.htm its efficiency] from Warnsdorff's Rule Web Page
* {{cite web
|first1=Dan
|last1=Thomasson
|url=http://www.borderschess.org/KnightTour.htm
|title=The knight's tour
|accessdate=۲۴ ژوئن ۲۰۱۳
|archiveurl=https://web.archive.org/web/20051219005826/http://www.borderschess.org/KnightTour.htm
|archivedate=۱۹ دسامبر ۲۰۰۵
|dead-url=yes
}}
* [http://www.mayhematics.com/t/t.htm Knight's tour notes]
* [http://www.kongregate.com/games/Exportgold/a-knights-tour Knight's Tour Flash Game]
* {{OEIS|A001230}}
* [http://warnsdorff.com warnsdorff.com] - Page devoted to Warnsdorff's Rule

=== پیاده‌سازی‌ها ===
* [http://demonstrations.wolfram.com/TheKnightsTour/ The Knight's Tour] by Jay Warendorff, [[Wolfram Demonstrations Project]]
* {{cite web
|first1=Piyush
|last1=Kumar
|url=http://www.compgeom.com/~piyush/teach/3330/homeworks/knightour.cpp
|title=A Simple backtracking implementation in C++
|access-date=24 ژوئن 2013
|archive-date=14 نوامبر 2013
|archive-url=https://web.archive.org/web/20131114171635/http://www.compgeom.com/~piyush/teach/3330/homeworks/knightour.cpp
}}
* {{cite web
|first1=Kym
|last1=Horsell
|url=http://junk.kymhorsell.com/knight.html
|title=A Simple implementation in standard Prolog
|accessdate=۲۴ ژوئن ۲۰۱۳
|archiveurl=https://web.archive.org/web/20120309014406/http://junk.kymhorsell.com/knight.html
|archivedate=۹ مارس ۲۰۱۲
|dead-url=yes
}}
* [https://web.archive.org/web/20170926064233/http://knightstour.co.uk/ An implementation in C#]
* [http://dmitrybrant.com/knights-tour Knight's Tours Using a Neural Network] Program that creates tours using a neural network, plus gallery of images.
* [http://www.brainbashers.com/knight An interactive version in JavaScript] {{Webarchive|url=https://web.archive.org/web/20160305173050/http://brainbashers.com/knight |date=5 مارس 2016 }}
* [http://www.breve.cz/jquery/jknight.php Knight's Tour in form of jQuery plugin]
* [https://play.google.com/store/apps/details?id=com.brodski.android.knightraid Knight Raid for OS Android]
* [https://web.archive.org/web/20130713111800/http://equites.timepit.eu/ An implementation in Scala]
* [http://openlibrary.org/books/OL15157004M/Book_of_computer_puzzles/ An implementation in BBC BASIC]

[[رده:الگوریتم‌های گراف]]
[[رده:مسئله‌های ریاضی]]
[[رده:مسئله‌های ریاضی شطرنج]]