کد و الگوریتم هشت وزیر با روش عقبگرد
یکی از معروف ترین سوال ها برای آموزش الگوریتم ها و روش عقبگرد (Backtraking)، مسئله هشت وزیر است که علاوه بر سادگی زیبایی خاصی هم دارد .
فهرست مطالب
تعریف مسئله هشت وزیر
یکی از معروف ترین سوال ها برای آموزش الگوریتم ها و روش عقبگرد (Backtraking)، مسئله هشت وزیر یا n queens است که علاوه بر سادگی زیبایی خاصی هم دارد .
مسیله n وزیر به شرح زیر است:
فرض کنید که صفحه شطرنجی به ابعاد n *n دارید ، چگونه می توان n عدد وزیر (نمی دونم چرا ما به ملکه در شطرنج می گوییم وزیر !!) را در صفحات شطرنج قرار داد به طوری که هم را تهدید نکنند.
قبل از شروع حل ابتدا بگذارید نحوه حرکت وزیر را در صفحه شطرنج مرور کنیم ، یک وزیر می تواند همانند تصویر زیر در راستای افقی و عمودی و دو قطر حرکت و آن خانه ها را تحت پوشش خود قرار دهد.
.jpg)
حرکت وزیر در صفحه شطرنج
روش عقبگرد یا backtracking در حل هشت وزیر
عقبگرد یا همان backtracking روشی است که در آن تمام حالت های ممکن ساخته می شود و هر حالتی که ساخته می شود چک می شود تا درست یا غلط بودن آن بررسی شود و اگر غلط بود حالتی دیگر را تولید می کند و همین طور ادامه می دهد.
بررسی یک مثال
برای راحتی در توضیح فرض کنیم که می خواهیم چهار وزیر را در صفحه شطرنجی با ابعاد ۴ * ۴ قرار دهیم . به شکل زیر که درخت تمام حالت های ممکن برای قرار گیری وزیر ها در صفحه شطرنج هستند دقت کنید :
شکل بالا درخت تمام حالاتی است که ۴ وزیر را می توان در صفحه شطرنج ۴ در ۴ قرار داد . وزیر اول می تواند در ستون های ۱ تا چهار قرار بگیرد ، وزیر دوم هم می تواند در خانه های ۱ تا چهارم قرار بگیرئ و همین طور تا آخر .
ولی جواب را چگونه از روی درخت بالا به دست آوریم ؟ ابتدا ما باید بتوانیم یک حالت را از درخت به دست بیاوریم که این کار با استفاده از پیمایش عمقی یا preorder امکان پذیر است.
در پیمایش پیش ترتیب یا عمقی ابتدا ریشه دیده می شود و بعد از آن فرزندان ، در زیر چند پیمایش preorder اول را می نویسم :
<1,1><2,1><3,1><4,1>
<1,1><2,1><3,1><4,2>
<1,1><2,1><3,1><4,3>
<1,1><2,1><3,1><4,4>
<1,1><2,1><3,2><4,1>
<1,1><2,1><3,2><4,2>
<1,1><2,1><3,2><4,3>
<1,1><2,1><3,2><4,4>
<1,1><2,1><3,3><4,1>
<1,1><2,1><3,3><4,2>
<1,1><2,1><3,3><4,3>
<1,1><2,1><3,3><4,4>
<1,1><2,1><3,4><4,1>
<1,1><2,1><3,4><4,2>
<1,1><2,1><3,4><4,3>
<1,1><2,1><3,4><4,4>
<1,1><2,2><3,1><4,1>
<1,1><2,2><3,1><4,2>
<1,1><2,2><3,1><4,3>
<1,1><2,2><3,1><4,4>
<1,1><2,2><3,2><4,1>
<1,1><2,2><3,2><4,2>
<1,1><2,2><3,2><4,3>
<1,1><2,2><3,2><4,4>
<1,1><2,2><3,3><4,1>
<1,1><2,2><3,3><4,2>
<1,1><2,2><3,3><4,3>
<1,1><2,2><3,3><4,4>
<1,1><2,2><3,4><4,1>
<1,1><2,2><3,4><4,2>
<1,1><2,2><3,4><4,3>
<1,1><2,2><3,4><4,4>
.
.
.
همین طور که می بینید اگر درخت حالات را پیمایش پیش ترتیب یا Preorder کنیم تمام حالاتی که ۴ وزیر در صفحه چهار در چهار قرار می گیرد را به صورت منظم به دست می آوریم حالا کل حالت های ممکن را داریم و برای رسیدن به جواب کافی است که تک تک حالت ها را بررسی کنیم ببینیم که وزیر ها هم را تهدید می کنند یا نه ! اگر هیچ کدام از وزیر ها مورد تهدید نبودند معلوم می شود آن حالت یکی از جوا هاست و آن را چاپ می کنیم و اگر وزیری مورد تهدید بود معلوم می شود که آن حالت جواب ما نیست و ما باید به سراغ حالت بعدی برویم.
پیاده سازی
برای بررسی اینکه ببینیم وزیر ها هم را تهدید می کنند یا نه تابع promising را در زیر نوشته ام که در آن
- s : آرایه ای است که خانه صفرم آن حاوی ستون وزیری صفرم است (وزیری که در سطر صفر) است ، خانه ی یکم آن حاوی ستون وزیر یکم است (وزیری که در سطر صفر) است و …
- n : تعداد خانه های آرایه یا همام تعداد وزیران
- limit : limit سطری از درخت است که در آن قرار داریم فرض کنید در سطر دوم درخت قرار داریم اون موقع برای بررسی این که ببینیم وزیر ها هم را تهدید می کنند یا باید وضعیت دو وزیر اول را چک کنیم زیرا وقتی در سطح دوم هستیم فقط از وضعیت دو وزیر اول آگاه هستیم و از وضعیت سایر وزیر ها اطلاع ندارم و limit هم می گوید ما اکنون در کدام سطح از درخت قرار داریم
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | bool promising(int* s, int n, int limit)//s array of position , n number of queens { if (limit == 0) { return true; } for (int i = 0; i <= limit - 1; i++) { for (int j = i + 1; j <= limit; j++) { if ((s[i] >= n) || (s[j] >= n) || (s[i] == s[j] || i - j == s[i] - s[j] || i - j == s[j] - s[i])) { return false; } } } return true; } |
خروجی این تابع یک مقدار منطقی است . اگر وزیر ها هم را تهدید نکنند مقدار true برمی گرداند اگر نه false بر می گرداند.
سوال دیگری که پیش می آید این است که آیا ما باید تمام درخت را ابتدا تولید کنیم و بعد به سراغ حل سوال برویم ؟ جواب به طرز روشنی منفی است ، ما لزومی به تولید درخت نداریم می توانیم در حین برنامه قسمت های مورد نظر از درخت (مسیر ها ) را تولید کنیم .
برای حل سوال دو تابع دیگر نوشتم n_solve_queen و n_queen که در ادامه توضیح می دهمشان.
تابع n_solve_queen آرایه s را تولید می کند و تابع اصلی که n_queen است را فرا می خواند و همین طور وضعیت وزیر صفرم (وزیر سطر صفر) در این تابع فراخوانی می شود
1 2 3 4 5 6 7 8 9 10 11 | void solve_n_qeen(int n) { int *s; s = new int[n]; for (int i = 0; i < n; i++) { s[0] = i; n_queen(s, n, 0); } } |
تابع بعدی تابع n_queen است که آرگمان هایش دقیقا مانند تابع promising است . در ابتدا که وارد این تابع می شویم تابع promising چک می کند که آیا تا سطر limit , limit وزیر اول هم را تهدید می کنند یا نه . اگر هم را تهدید بکنند تابع تمام می شود ولی اگر هم را تهدید نکنند یک شرط دیگر بررسی می شود ، شرط جدید می گوید آیا الان در سطر آخر(وزیر آخر) قرار داریم یا نه .اگر در سطر آخر قرار داشتیم یعنی توانسته ایم n وزیر را بدون اینکه هم را تهدید کنند در یک صفحه شطرنج n در n قرار دهیم ولی اگر در سطر آخر نبودیم خود تابع n_queen را برای سطر بعد فرا می خوانیم به طوری که بار اول وزیر در ستون صفرم باشد و بار بعدش ستون یکم و همین طور تا ستون n-1 ام.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | void n_queen(int *s, int n, int limit) { static int counter = 0; if (promising(s,n,limit)) { if (limit == n-1) { int row = 0; counter++; cout << setw(3) << counter << ": "; for (int i = 0; i < n; i++) { cout << setw(2) << "(" << row << "," <<s[i] << ")"; row++; } cout << endl; } else { for (int j = 0; j < n; j++) { s[limit + 1] = j; n_queen(s, n, limit+1); } } } } |
کد کامل حل هشت وزیر به زبان سی پلاس پلاس
در زیر کد کامل برنامه n – queens ( هشت وزیر ) قرار دارد :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | // n-Queen.cpp : open-mind.ir // #include "stdafx.h" #include <iostream> #include <iomanip> using namespace std; bool promising(int* s, int n, int limit)//s array of position , n number of queens { if (limit == 0) { return true; } for (int i = 0; i <= limit - 1; i++) { for (int j = i + 1; j <= limit; j++) { if ((s[i] >= n) || (s[j] >= n) || (s[i] == s[j] || i - j == s[i] - s[j] || i - j == s[j] - s[i])) { return false; } } } return true; } void n_queen(int *s, int n, int limit) { static int counter = 0; if (promising(s,n,limit)) { if (limit == n-1) { int row = 0; counter++; cout << setw(3) << counter << ": "; for (int i = 0; i < n; i++) { cout << setw(2) << "(" << row << "," <<s[i] << ")"; row++; } cout << endl; } else { for (int j = 0; j < n; j++) { s[limit + 1] = j; n_queen(s, n, limit+1); } } } } //open-mind.ir void solve_n_qeen(int n) { int *s; s = new int[n]; for (int i = 0; i < n; i++) { s[0] = i; n_queen(s, n, 0); } } int main() { int n; cout << "Enter n(number of queens in n*n board) ::"; cin >> n; solve_n_qeen(n); return 0; } |
نمایش خروجی
وقتی برنامه را برای ۸ وزیر اجرا کردم ۹۲ جواب به دست آمد که در زیر بخشی از آن را می بینید
و وقتی برای ۱۶ وزیر اجرا کردم در طی شش ساعت ۸۰۸۰۰۰ جواب مختلف پیدا کردم و اگر می خواستم تمام جواب های ممکن را پیدا احتمالا باید نزدیک به یک روز برنامه را در حال اجرا می گذاشتم و در زیر بخشی از جواب ها را می توانید برای ۱۶ وزیر ببینید :
مطالعه بیشتر
* برای مطالعه بیشتر و حل این سوال برای تعداد وزبرهای زیاد به این پست از وبسایت ما مراجعه کنید : n وزیر با روش تپه نوردی ( N queens by Hill climbing )
*البته می توانید این برنامه را بدون بازگشتی حل کنید که سرعت خیلی بیشتری هم دارد اما من سوال را برای مقاصد آموزشی به این طریق حل کردم.
و در آخر اگر کد این برنامه را با زبان های دیگر یا روشی دیگر نوشته اید آن را برای ما ایمیل کنید تا در همین پست قرارش دهیم.
برای بسته نشدن برنامه بعد از نتایج نتونستم کاری انجام بدم با اینکه به دوستمون گفته بودید آخر برنامه ;()cin.get قرار بده لطفا مشخص تر راهنمایی بفرمایید
شما این دو خط رو قرار بدید ببینید مشکل حل میشه یا نه
تشکر بسیار زیاد
حل شد
عالی بود ممنون
من که هیچی نفهمیدم. ولی دمت گرم. برا نمره گرفتن خوبه
این برنامه رو میشه برای n وزیر هم نوشت یا متفاوته ؟
سلام
بله میشه.
موفق باشید
در شطرنج نام وزیر نداریم بعد اسلام اسمش را وزیر گذاشته ایم. در زبان پهلوی یعنی زبان پیش از اسلام ایران وزیر در شَترَنگ به نام فرزین نامیده میشد. فرزین یعنی کسی که بر روی زین اسب است. اصطلاحا به کسی گفته میشد که از نظر جایگاه اجتماعی بالاترین مقام در کنار پادشاه است اما کارهای فوق العاده میکند و میتواند فرامین بسیار کارا بدهد. اگر نگاه کنیم وزیر شطرنج از همه مهره ها بهتر و با توانایی بالاتر حرکت میکند فقط مثل اسب نمی تواند بجهد. این وزیر جنسیت ندارد میتواند پهلوان بانو گردآفرید شاهنامه باشد یا رستم.
بسیار تشکر از نظر خوبتون – بسیار استفاده کردم .
سلام.خسنه نباشید میگم به شما.ممنون از مطلب کاملتون.
فقط می خواستم بپرسم باید چیکار کنم که بعد از اجرا شدن برنامه صفحه بسته نشه؟
سلام
آخر برنامت بنویس
درود
در قطعه کد زیر شما ۲ بار از حلقه for استفاده کردید
با یک حلقه هم می توان نوشت وشرط ها را دران نوشت
سلام – بله می شد با یک حلقه ی for نوشت – ولی هربار که حلقه اجرا می شد باید شرط هم یک بار چک می شد – ولی زیاد فرقی هم ندارد. می شد یک فور گذاشت و شرط ها هم در آن نوشت.
در قطعه کد امیدواری ۲بار از حلقه استفاده کردید
مرتبه تکرار و پیچیدگی زمانی برنامه خیلی ……میشه با یک حلقه نوشت
http://uupload.ir/files/8hdt_pr.jpg
حقیقتن باید کد بهینه شه تا به بهترین کیفیت دست پیدا کرد
خیلی خیلی ممنون ازتون بابت آموزش
تشکر از نظرهای خوبتون – بله حق با شماست می شه با یک فور هم نوشت ، موقعی که من این کد رو نوشتم تازه وارد این مباحث شده بودم و متاسفانه بهینه همه چیز رو ننوشتم .
عالی بود؛ ممنون!
عالی بود؛ واقعا ممنون!
سلام
در شبه کد این الگوریتم در قسمت promising در حلقه while داریم
k<i
دلیل این شرط برای حلقه چیه؟
این کد خیلی بد نوشته شده! از کد توی این بلاگ چراا استفاده نمی کنی؟
می گه فرض کن الان توی سطر آی هستیم -وزیر های موجود در سطر های قبل از آی (با کی مشخص می شوند) را با وزیر سطر آی مقایسه می کنه تاببینه برخورد دارند یا نه!
سلام ببخشیدمن یه برنامه نوشتم تا یه جاهایی اجرا میشه اما بعدش یه صفحه باز میشه روش نوشتهwindows can check online for a solution to the problem میشه بگین مشکل از کجاست؟؟؟؟؟؟؟
این چیزی که می گی باید بیشتر روی مدیریت حافظه باشه ، دقیق نمی دونم چون باید برنامه رو ببینم ، ایمیل کن
سلام میشه درباره این برنامه هشت وزیری که نوشتیند توضیحی بدیند من این برنامه هشت وزیرو باید برا استادم توضیح بدم (ممنون)
کلی تلاش کردم تونستم توضیح بدم ، بعید می دونم بیشتر از این بتوانم توضیح دهم!
سلام میشه با روش الگوریتم ژنتیک یا ارضای محدودیت یا تپه نوردی کد برنامع ۸ وزیر رو بذارید با توضیح کاملش ؟؟؟!
خیلی احتیاج دارم ممنون میشم
توی این مدت کوتاه نمی تونم چون درگیر امتحان ها هستم ولی بعدا حتما می گذارم. ولی اگر می خواهید می توانید از بخش سفارش پروژه در بالای صفحه، سفارش بدهید تا سایر دوستان برایتان انجام دهند.
توی این پست می تونی مطلب مورد نظرت رو پیدا کنی
http://open-mind.ir/1393/n-%D9%88%D8%B2%DB%8C%D8%B1-%D8%A8%D8%A7-%D8%B1%D9%88%D8%B4-%D8%AA%D9%BE%D9%87-%D9%86%D9%88%D8%B1%D8%AF%DB%8C-n-queens-by-hill-climbing/
سلام آقای دلیرانی من درس هوش مصنوعی رو دارم و استادم یه سوال در بخش best frist داده می خواهم به من کمک کنید سوال اینه که می خواهیم از تهران بریم اهواز هم میتونیم از کرج بریم از قم بریم از دماوند بریم از نظر مسافت کوتاه ترین مسیر و انتخاب می کنیم و میریم قم از نظر مسافت کوتاه تره حالا شهرهایی که از تهران به اهواز هست تو مسیر قم را مینویسیم برنامش رو باید به روش ++c بنویسیم میشه کمک کنید خواهشن
دنبال الگوریتم، داجسترا یا فلوید برو
سلام اقای دلیرانی
خسته نباشید
من مقاله ی شما درباره ی معمای ۸ وزیر و گردش اسب رو خوندم
اما شما بیشتر درباره برنامه نویسیشون توضیح داده بودین
من هنوز الگوریتم ساده ی این ۲تا رو متوجه نشدم
می شه خواهش کنم الگوریتم ساده و به زبان فارسی و نه
c
این ۲تا رو در اختیار من بذارین
ممنون می شم.
سلام ، متاسفم که نتونستم خوب مطلب را انتقال بدم.
الگوریتمش توی کتاب سی ال آر اس هست
البته توی این سایت هم هست :http://www.algorithmha.ir/
سلام
حداکثر توی یک صفحه ی شطرتج ۸ وزیر جا میشود چون اگر بیشتر شود
مثلا ۹ وزیر ، یا ستونی تکراری است یا سطری چون ۸×۸ است .
پس به نظر شما چه جوری ۱۶ وزیر جا میشود ؟
توی ۸ وزیر هم چک کنید فکر کنم جواب های اش خیلی کمتره .
موفق باشید
سلام
۱۶ وزیر برای صفحه ۱۶ در ۱۶ است نه صفحه ی ۸ در هشت !
برای ۸ وزیر هم تعداد راه ها را درست محاسبه می کند ، اگر شک دارید می توانید در اینترنت آن را سرچ کنید
ممنون
سلام
این با روش عقب گرد ساده حل شده یا MRV یا LCV؟