حل مسئله معمای 8 وزیر : بررسی جامع مسئله 8 وزیر در شطرنج ، و روشهای حل آن

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

 

در ادامه به بررسی کامل معمای هشت وزیر و روشهایی که برای حل آن کار گرفته میشود می پردازیم.

معمای هشت وزیر،  در حالت کلی تر به N وزیر معروف است یعنی تعداد وزیرها بجای 8 میتواند هر عدد N ای باشد. مثلا مسئله 4 وزیر ، 16 وزیر یا غیره.

 

چیدن 8 وزیر در صفحه شطرنج = معمای 8 وزیر

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

 

تاریخچه مسئله 8 وزیر :

این مسئله در سال ۱۸۴۸ توسط شطرنج بازی به نام Max Bezzel عنوان شد و ریاضی دانان بسیاری ازجمله Gauss و Georg Cantor بر روی این مسئله کار کرده و در نهایت آن را به n وزیر تعمیم دادند.

اولین راه حل توسط Franz Nauck در سال ۱۸۵۰ ارائه شد که به همان مسئله n وزیر تعمیم داده شد.

پس از آن Gunther راه حلی با استفاده از دترمینان ارائه داد که J.W.L. Glaisher آن را کامل نمود.

در سال ۱۹۷۹، Edsger Dijkstra Nauck این مسئله را با استفاده از الگوریتم عقب‌گرد حل کرد.

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

 

تعریف مسئله هشت وزیر یا n وزیر :

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

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

مسئله n وزیر از جمله مسائل NP در هوش مصنوعی است که روش‌های جستجوی معمولی قادر به حل آن‌ها نخواهد بود.

مطالب زیر را حتما بخوانید

دیدگاهتان را بنویسید

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