MahdiyarGHD
خواندن ۲ دقیقه·۳ سال پیش

حل مشکل «سفر اسب» | Knight's tour

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


در این مطلب، قرار هست با مسئلهٔ سفر اسب و «قانون وارنزدروف» آشنا شیم و چند نمونه از حل این مسئله با زبان های مختلف رو ببینیم که سعی کردیم تا حد امکان داینامیک نوشته شه و با موقعیت های مختلف اسب سازگار باشه.


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



کل ماجرا به این‌ شکل هست که اول میایم و هشت تا حالت معمول‌ای که اسب می‌تونه حرکت کنه رو حساب می‌کنیم و طبق شرط های زیر، فیلترشون می‌کنیم :

  • اسب قبلا روی اون خونه نرفته باشه
  • از محدوده تخته خارج نباشه
  • خونه هایی که تعداد حرکتاشون صفر هست رو حذف می‌کنیم ( هر خانه حاوی یک عدد صحیح است که بیان‌گر تعداد حرکاتی است که اسب می‌تواند از ان خانه انجام دهد. )

حالا که تعداد حرکاتی که اسب می‌تونه حرکت کنه رو بدست آوردیم، باید بهترین حرکت رو برای اسب انتخاب کنیم، طبق قانون وارنزدروف بهترین حرکت رفتن به خونه‌ای هست که کمترین تعداد حرکات رو داره ، برای مثال در عکس زیر باید به خونه‌ای رفت که تعداد حرکاتش "۲" هست. (هر دفعه که اسب حرکت می‌کنه میایم و تعداد حرکات قابل انجام خونه ها رو آپدیت می‌کنیم)

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

حالا همین کار رو دوباره و دوباره انجام میدیم تا اسب تمام خونه هارو طی کنه و مشکل حل شه، می‌تونیم این فرایند رو توی یک حلقه قرار بدیم و تا زمانی که تموم نشده حلقه ادامه داشته باشه.






شاید از این پست‌ها خوشتان بیاید