سفر اسب

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

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

نظریه

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

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

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

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

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

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

1. m و n هر دو فرد باشند. n مساوی ۱ نباشد.
2. m = ۱، ۲ یا ۴. n مساوی ۱ نباشد.
3. 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})=\{\begin{array}{cc}1& \text{if}{U}_{t+1}(N_{i,j})>3\\ 0& \text{if}{U}_{t+1}(N_{i,j})<0\\ V_t(N_{i,j})& \text{otherwise},\end{array}$

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

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

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

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

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

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

• Warnsdorff's Rule and its efficiency from Warnsdorff's Rule Web Page
• الگو:Cite web
• Knight's tour notes
• Knight's Tour Flash Game
• الگو:OEIS
• warnsdorff.com - Page devoted to Warnsdorff's Rule

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

• The Knight's Tour by Jay Warendorff, Wolfram Demonstrations Project
• الگو:Cite web
• الگو:Cite web
• 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 الگو:Webarchive
• Knight's Tour in form of jQuery plugin
• Knight Raid for OS Android
• An implementation in Scala
• An implementation in BBC BASIC