موضوع مقاله: مسئله چند وزیر | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله چند وزیر | مقدمه: مسئله چند وزیر یک معمای شطرنجی و ریاضیاتی است که بر اساس آن باید n وزیر شطرنج در یک صفحه n×n شطرنج به‌گونه‌ای قرار داده شوند که هیچ‌یک زیر ضرب دیگری نباشند. | ## بخش 1: مسئله چند وزیر | با توجه به اینکه وزیر به‌صورت افقی، عمودی و اُریب حرکت می‌کند، باید هر وزیر را در طول، عرض و قطر متفاوتی قرار داد. اولین و مشهورترین شکل این مسئله معمای هشت وزیر است که برای حل آن باید ۸ وزیر را در یک صفحهً معمولی (۸×۸) شطرنج قرار داد. این مسئله ۹۲ جواب دارد که ۱۲ جواب آن منحصر به‌فرد است یعنی بقیه جواب‌ها از تقارن جواب‌های اصلی به‌دست می‌آید. تاریخچه این مسئله در سال ۱۸۴۸ توسط شطرنج بازی به نام Max Bezzel عنوان شد و ریاضی دانان بسیاری ازجمله کارل فریدریش گاوس بر روی این مسئله کار کرده و در نهایت آن را به n وزیر تعمیم دادند. اگر راه حل هایی که با چرخش و یا بازتاب برهم منطبق می‌شوند به عنوان یک راه حل در نظر گرفته شوند ، پازل دارای ۱۲ راه حل خواهد بود. هر یک از این راه حل‌ها در زیر نشان داده شده است: صورت مسئله هدف از مسئله n وزیر، چیدن n مهره وزیر در یک صفحه شطرنج(n*n) است، به‌طوری‌که هیچ دو وزیری یکدیگر را گارد ندهند، یعنی هیچ دو مهره‌ای نباید در یک سطر، ستون یا قطر یکسان باشند. مسئله n وزیر از جمله مسائل NP در هوش مصنوعی است که روش‌های جستجوی معمولی قادر به حل آن‌ها نخواهد بود شمردن تعداد جواب‌ها جدول زیر شمار راه حل‌های متمایز و همهٔ راه حل‌ها را برای جای گرفتن n وزیر بر روی صفحه n × n نشان می‌دهد. تعداد وزیرهامتمایزکل۱۱۱۲۰۰۳۰۰۴۱۲۵۲۱۰۶۱۴۷۶۴۰۸۱۲۹۲۹۴۶۳۵۲۱۰۹۲۷۲۴۱۱۳۴۱۲٬۶۸۰۱۲۱٬۷۸۷۱۴٬۲۰۰۱۳۹٬۲۳۳۷۳٬۷۱۲۱۴۴۵٬۷۵۲۳۶۵٬۵۹۶۱۵۲۸۵٬۰۵۳۲٬۲۷۹٬۱۸۴۱۶۱٬۸۴۶٬۹۵۵۱۴٬۷۷۲٬۵۱۲۱۷۱۱٬۹۷۷٬۹۳۹۹۵٬۸۱۵٬۱۰۴۱۸۸۳٬۲۶۳٬۵۹۱۶۶۶٬۰۹۰٬۶۲۴۱۹۶۲۱٬۰۱۲٬۷۵۴۴٬۹۶۸٬۰۵۷٬۸۴۸۲۰۴٬۸۷۸٬۶۶۶٬۸۰۸۳۹٬۰۲۹٬۱۸۸٬۸۸۴۲۱۳۹٬۳۳۳٬۳۲۴٬۹۷۳۳۱۴٬۶۶۶٬۲۲۲٬۷۱۲۲۲۳۳۶٬۳۷۶٬۲۴۴٬۰۴۲۲٬۶۹۱٬۰۰۸٬۷۰۱٬۶۴۴۲۳۳٬۰۲۹٬۲۴۲٬۶۵۸٬۲۱۰۲۴٬۲۳۳٬۹۳۷٬۶۸۴٬۴۴۰۲۴۲۸٬۴۳۹٬۲۷۲٬۹۵۶٬۹۳۴۲۲۷٬۵۱۴٬۱۷۱٬۹۷۳٬۷۳۶۲۵۲۷۵٬۹۸۶٬۶۸۳٬۷۴۳٬۴۳۴۲٬۲۰۷٬۸۹۳٬۴۳۵٬۸۰۸٬۳۵۲۲۶۲٬۷۸۹٬۷۱۲٬۴۶۶٬۵۱۰٬۲۸۹۲۲٬۳۱۷٬۶۹۹٬۶۱۶٬۳۶۴٬۰۴۴۲۷۲۹٬۳۶۳٬۴۹۵٬۹۳۴٬۳۱۵٬۶۹۴۲۳۴٬۹۰۷٬۹۶۷٬۱۵۴٬۱۲۲٬۵۲۸ شمار پاسخ‌‌های حالت شش وزیر کمتر از پنج وزیر است. صفحه ۲۷*۲۷ بزرگترین حالت مسئله است که پاسخ‌های آن به طور کامل تا به حال شمرده شده است. روش‌های حل مسئله الگوریتم عقبگرد از تکنیک عقبگرد برای حل مسائلی استفاده می‌شود که در آن‌ها دنباله‌ای از اشیاء از یک مجموعه مشخص انتخاب می‌شود، به‌طوری‌که این دنباله، ملاکی را در بر می‌گیرد. این الگوریتم همانند جستجوی عمقی است، با این تفاوت که فرزندان یک گره فقط هنگامی ملاقات می‌شوند که گره امید بخش باشد و در آن گره حلی وجود نداشته باشد. با توجه به اینکه هیچ ۲ وزیری نباید همدیگر را گارد کنند و در یک سطر نمی‌توانند باشند، تعداد کل حالت‌ها برای n=۴ برابر ۴*۴*۴*۴=۲۵۶ است. در شطرنج یک وزیر می‌تواند به مهره‌هایی که در خانه‌های عمود یا مورب به وی قرار دارند حمله کند. یا به عبارت ریاضی، اگر ردیفها و ستونهای شطرنج را از یک تا هشت شماره‌گذاری کنیم و وزیر در خانه (i، j) قرار داشته باشد، مهره‌هایی که در خانه‌های (i، m) یا (m، j) یا (i ± m، j ± m) قرار دارند توسط وزیر تهدید می‌شوند. برای سادگی تشریح این مسئله با استفاده از روش بازگشت به عقب، فرض می‌کنیم که خانه‌های شطرنج ۴x۴ و تعداد وزیرها نیز ۴ باشد. سپس بعد از یافتن راه حل برای این مسئله ساده شده، اقدام به نوشتن الگوریتم برای مسئله اصلی می‌کنیم. | ## بخش 2: مسئله چند وزیر | مراحل جستجو برای یافتن جواب را به این صورت دنبال می‌کنیم که: وزیر اول را در ردیف اول و ستون اول قرار می‌دهیم. در ردیف دوم از اولین ستون به جلو رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در این خانه قرار می‌دهیم. همانند قبل، در ردیف سوم از اولین ستون به جلو رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید وزیران اول و دوم نباشد. پس به عقب یعنی ردیف دوم برگشته و وزیر دوم را به خانه‌ای دیگر از ردیف دوم منتقل می‌کنیم که مورد تهدید وزیر اول نباشد. همانند قبل، در ردیف چهارم به دنبال اولین خانه‌ای می‌گردیم که مورد تهدید وزیران پیشین نباشد. در ردیف دوم اولین خانه‌ای را میابیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در آن خانه قرار می‌دهیم. در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید وزیران اول و دوم نباشد و وزیر سوم را در آن خانه می‌گذاریم. حال اگر فرض کنیم که این خانه جواب نیست و به مسیر خود ادامه دهیم، احتمالاً" می‌توانیم جوابهای دیگری نیز بیابیم. \n"); do_work(0); do_work(1); } انیمیشن روش بازگشتی وسط|نمایش گرافیکی روش بازگشتی عقبگرد الگوریتم مونت کارلو از الگوریتم مونت کارلو برای برآورد کردن کارایی یک الگوریتم عقبگرد استفاده می‌شود. الگوریتم‌های مونت کارلو، احتمالی هستند، یعنی دستور اجرایی بعدی گاه به‌طور تصادفی تعیین می‌شوند. الگوریتم مونت کارلو مقدار مورد انتظار یک متغیر تصادفی را که روی یک فضای ساده تعریف می‌شود، با استفاده از مقدار میانگین آن روی نمونه تصادفی از فضای ساده بر آورد می‌کند. تضمینی وجود ندارد که این برآورد به مقدار مورد انتظار واقعی نزدیک باشد، ولی احتمال نزدیک شدن آن، با افزایش زمان در دسترس برای الگوریتم، افزایش می‌یابد. یکی از روش‌های حل این مسئله برای n>=4 یا n=1 استفاده از روش مکاشفه‌ای ( heuristic)است: 1- عدد n را بر عدد ۱۲ تقسیم کن و باقی‌مانده را یادداشت کن ۲- به ترتیب اعداد زوج ۲ تا n را در لیستی بنویس ۳- اگر باقی‌مانده ۳ یا ۹ بود، عدد ۲ را به انتهای لیست انتقال بده. ۴- به لیست اعداد فرد ۱ تا n را به ترتیب اضافه کن، اما اگر باقی‌مانده ۸ بود اعداد را دو به دو باهم عوض کند (مثلاً ۱و۳و۵و۷و۹ تبدیل به ۳و۱و۷و۵و۹ میشه) ۵- اگر باقی‌مانده ۲ بود جای ۱ و۳ را با هم عوض کن و ۵ را به انتهای لیست ببر. ۷- حال با استفاده از لیست بدست آمده وزیرها در صفحه شطرنج چیده می‌شوند، به‌طوری‌که جای وزیر ستون اول، اولین عدد لیست، جای وزیر ستون دوم، دومین عدد لیست و... این الگوریتم یک راه حل برای حل این مسئله‌است، برای بدست آوردن همه حالات از روش‌های دیگری می‌توان استفاده کرد. | ## بخش 3: مسئله چند وزیر | روش حل مسئله ۱۲ راه حل یکتا دارد که با در نظرگیری تقارن و چرخش به ۹۲ حالت قابل تبدیل است. روش‌های جستجوی محلی می‌توان به مسئله ۸ وزیر به عنوان یک مسئله بهینه‌سازی نیز نگریست که در آن هدف بهینه کردن تعداد گاردهای جفت وزیرها می‌باشد. به عنوان مثال فرض کنید در صفحه شطرنج معمولی، ۸ وزیر را به دو روش زیر قرار دهیم: 250px 250px در روش چینش سمت چپ ۳ وزیر و در روش چینش سمت راست ۴ وزیر همدیگر را گارد می‌دهند. در صورتی S* می‌تواند جواب مسئله باشد که به ازای همه جواب‌های موجود در S، S* بهینه تر از دیگر جواب‌ها باشد. در مسئله ۸ وزیر دیدیم که جوابی بهینه‌است که تعداد گاردهای جفت وزیر آن کمتر باشد. روش‌های جستجوی محلی همگی حالت‌های همسایه حالت فعلی را برای رسیدن به بهینه‌ترین جواب بررسی می‌کنند. اولین تابع میزان بهینگی جواب مسئله ارزیابی می‌کند و تابع دوم یکی از حالت‌های همسایه حالت فعلی را انتخاب می‌کند. نحوه پیاده‌سازی و طراحی الگوریتم برای انتخاب حالت همسایه در این روش‌های جستجو از اهمیت ویژه‌ای برخوردار است. به عنوان مثال برای مسئله ۸ وزیر می‌توان به شکل‌های زیر حالت‌های همسایگی را تولید کرد: ۱) دو وزیر به تصادف انتخاب شده و جای آن دو باهم عوض گردد. ۳) وزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند الگوریتم ژنتیک نحوه نمایش مسئله: می‌دانیم اگر دو وزیر در یک ستون قرار گیرند قطعاً به جواب نخواهیم رسید. برای نمایش مسئله در کروموزوم‌ها از این ویژگی استفاده کرده و به صورت زیر عمل می‌کنیم: یک آرایه تک بعدی ایجاد می‌کنیم که به تعداد ستون‌های صفحه شطرنج عنصر دارد. به عنوان مثال اگر مسئله ۸ وزیر را در نظر بگیریم، آرایه تک بعدی باید دارای ۸ عنصر باشد. فرض کنید آرایه دارای مقادیر زیر باشد: ۸ , ۷ , ۶ , ۵ , ۴ , ۳ , ۲ , ۱ مقدار ۸ در اولین عنصر آرایه گویای این مطلب است که در ستون اول صفحه شطرنج وزیری در سطر هشتم قرار داده‌ایم. تولید جمعیت اولیه: الگوریتم‌های ژنتیک ابتدا جمعیت اولیه‌ای تولید کرده و سپس سعی در بهبود بخشیدن این جمعیت دارند. برای محاسبه میزان بهینگی جواب تعداد جفت وزیرهایی را که به هم گارد می‌دهند، محاسبه می‌کنیم. برای مسئله ۸ وزیر در بدترین حالت هر وزیر با همه وزیرهای دیگر گارد می‌دهد (فرض کنید همه وزیرها در یک سطر قرار گیرند). | ## جمع‌بندی | در این حالت حداکثر تعداد جفت وزیرهایی که به همدیگر گارد می‌دهند ۲۸ جفت است: ۷ + ۶ + ۵ + ۴ +۳ + ۲ + ۱ در حالت کلی برای مسئله n وزیر حداکثر تعداد جفت وزیرهایی که به همدیگر گارد می‌دهند به صورت زیر محاسبه می‌شود: ۱+ ۲ +..