سفر اسب

 

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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.}$ 

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

گرچه ممکن است سری واگرا باشد، اما شبکه باید در نهایت همگرا شود که این هنگامی رخ می‌دهد که هیچ نرونی وضعیتش را از زمان ${\displaystyle t}$  تا ${\displaystyle 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

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

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

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

 

در ویکی‌انبار پرونده‌هایی دربارهٔ سفر اسب موجود است.

• 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