هشت وزیر،سورس کد حل مساله ۸ وزیر با الگوریتم ژنتیک در متلب

زبان برنامه نویسی: MATLAB

نمایش گرافیکی موقعیت وزیرها در صفحه ۸*۸

مسئله چند وزیر یک معماری شطرنجی و ریاضیاتی است که بر اساس آن باید n وزیر شطرنج در یک صفحه n×n شطرنج به‌گونه‌ای قرار داده شوند که هیچ‌یک زیر ضرب دیگری نباشند. با توجه به اینکه وزیر به‌صورت افقی، عمودی و اُریب حرکت می‌کند، باید هر وزیر را در طول، عرض و قطر متفاوتی قرار داد.

اولین و مشهورترین شکل این مسئله معمای هشت وزیر است که برای حل آن باید ۸ وزیر را در یک صفحهً معمولی (۸×۸) شطرنج قرار داد. این مسئله ۹۲ جواب دارد که ۱۲ جواب آن منحصر به‌فرد است یعنی بقیه جواب‌ها از تقارن جواب‌های اصلی به‌دست می‌آید.

الگوریتم ژنتیک زیر مجموعه‌ای از الگوریتم‌های تکاملی است. این الگوریتم از سیستم بیولوژی بدن الهام گرفته شده است. در این الگوریتم نیاز است که بتوانیم هر پاسخ ممکن به مسئله را در یک ساختار مناسب نمایش دهیم.

در ادامه، یک تابع نیاز است تا هر نمونه جواب (که در ساختار مناسب نمایش داده شده است) را به مقدار عددی نگاشت کند. این تابع باید میزان مناسب بودن یک پاسخ برای مسئله را نشان دهد. این تابع را اصطلاحا fitness function می‌نامند.

پس از مشخص شدن ساختار نمایش یک پاسخ در مساله و تابع ارزیابی آن، یک نسل اولیه از پاسخ‌ها تولید می‌شود و با اعمال فرآیند‌ها ژنتیک از نسل اولیه نسل‌های بعدی به وجود می‌آید و این روند تکرار می‌گردد تا پاسخ مناسب پیدا گردد.

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

پاسخ‌های بدست آمده از الگوریتم ژنتیک بهترین جواب ممکن نیست. در واقع هیچ تضمینی برای یافتن پاسخ بهینه با استفاده از این الگوریتم وجود ندارد. ولی با استفاده از این الگوریتم می‌توان به جواب‌هایی رسید که تا حد کافی مناسب باشند.

تاریخچه

این مسئله در سال ۱۸۴۸ توسط شطرنج بازی به نام Max Bezzel عنوان شد و ریاضی دانان بسیاری ازجمله کارل فریدریش گاوس بر روی این مسئله کار کرده و در نهایت آن را به n وزیر تعمیم دادند. اولین راه حل توسط Franz Nauck در سال ۱۸۵۰ ارائه شد که به همان مسئله n وزیر تعمیم داده شد. پس از آن Gunther راه حلی با استفاده از دترمینان ارائه داد که James Whitbread Lee Glaisher آن را کامل نمود. در سال ۱۹۷۹، ادسخر دیکسترا این مسئله را با استفاده از الگوریتم عقب‌گرد حل کرد.

حل مسئله

مسأله هشت وزیر دارای ۹۲ راه حل متمایز است. اگر راه حل هایی که با چرخش و یا بازتاب برهم منطبق می‌شوند به عنوان یک راه حل در نظر گرفته شوند ، پازل دارای ۱۲ راه حل خواهد بود. به این راه حل‌ها، راه حل های پایه گفته می‌شود.

صورت مسئله

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