الگوریتم سورس کد مسئله وزیر وزیر

این خام میباشد میتوان نام مشخصات خودتون اونو ارائه بدید

مساله هشت وزیر جمله مسائل پرمخاطب مباحث طراحی الگوریتم است. ۸  مهره وزیر رو روی صفحه شطرنج چنان بچینید نتونن همدیگه رو تهدید کنن.

برای افرادی بازی شطرنج آشنایی ندارن:

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

مساله هشت وزیر  ما مساله رو حالت کلی نظر میگیریم. یعنی زمانی ابعاد شطرنج n n تعداد مهره n هستش. ( n > 3 ) روشهای مختلفی پیدا کردن جواب وجود داره. یکی این روشها چیدن تصادفی مهره روی شطرنجه! عبارت دیگه n مهره رو صورت تصادفی خانه مختلف قرار میدیم بررسی میکنیم آیا شرط مساله رو برآورده میکنن نه؟ این روش بسیار سریع ما رو جواب میرسونه. اما ایرادی داره نمی شه مطمئن بود بشه همه حالتهای چینش دست پیدا کرد. 8 8 شطرنج این مساله جواب مختلف داره. شما ممکنه روش تصادفی رو هزار بار کار ببرید، اما نتونید همه حالت ممکنه رو دست بیارید. این روش زمانی مفیده پیدا کردن یه جواب ما کافی باشه.

در این دسته روشها مهره رو یکی یکی صورت بازگشتی روی طوری میچینیم مطمئن باشیم مهره قبلی تداخل نداره شرط مساله برآورده میشه. معمولا سطر اول شروع میکنیم قرار دادن مهره ها. پر واضحه هر سطر فقط میتونه یه مهره رو تو خودش جا بده. مهره سطر دوم رو طوری قرار میدیم توسط مهره سطر اول تهدید نشه. این کار خانه مختلفی سطر رو میشه انتخاب کرد. نظم داشتن کارهامون فرض میکنیم همیشه انتخاب خانه سمت چپ سطر شروع میشه. عبارت دیگه شروع سمت چپ سطر اولین خانه شرط رو برآورده کنه انتخاب میکنیم. همین ترتیب سطرهای بعدی رو میچینیم. اگر سطری رسیدیم اساس چیدمان سطرهای قبلی هیچ خانه امنی مهره وجود نداشت ( یعنی همه خانه توسط مهره قبلی تهدید میشدن ) یه مرحله عقب میگردیم مهره سطر قبل رو جابجا میکنیم. این کار حرکت مهره اولین خانه سمت چپ موقعیت فعلی شرط رو برآورده کنه، انجام میشه. ادامه دادن این روال جابجا کردن مهره صورت منظم بازگشتی تمامی حالتهای ممکنه دست مییان.

برای پیاده سازی چنین الگوریتمی تشخیص اینکه خانه هایی سطر امن هستن روشهای مختلفی وجود داره. ساده ترینشون اینه هر بار تمامی خانه هایی رو امکان تهدید شدن اونها وجود داره بررسی کنیم قرار نداشتن مهره وزیر اونها مطمئن باشیم. اما این روش اصلا کارا بهینه نیست.

روش دیگه تعریف کردن شطرنج صورت یه آرایه n n هستش خونه امن امن علامتگذاری مشخص میشن. هر بار مهره رو قرار میگیره تمام خونه هایی توسط این مهره تهدید میشن صورت امن علامتگذاری میشن. این ترتیب میشه فهمید هر خونه توجه چینش مهره قبلی امن هست نه؟ اما این روش معایبی داره باعث میشه روش سوم رجوع کنیم. آشنایی این معایب کافیه سعی کنید برنامه رو بنویسید!

در روش سوم من ازش استفاده کردم، علامتگذاری خانه امن امن شیوه دیگه بهره میبریم. این ترتیب اقطار راست چپ، چپ راست ستونها شماره هایی مشخص میشن کار علامتگذاری رو بسیار ساده میکنن. این روش شک کاراترین روشهای رسیدن جواب مساله ماست. سرعت اجرای بالایی داره حافظه مصرفی بسیار کم!

کدی زبان ++C این مساله نوشته شده استفاده روش سوم تعداد جوابهای ممکن – نه خود جوابها – مقادیر مختلف n رو مشخص میکنه. مثال اگر n رو 8 وارد کنید خروجی برنامه خواهد بود. توصیه میکنم nهای بزرگ برنامه رو امتحان نکنید! اگر n رو وارد کنید بعد گذشتن زمان زیادی عدد 14772512 روی نمایش چاپ میشه. یعنی شطرنج حدود ۱۵ میلیون حالت مختلف چیدمان صحیح وجود داره!!