knight tour

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

knight tour

chess

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

 

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

knight-move

knight-move-chess

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

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

move-of-knight

move-of-knight

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

 

 

 

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۱۵ دیدگاه

پاسخ دهید

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