حل مساله n وزیر با الگوریتم پس گرد (Backtracking) – به زبان ساده


در این مطلب، به روش حل مساله n وزیر با الگوریتم پس گرد (Backtracking) پرداخته میشود. همچنین، کدهای پیادهسازی روش مذکور در زبانهای گوناگون، ارائه شدهاند. در بازی شطرنج، وزیر میتواند به میزان نامحدودی به طور افقی، عمودی و قطری حرکت کند. در مساله n وزیر، هدف آن است که n وزیر در یک صفحه شطرنج n×n به گونهای قرار بگیرند که هیچ یک زیر ضرب دیگری نباشد. اولین مساله n وزیر در سال ۱۸۴۸ و با عنوان مساله ۸ وزیر مطرح شد. در سال ۱۸۵۰، «فرانز نائوک» (Franz Nauck) اولین راهکار برای مساله ۸ وزیر را ارائه کرد. او، مساله 8 وزیر را به مساله n وزیر تعمیم داد که در واقع همان قرارگیری n وزیر در یک صفحه شطرنج n×n است، به صورتی که یکدیگر را تهدید نکنند. ریاضیدانان متعددی روی مساله ۸ وزیر و حالت تعمیم یافته آن یا همان n وزیر کار و سعی کردند آن را حل کنند که از این جمله میتوان به «کارل فریدریش گاوس» (Carl Friedrich Gauss) اشاره کرد. «اس گانتر» (S. Gunther) در سال ۱۸۷۴ یک روش قطعی برای حل این مساله ارائه کرد و «جیمز گلشیر» (James Whitbread Lee Glaisher) راهکار ارائه شده توسط گانتر را بهبود بخشید.
سرانجام و در سال ۱۹۷۲، «ادسخر ویبه دِیکسترا» (Edsger W. Dijkstra) الگوریتم «اول عمق پسگرد» (Depth-First Backtracking) را برای حل این مساله معرفی کرد. حل مساله ۸ وزیر به لحاظ محاسباتی بسیار پرهزینه است، زیرا تنها در یک صفحه 8×۸ برای هشت وزیر، ۴,۴۲۶,۱۶۵,۳۶۸ حالت ممکن قرارگیری در صفحه شطرنج وجود دارد که از میان آنها، تنها ۹۲ مورد راه حل مساله است. بنابراین، با افزایش مقدار n، پیچیدگی محاسباتی افزایش پیدا میکند. البته، روشهایی برای کاهش پیچیدگی محاسباتی جهت حل این مساله ارائه شده است؛ اما به طور کلی، مساله n وزیر از جمله مسائل «انپی» (Non Deterministic Polynomial | NP) در حوزه «هوش مصنوعی» (Artificial Intelligence) محسوب میشود.
شایان توجه است که در مساله n وزیر، برای n=2 و n=۳ پاسخی وجود ندارد. همچنین، الزاما تعداد راهکارهای موجود برای مساله با افزایش N افزایش پیدا نمیکنند. برای مثال، مساله ۶ وزیر، تعداد پاسخهای کمتری نسبت به حالت ۵ وزیر دارد. در ادامه، روش حل مساله n وزیر برای N=4 نمایش داده شده است؛ سپس، یک الگوریتم ساده برای حل آن معرفی و در نهایت، مساله ۴ وزیر با استفاده از «الگوریتم پَسگرد» (Backtracking Algorithm) حل شده است. پیادهسازی الگوریتم پسگرد برای حل مساله N وزیر با زبانهای برنامهنویسی C++/C، پایتون و جاوا انجام شده است.
خروجی مورد انتظار، یک ماتریس دودویی است که در آن ۱ برای محلهایی که وزیر در آن قرار گرفته و ۰ برای محلهای فاقد وزیر است. برای مثال، ماتریس خروجی زیر، برای مساله ۴ وزیر است که تصویر آن در بالا وجود دارد.
{ 0, 1, 0, 0} { 0, 0, 0, 1} { 1, 0, 0, 0} { 0, 0, 1, 0}
الگوریتم ساده برای حل مساله N وزیر
الگوریتم ساده برای حل مساله n وزیر، همه پیکربندیهای ممکن برای وزیرها روی صفحه را تولید میکند و پیکربندی را چاپ میکند که محدودیتهای داده شده را ارضا میکند.
while there are untried configurations { generate the next configuration if queens don't attack in this configuration then { print this configuration; } }
الگوریتم پَسگرد
در الگوریتم «پَسگرد» (Backtracking)، ایده آن است که وزیرها یکی یکی در ستونهای متفاوت قرار بگیرند و کار از چپترین ستون آغاز میشود. هنگامی که یک وزیر در ستون قرار میگیرد، بررسی میشود که آیا وزیر جدید قرار داده شده با سایر وزیرهای قرار گرفته در صفحه تصادم دارد یا خیر.
در ستون کنونی، اگر سطری پیدا شود که هیچ ضربی بین وزیر جدید و سایر وزیرها وجود نداشته باشد، وزیر در آنجا قرار داده میشود. در غیر این صورت، پسگرد اتفاق میافتد و false بازگردانده میشود. الگوریتم پَسگرد برای حل مساله n وزیر، به صورت زیر است:
- از چپترین ستون شروع کن.
- اگر همه وزیرها قرار گرفتهاند،
- True را بازگردان
- همه سطرها در ستون کنونی را بررسی کن. اقدامات زیر را برای هر سطر آزموده شده انجام بده.
- اگر وزیر بتواند به صورت امن در این سطر قرار بگیرد، آن را [row, column] به عنوان بخشی از راهکار علامتگذاری کن و به طور بازگشتی بررسی کن که آیا قرار دادن وزیر در اینجا منجر به راهکار میشود.
- اگر قرار دادن وزیر در [row, column] منجر به راهکار میشود، true را بازگردان.
- اگر قرار دادن وزیر منجر به یک راهکار شود، نشانهگذاری آن را بردار [row, column] (پسگرد) و به مرحله a برو و سطر دیگری را بررسی کن.
- اگر همه سطرها مورد بررسی قرار گرفتند و هیچ یک پاسخ نبودند، false را به trigger backtracking (عامل عقبنشینی) بازگردان.
پیادهسازی مساله N وزیر در ++C/C
پیاده سازی مساله N وزیر در پایتون
پیاده سازی مساله N وزیر در جاوا
خروجی؛ مقدار ۱ نشانگر محل قرارگیری وزیر است.
0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان دادهها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- معرفی منابع آموزش ویدئویی هوش مصنوعی به زبان فارسی و انگلیسی
- زبان برنامهنویسی پایتون (Python) — از صفر تا صد
- آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس
- پشته در ساختمان داده چیست؟ – به زبان ساده
^^
سلام من اینو نمی فهمم از کجا به کجا میره آیا در تابع چندین مقدار ذخیره میشه آیا اگر آموزش c++ فرادرس تهیه کنم می تونم اینم بفهمم
با تشکر از مطلب بسیار زیبا.میشه مثالی از کاربرد این الگوریتم در حوزه هایی دیگه ارائه بدین