سفر اسب به دنبالهای از حرکات یک مهرهٔ اسب در یک صفحهٔ شطرنج گفته میشود به طوری که از هر خانه دقیقاً یک بار بگذرد. اگر اسب به خانهای برسد که از ابتدای سفر از آن گذشتهاست، سفر بسته است. در غیر این صورت، سفر باز است. تعداد دقیق سفرها در یک صفحهٔ شطرنج ۸×۸ هنوز مشخص نیست.
مسئلهٔ سفر اسب یک مسئلهٔ ریاضیات شطرنجی برای پیدا کردن یک سفر اسب است. ساخت یک برنامه برای پیدا کردن یک سفر اسب یک مسئلهٔ رایج برای دانشجویان علوم کامپیوتر است.[۱]
در این مطلب، قرار هست با مسئلهٔ سفر اسب و «قانون وارنزدروف» آشنا شیم و چند نمونه از حل این مسئله با زبان های مختلف رو ببینیم که سعی کردیم تا حد امکان داینامیک نوشته شه و با موقعیت های مختلف اسب سازگار باشه.
کل ماجرا به این شکل هست که اول میایم و هشت تا حالت معمولای که اسب میتونه حرکت کنه رو حساب میکنیم و طبق شرط های زیر، فیلترشون میکنیم :
حالا که تعداد حرکاتی که اسب میتونه حرکت کنه رو بدست آوردیم، باید بهترین حرکت رو برای اسب انتخاب کنیم، طبق قانون وارنزدروف بهترین حرکت رفتن به خونهای هست که کمترین تعداد حرکات رو داره ، برای مثال در عکس زیر باید به خونهای رفت که تعداد حرکاتش "۲" هست. (هر دفعه که اسب حرکت میکنه میایم و تعداد حرکات قابل انجام خونه ها رو آپدیت میکنیم)
با این کار، براساس قانون وارنزدروف احتمال اینکه اسب جایی به بنبست برخورد کنه خیلی کمتر هست.
حالا همین کار رو دوباره و دوباره انجام میدیم تا اسب تمام خونه هارو طی کنه و مشکل حل شه، میتونیم این فرایند رو توی یک حلقه قرار بدیم و تا زمانی که تموم نشده حلقه ادامه داشته باشه.