مسئله چند وزیر

مسئله چند وزیر یک معمای شطرنجی و ریاضیاتی است که بر اساس آن باید n وزیر شطرنج در یک صفحه n×n شطرنج به گونه ای قرار داده شوند که هیچ یک زیر ضرب دیگری نباشند. با توجه به اینکه وزیر به صورت افقی، عمودی و اُریب حرکت می کند، باید هر وزیر را در طول، عرض و قطر متفاوتی قرار داد.
اولین و مشهورترین شکل این مسئله معمای هشت وزیر است که برای حل آن باید ۸ وزیر را در یک صفحهً معمولی ( ۸×۸ ) شطرنج قرار داد. این مسئله ۹۲ جواب دارد که ۱۲ جواب آن منحصر به فرد است یعنی بقیه جواب ها از تقارن جواب های اصلی به دست می آید. مسئله n وزیر در صورتی جواب دارد که n مساوی ۱ یا بیشتر از ۳ باشد. یعنی مسئله دو وزیر و سه وزیر راه حلی ندارند.
این مسئله در سال ۱۸۴۸ توسط شطرنج بازی به نام Max Bezzel عنوان شد و ریاضی دانان بسیاری ازجمله کارل فریدریش گاوس بر روی این مسئله کار کرده و در نهایت آن را به n وزیر تعمیم دادند. اولین راه حل توسط Franz Nauck در سال ۱۸۵۰ ارائه شد که به همان مسئله n وزیر تعمیم داده شد. پس از آن Gunther راه حلی با استفاده از دترمینان ارائه داد که James Whitbread Lee Glaisher آن را کامل نمود. در سال ۱۹۷۹، ادسخر دیکسترا این مسئله را با استفاده از الگوریتم عقب گرد حل کرد.
مسئله هشت وزیر دارای ۹۲ راه حل متمایز است. اگر راه حل هایی که با چرخش و یا بازتاب برهم منطبق می شوند به عنوان یک راه حل در نظر گرفته شوند ، پازل دارای ۱۲ راه حل خواهد بود. به این راه حل ها، راه حل های پایه گفته می شود. هر یک از این راه حل ها در زیر نشان داده شده است:
هدف از مسئله n وزیر، چیدن n مهره وزیر در یک صفحه شطرنج ( n*n ) است، به طوری که هیچ دو وزیری یکدیگر را گارد ندهند، یعنی هیچ دو مهره ای نباید در یک سطر، ستون یا قطر یکسان باشند. وزیر در خانه های شطرنج به صورت عرضی، طولی و قطری می تواند حرکت کند. مسئله n وزیر از جمله مسائل NP در هوش مصنوعی است که روش های جستجوی معمولی قادر به حل آن ها نخواهد بود
جدول زیر شمار راه حل های متمایز و همهٔ راه حل ها را برای جای گرفتن n وزیر بر روی صفحه n × n نشان می دهد.
شمار پاسخ های حالت شش وزیر کمتر از پنج وزیر است. فرمول دقیق و حتی تقریبی درستی برای یافتن تعداد پاسخ های این مسئله وجود ندارد. صفحه ۲۷*۲۷ بزرگترین حالت مسئله است که پاسخ های آن به طور کامل تا به حال شمرده شده است.