تبلیغات


knight tour

برنامه حل سوال گردش اسب – knight tour

اشتراک گذاری
Share on FacebookTweet about this on TwitterShare on Google+Share on LinkedInPin on PinterestPrint this pageEmail this to someone

کد برنامه نویسی مسئله گردش اسب - knight tour

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

 

برنامه حرکت اسبی یا همان knight tour. اسب می تواند حرکاتی به شکل  L  انجام دهد(دو خانه در یک جهت و سپس یک خانه در جهت  عمود بر جهت اول )به این ترتیب یک اسب از خانه ای در وسط صفحه خالی شطرنج می تواند هر یک از هشت حرکت مختلف را که در شکل می بینید انجام دهد.

کد برنامه نویسی مسئله گردش اسب - knight tour

knight-move-chess

۱ )      یک صفحه شطرنج ۸*۸ رسم کنید و سعی کنید  مساله گردش اسب را با دست حل کنید . در اولین خانه ای که قرار می گیرید عدد ۱و در دومین خانه عدد ۲ و در سومین خانه عدد ۳ و…را بنویسید . پیش از آغاز گردش مسافتی را که می تواند طی کند تخمین بزنید؟

۲)      برنامه ای بنویسید که اسب را در یک صفحه شطرنج گردش دهد . این صفحه را با یک آرایه دواندیسی نمایش دهید در ابتدا تمام خانه ها را برابر ۰ قرار دهید .هر یک از هشت حرکت ممکن برحسب  هر دو جز افقی و عمودی آن ها توصیف می شوند    مثلا حرکتی از نوع صفر به صورتی که در شکل نشان داده شده شامل یک حرکت افقی به سمت راست به اندازه دو خانه  ویک حرکت عمودی به بالا به اندازه یک خانه است  این حرکت ها را می توان با ۲ آرایه ۸ تایی نشان داد که در شکل آمده اند.

کد برنامه نویسی مسئله گردش اسب - knight tour

move-of-knight

 

برای نمایش ردیف و ستون محل جاری اسب از متغییر های currentrow ,currentcolumn   استفاده می کنیم .

شمارنده ای در نظر بگیرید که از ۱ تا ۶۴ تغییر می کند  و در آن تعداد حرکاتی که اسب انجام داده  ثبت کنید.

اگر توجه کرده باشید خانه هایی که در گوشه هستند دردسر ساز ترند برای همین خانه ها را در جه بندی می کنیم و برای گوشه ها اهمیت بیشتری قایل می شویم . این درجه بندی را در شکل می بینید .

کد برنامه نویسی مسئله گردش اسب - knight tour

امتیاز خانه های شطرنج

ابتدا سعی کنید خانه هایی که شماره کوچک تری دارند پر کنید (اهمیت بیشتری دارد)زیرا احتمال موفقیت بالا می رود .

در برنامه نوشته شده   تابع    reset_array  ارزش های از پیش تعیین شده را درون آرایه می ریزد .

تابع show آرایه دوبعدی را نمایش می دهد.

تابع check_around خانه های اطراف خانه ای را که در آن هستیم چک می کند و خانه ای را که اهمیت بیشتری دارد انتخاب می کند و اگر از خانه هایی که ارزش یکسان دارند چند تا داشتیم به طور رندم انتخاب می کند و شماره عملی را که برای رفتن به آن خانه لازم است برمی گرداند.

تابع fill_board با استفاده از تابع reset_array   نقطه ای که اسب درش است را به نقطه ای که reset_array   گفته می برد.

در تابع  main()   تابع fill_board  چند بار فراخوانی می شود تا به جواب مطلوب یعنی پر کردن تمام خانه های جدول برسیم.

این هم از کد برنامه knight tour   مستقیم سراغ کد نیایید خودتان فکر کنید.

کد برنامه نویسی مسئله گردش اسب - knight tour

نمایی از اجرای برنامه

اینم کد برنامه:

 

 

 

 

 

 


تبلیغات:

۷ دیدگاه

  • مرسی فراوون ، داشتم دستی مساله رو حل میکردم و همش فک میکردم که بهتره اول خونه های وسط پر شه همش ، خیلی گیر کرده بودم . تشکر فراوون

  • سلام
    خیلی توضیحات الگوریتم حرکت اسب خیلی واضح و قشنگ بود ممنون.
    اگه میشه فقط با یک فانکشن بنویسید که اینقد تعداد خط برنامه نره بالا.
    ما برنامه نویسا به تنبلی شهرت داریم :)))

  • ممنون از کدی که گذاشتید، کلی گشتم تا تونستم این سایت رو پیدا کنم، رو سئو بیشتر کار کنید؛ تو صفحه دوم،سوم گوگل پیداتون کردم.
    بازهم ممنون از سایتتون.

  • با عرض سلام ، شما برنامه ی نوشته شده ی مکعب روبیک در زبان c رو دارید ؟ اگه هست امکانش هست که برام Email کنین ؟

  • آقا دمت گرم خیلی سایت خفنی زدید . کدشو با C# بنویسید خوب می شه

نظر خود را بنویسید.

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *