سفر اسب

سفر اسب به دنباله ای از حرکات یک مهرهٔ اسب در یک صفحهٔ شطرنج گفته می شود به طوری که از هر خانه دقیقاً یک بار بگذرد. اگر اسب به خانه ای برسد که از ابتدای سفر از آن گذشته است، سفر بسته است. در غیر این صورت، سفر باز است. تعداد دقیق سفرها در یک صفحهٔ شطرنج ۸×۸ هنوز مشخص نیست.
مسئلهٔ سفر اسب یک مسئلهٔ ریاضیات شطرنجی برای پیدا کردن یک سفر اسب است. ساخت یک برنامه برای پیدا کردن یک سفر اسب یک مسئلهٔ رایج برای دانشجویان علوم کامپیوتر است. [ ۱] انواع مختلف مسئلهٔ سفر اسب به خاطر تفاوت در اندازهٔ صفحه های شطرنج و هم چنین صفحه های غیرمربعی است.
مسئلهٔ سفر اسب نمونه ای از مسئلهٔ کلّی تر مسیر همیلتونی در نظریهٔ گراف است. مشابهاً، مسئلهٔ پیدا کردن یک سفر بسته برای اسب، یک نمونه از مسئلهٔ دور همیلتونی است. برخلاف مسئلهٔ مسیر همیلتونی، مسئلهٔ سفر اسب می تواند در زمان خطی حل شود. [ ۲]
در یک صفحهٔ ۸×۸، دقیقاً ۲۶٬۵۳۴٬۷۲۸٬۸۲۱٬۰۶۴ سفر بستهٔ جهت دار وجود دارد. ( برای مثال دو سفر در طول مسیر یکسان که دارای جهت های مخالف هستند جداگانه شمارش می شوند، چرخش ها و تقارن ها هم به همین صورت هستند ) [ ۳] [ ۴] [ ۵] تعداد سفرهای بستهٔ غیرجهت دار نصف این عدد است زیرا هر سفر می تواند در جهت عکس نیز به حساب بیاید. ۹٬۸۶۲ سفر بستهٔ غیرجهت دار در یک صفحهٔ ۶×۶ وجود دارد. [ ۶]
شْوِنْک[ ۷] ثابت کرد برای هر صفحهٔ m×n که در آن m کم تر یا مساوی n است، یک سفر بستهٔ اسب همیشه وجود دارد مگر این که حداقل یکی از این شروط برقرار باشند:
• m و n هر دو فرد باشند. n مساوی ۱ نباشد.
• m = ۱، ۲ یا ۴. n مساوی ۱ نباشد.
• m = ۳ و n = ۴، ۶ یا ۸.
کول و د کورتینز اثبات کردند در هر صفحهٔ مربعی که کوچک ترین بعد آن حداقل ۵ باشد، یک سفر ( احتمالاً باز ) اسب وجود دارد. [ ۸]
راه های مختلفی برای پیدا کردن یک سفر اسب در یک صفحه با یک کامپیوتر وجود دارد. برخی از این راه ها الگوریتم هستند در حالی که بقیه ابتکاری هستند.
یک جستجوی جامع برای یک سفر اسب برای تمامی صفحه ها غیر از صفحه های کوچک غیرعملی است. برای مثال، در یک صفحهٔ ۸x۸ تقریباً ۴x10۵۱ دنبالهٔ حرکت ممکن وجود دارد[ ۹] و انجام عملیات روی چنین مجموعهٔ بزرگی فرای ظرفیت کامپیوترهای امروزی ( یا شبکه هایی از کامپیوترها ) است.