سفر اسب

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

سفر اسب در صفحهٔ شطرنج

سفر اسب در یک صفحهٔ ۵×۵

مسئلهٔ سفر اسب یک مسئلهٔ ریاضیات شطرنجی برای پیدا کردن یک سفر اسب است. ساخت یک برنامه برای پیدا کردن یک سفر اسب یک مسئلهٔ رایج برای دانشجویان علوم کامپیوتر است. انواع مختلف مسئلهٔ سفر اسب به خاطر تفاوت در اندازهٔ صفحه‌های شطرنج و هم‌چنین صفحه‌های غیرمربعی است.

نظریه

گراف اسب تمام مسیرهای ممکن برای یک سفر اسب را در یک صفحهٔ شطرنج استاندارد ۸×۸ نشان می‌دهد. عددهای هر رأس بیان‌گر تعداد حرکات ممکن که می‌توانند از آن رأس شروع شوند هستند.

مسئلهٔ سفر اسب نمونه‌ای از مسئلهٔ کلّی‌تر مسیر همیلتونی در نظریهٔ گراف است. مشابهاً، مسئلهٔ پیدا کردن یک سفر بسته برای اسب، یک نمونه از مسئلهٔ دور همیلتونی است. برخلاف مسئلهٔ مسیر همیلتونی، مسئلهٔ سفر اسب می‌تواند در زمان خطی حل شود.

تعداد سفرهای بسته

در یک صفحهٔ ۸×۸، دقیقاً ۲۶٬۵۳۴٬۷۲۸٬۸۲۱٬۰۶۴ سفر بستهٔ جهت‌دار وجود دارد. (برای مثال دو سفر در طول مسیر یکسان که دارای جهت‌های مخالف هستند جداگانه شمارش می‌شوند، چرخش‌ها و تقارن‌ها هم به همین صورت هستند) تعداد سفرهای بستهٔ غیرجهت‌دار نصف این عدد است زیرا هر سفر می‌تواند در جهت عکس نیز به‌حساب‌بیاید. ۹٬۸۶۲ سفر بستهٔ غیرجهت‌دار در یک صفحهٔ ۶×۶ وجود دارد.

کدام صفحه‌ها دارای سفر هستند

شْوِنْک ثابت کرد برای هر صفحهٔ m×n که در آن m کم‌تر یا مساوی n است، یک سفر بستهٔ اسب همیشه وجود دارد مگر این که حداقل یکی از این شروط برقرار باشند:

m و n هر دو فرد باشند. n مساوی ۱ نباشد.
m = ۱، ۲ یا ۴. n مساوی ۱ نباشد.
m = ۳ و n = ۴، ۶ یا ۸.

کول و د کورتینز اثبات کردند در هر صفحهٔ مربعی که کوچک‌ترین بعد آن حداقل ۵ باشد، یک سفر (احتمالاً باز) اسب وجود دارد.

پیدا کردن سفرها با کامپیوتر

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

الگوریتم‌های جامع

یک جستجوی جامع برای یک سفر اسب برای تمامی صفحه‌ها غیر از صفحه‌های کوچک غیرعملی است. برای مثال، در یک صفحهٔ ۸x۸ تقریباً ۴x10 دنبالهٔ حرکت ممکن وجود دارد و انجام عملیات روی چنین مجموعهٔ بزرگی فرای ظرفیت کامپیوترهای امروزی (یا شبکه‌هایی از کامپیوترها) است.

الگوریتم‌های تقسیم و حل

با تقسیم صفحه به قسمت‌های کوچک‌تر، ساخت سفر در هر قسمت و وصل کردن قسمت‌ها به یکدیگر، می‌توان در بیش‌تر صفحه‌های مربعی در زمان چندجمله‌ای سفرها را پیدا کرد.

راه حل شبکه‌های شبکه عصبی

مسئلهٔ سفر اسب با یک شبکهٔ عصبی نیز قابل حل است. شبکه به صورتی ساخته می‌شود که هر حرکت مجاز اسب با یک نرون نمایش داده‌می‌شود، و به هر نرون به صورت تصادفی مقدار اولیهٔ «فعال» یا «غیرفعال» (خروجی ۱ یا ۰) داده می‌شود، که ۱ نشان‌دهندهٔ این است که نرون قسمتی از راه حل نهایی است. هر نرون یک تابع وضعیت نیز دارد (در زیر توضیح داده شده) که مقدار اولیهٔ ۰ را دارد.

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

U_{t+1}(N_{i,j})=U_{t}(N_{i,j})+2-\sum _{N\in G(N_{i,j})}V_{t}(N)

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.

که $t$

نشان‌دهندهٔ وقفه‌های مجزای زمان،

U(N_{i,j})

وضعیت نرونی که خانهٔ

i

را به خانهٔ

j

وصل می‌کند،

V(N_{i,j})

خروجی نرونِ از

i

تا

j

و

G(N_{i,j})

مجموعه‌ای از همسایه‌های نرون است.

گرچه ممکن است سری واگرا باشد، اما شبکه باید در نهایت همگرا شود که این هنگامی رخ می‌دهد که هیچ نرونی وضعیتش را از زمان $t$

تا

t+1

تغییر ندهد. هنگامی که شبکه همگرا می‌شود، شبکه یا یک سفر اسب یا یک سری از دو یا بیش‌تر از دورهای مستقل در همان صفحه را رمز می‌کند.

قانون وارنزدروف

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

یک نمایش از قانون وارنزدروف. هر خانه حاوی یک عدد صحیح است که بیان‌گر تعداد حرکاتی است که اسب می‌تواند از ان خانه انجام دهد. در این صورت، قانون به ما می‌گوید به خانه‌ای برویم که کوچک‌ترین عدد صحیح در آن قرار دارد، یعنی ۲.

قانون وارنزدروف یک شیوهٔ ابتکاری برای پیدا کردن یک سفر اسب است. ما اسب را طوری حرکت می‌دهیم که همیشه به خانه‌ای برسم که طی آن مسیر اسب «کم‌ترین» حرکات رو به جلو را داشته باشد. هنگام محاسبهٔ تعداد حرکات رو به جلو برای هر خانهٔ موردنظر، حرکت‌هایی را که خانه‌های قبلاً پیموده‌شده‌اند را می‌پیمایند، نمی‌شماریم. هنگامی که تعداد حرکت‌های رو به جلو برابر است، ممکن است بیش‌تر از یک انتخاب داشته‌باشیم؛ روش‌های گوناگونی برای انتخاب مسیر مناسب وجود دارد. از جملهٔ آن‌ها می‌توان به روشی که توسط پل و روشی دیگر که به وسیلهٔ اسکیرل و کول ابداع شد اشاره کرد.

این قانون همچنین ممکن است به‌طور کلّی برای هر گرافی به کار رود. در ... هر حرکت به رأس مجاور با کم‌ترین درجه (گراف) انجام می‌شود. گرچه مسئلهٔ مسیر همیلتونی به‌طور کلّی ان‌پی سخت است، امّا در بسیاری از گراف‌ها این شیوهٔ ابتکاری قادر است یک راه حل در زمان خطی پیدا کند. سفر اسب یک مورد خاص است.

منابع

↑ 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.; Hindrichs, T.; Morsy, H. & Wegener, I. (1994). "Solution of the Knight's Hamiltonian Path Problem on Chessboards". Discrete Applied Mathematics. 50 (2): 125–134. doi:10.1016/0166-218X(92)00170-Q.
↑ 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. 3 (1): 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.
↑ 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 24 June 2013.
↑ Wegener, I. (2000). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-89871-458-3.
↑ Weisstein, Eric W. "Knight's Tour". MathWorld.
↑ Allen J. Schwenk (1991). "Which Rectangular Chessboards Have a Knight's Tour?". Mathematics Magazine: 325–332.
↑ Cull, Paul. "Knight's Tour Revisited" (PDF). Fibonacci Quarterly. Retrieved 5 August 2012.
↑ "Enumerating the Knight's Tour".
↑ Cull, P. (June 1978). "Knight's Tour Revisited". Fibonacci Quarterly. 16: 276–285.
↑ Parberry, Ian (1997). "An Efficient Algorithm for the Knight's Tour Problem" (PDF). Discrete Applied Mathematics. 73: 251–260. doi:10.1016/S0166-218X(96)00010-8. Archived from the original (PDF) on 27 September 2013. Retrieved 24 June 2013.
↑ Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.
↑ Pohl, Ira (July 1967). "A method for finding Hamilton paths and Knight's tours". Communications of the ACM. 10 (7): 446–449. doi:10.1145/363427.363463.
↑ Squirrel, Douglas (1996). "A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards" (PDF). Retrieved 2011-08-21.
↑ Alwan, Karla (1992). Finding Re-entrant Knight's Tours on N-by-M Boards (PDF). ACM Southeast Regional Conference. New York, New York: ACM. pp. 377–382. doi:10.1145/503720.503806. Retrieved 2008-10-28.

پیوند به بیرون

Warnsdorff's Rule and its efficiency from Warnsdorff's Rule Web Page
Thomasson, Dan. "The knight's tour". Archived from the original on 19 December 2005. Retrieved 24 June 2013.
Knight's tour notes
Knight's Tour Flash Game
(دنباله A001230 در OEIS)
warnsdorff.com - Page devoted to Warnsdorff's Rule

پیاده‌سازی‌ها

The Knight's Tour by Jay Warendorff, Wolfram Demonstrations Project
Kumar, Piyush. "A Simple backtracking implementation in C++". Archived from the original on 14 November 2013. Retrieved 24 June 2013.
Horsell, Kym. "A Simple implementation in standard Prolog". Archived from the original on 9 March 2012. Retrieved 24 June 2013.
An implementation in C#
Knight's Tours Using a Neural Network Program that creates tours using a neural network, plus gallery of images.
An interactive version in JavaScript بایگانی‌شده در ۵ مارس ۲۰۱۶ توسط Wayback Machine
Knight's Tour in form of jQuery plugin
Knight Raid for OS Android
An implementation in Scala
An implementation in BBC BASIC

[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. 50 (2): 125–134. doi:10.1016/0166-218X(92)00170-Q.

[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. 3 (1): 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 (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 24 June 2013.

[5] Wegener, I. (2000). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-89871-458-3.

[6] Weisstein, Eric W. "Knight's Tour". MathWorld.

[7] Allen J. Schwenk (1991). "Which Rectangular Chessboards Have a Knight's Tour?". Mathematics Magazine: 325–332.

[8] Cull, Paul. "Knight's Tour Revisited" (PDF). Fibonacci Quarterly. Retrieved 5 August 2012.

[9] "Enumerating the Knight's Tour".

[10] Cull, P. (June 1978). "Knight's Tour Revisited". Fibonacci Quarterly. 16: 276–285.

[11] Parberry, Ian (1997). "An Efficient Algorithm for the Knight's Tour Problem" (PDF). Discrete Applied Mathematics. 73: 251–260. doi:10.1016/S0166-218X(96)00010-8. Archived from the original (PDF) on 27 September 2013. Retrieved 24 June 2013.

[12] Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.

[pohl-13] Pohl, Ira (July 1967). "A method for finding Hamilton paths and Knight's tours". Communications of the ACM. 10 (7): 446–449. doi:10.1145/363427.363463.

[14] Squirrel, Douglas (1996). "A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards" (PDF). Retrieved 2011-08-21.

[alwan-waters-15] Alwan, Karla (1992). Finding Re-entrant Knight's Tours on N-by-M Boards (PDF). ACM Southeast Regional Conference. New York, New York: ACM. pp. 377–382. doi:10.1145/503720.503806. Retrieved 2008-10-28.