کد و الگوریتم هشت وزیر (n queens) با روش عقبگرد با ++C

n queen

یکی از معروف ترین سوال ها برای آموزش الگوریتم و روش عقبگرد  (Backtraking)  مسیله هشت وزیر یا n queens  است که علاوه بر سادگی زیبایی خاصی هم دارد .

مسیله  n وزیر به شرح زیر است:

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

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

حرکت وزیر در صفحه شطرنج

معرفی روش عقبگرد – backtracking :

عقبگرد یا همان backtracking  روشی است که در آن تمام حالت های ممکن ساخته می شود و هر حالتی که ساخته می شود چک می شود تا درست یا غلط بودن آن بررسی شود و اگر غلط بود حالتی دیگر را تولید می کند و همین طور ادامه می دهد.

برای راحتی در توضیح فرض  کنیم که می خواهیم چهار وزیر را در صفحه شطرنجی با ابعاد ۴ * ۴ قرار دهیم . به شکل زیر که درخت تمام حالت های ممکن برای قرار گیری وزیر ها در صفحه شطرنج هستند دقت کنید :

n queen tree

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

ولی جواب را چگونه از روی درخت بالا به دست آوریم ؟ ابتدا ما باید بتوانیم یک حالت را از درخت به دست بیاوریم که این کار با استفاده از پیمایش عمقی یا 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 هم می گوید ما اکنون در کدام سطح از درخت قرار داریم

خروجی این تابع یک مقدار منطقی است . اگر وزیر ها هم را تهدید نکنند مقدار  true برمی گرداند اگر نه false بر می گرداند.

سوال دیگری که پیش می آید این است که آیا ما باید تمام درخت را ابتدا تولید کنیم و بعد به سراغ حل سوال برویم ؟ جواب به طرز روشنی منفی است ، ما لزومی به تولید درخت نداریم می توانیم در حین برنامه قسمت های مورد نظر از درخت (مسیر ها ) را تولید کنیم .

برای حل سوال دو تابع دیگر نوشتم n_solve_queen و n_queen که در ادامه توضیح می دهمشان.

تابع n_solve_queen  آرایه s را تولید می کند و تابع اصلی که n_queen  است را فرا می خواند و همین طور وضعیت وزیر صفرم (وزیر سطر صفر) در این تابع فراخوانی می شود

 

تابع بعدی تابع n_queen است که آرگمان هایش دقیقا مانند تابع promising است . در ابتدا که وارد این تابع می شویم تابع promising چک می کند که آیا تا سطر limit , limit وزیر اول هم را تهدید می کنند یا نه . اگر هم را تهدید بکنند تابع تمام می شود ولی اگر هم را تهدید نکنند یک شرط دیگر بررسی می شود ، شرط جدید می گوید آیا الان در سطر آخر(وزیر آخر) قرار داریم یا نه .اگر در سطر آخر قرار داشتیم یعنی توانسته ایم n وزیر را بدون اینکه هم را تهدید کنند در یک صفحه شطرنج n در n قرار دهیم ولی اگر در سطر آخر نبودیم خود تابع n_queen را برای سطر بعد فرا می خوانیم به طوری که بار اول وزیر در ستون صفرم باشد و بار بعدش ستون یکم و همین طور تا ستون n-1 ام.

 

در زیر کد کامل برنامه n – queens  ( هشت وزیر )  قرار دارد :

 

وقتی برنامه را برای ۸ وزیر اجرا کردم ۹۲ جواب به دست آمد که در زیر بخشی از آن را می بینید

8-chess

 

و وقتی برای ۱۶ وزیر اجرا کردم در طی شش ساعت ۸۰۸۰۰۰ جواب مختلف پیدا کردم و اگر می خواستم تمام جواب های ممکن را پیدا احتمالا باید نزدیک به یک روز برنامه را در حال اجرا می گذاشتم و در زیر بخشی از جواب ها را می توانید برای ۱۶ وزیر ببینید :

6 - hourse - 16 queen

 

* برای مطالعه بیشتر و حل این سوال برای تعداد وزبر های زیاد به این پست از وبسایت ما مراجعه کنید : n وزیر با روش تپه نوردیN queens by Hill climbing

*البته می توانید این برنامه را بدون بازگشتی حل کنید که سرعت خیلی بیشتری هم دارد اما من سوال را برای مقاصد آموزشی به این طریق حل کردم.

و در آخر اگر کد این برنامه را با زبان های دیگر یا روشی دیگر نوشته اید آن را برای ما ایمیل کنید تا در همین پست قرارش دهیم.

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۳۰ دیدگاه

  • در شطرنج نام وزیر نداریم بعد اسلام اسمش را وزیر گذاشته ایم. در زبان پهلوی یعنی زبان پیش از اسلام ایران وزیر در شَترَنگ به نام فرزین نامیده میشد. فرزین یعنی کسی که بر روی زین اسب است. اصطلاحا به کسی گفته میشد که از نظر جایگاه اجتماعی بالاترین مقام در کنار پادشاه است اما کارهای فوق العاده میکند و میتواند فرامین بسیار کارا بدهد. اگر نگاه کنیم وزیر شطرنج از همه مهره ها بهتر و با توانایی بالاتر حرکت میکند فقط مثل اسب نمی تواند بجهد. این وزیر جنسیت ندارد میتواند پهلوان بانو گردآفرید شاهنامه باشد یا رستم.

  • فروش درب چوبی ساختمان

    ۸وزیر رو به n طریق میشه در زمین شطرنج جا داد ولی سوال اینه که ۹ وزیر رو تو صفحه ۸*۸ میشه جاداد؟؟؟؟؟؟؟؟؟؟؟؟

    ممنون

    • سلام – توی کامنت های قبل هم همچین برداشتی رخ داده است – منظور از نه وزیر قرار دادن نه وزیر در صفحه ی ۹ * ۹ است اگر نه نمی توان ۹ وزیر را در صفحه ی هشت در هشت جا داد.

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

  • درود

    در قطعه کد زیر شما ۲ بار از حلقه for استفاده کردید

    با یک حلقه هم می توان نوشت وشرط ها را دران نوشت

    • فرهاد دلیرانی

      سلام – بله می شد با یک حلقه ی for نوشت – ولی هربار که حلقه اجرا می شد باید شرط هم یک بار چک می شد – ولی زیاد فرقی هم ندارد. می شد یک فور گذاشت و شرط ها هم در آن نوشت.

      • در قطعه کد امیدواری ۲بار از حلقه استفاده کردید
        مرتبه تکرار و پیچیدگی زمانی برنامه خیلی ……میشه با یک حلقه نوشت

        http://uupload.ir/files/8hdt_pr.jpg

        حقیقتن باید کد بهینه شه تا به بهترین کیفیت دست پیدا کرد
        خیلی خیلی ممنون ازتون بابت آموزش

        • فرهاد دلیرانی

          تشکر از نظرهای خوبتون – بله حق با شماست می شه با یک فور هم نوشت ، موقعی که من این کد رو نوشتم تازه وارد این مباحث شده بودم و متاسفانه بهینه همه چیز رو ننوشتم .

  • عالی بود؛ ممنون!

  • عالی بود؛ واقعا ممنون!

  • سلام
    در شبه کد این الگوریتم در قسمت promising در حلقه while داریم
    k<i
    دلیل این شرط برای حلقه چیه؟

    • فرهاد دلیرانی

      این کد خیلی بد نوشته شده! از کد توی این بلاگ چراا استفاده نمی کنی؟
      می گه فرض کن الان توی سطر آی هستیم -وزیر های موجود در سطر های قبل از آی (با کی مشخص می شوند) را با وزیر سطر آی مقایسه می کنه تاببینه برخورد دارند یا نه!

  • سلام ببخشیدمن یه برنامه نوشتم تا یه جاهایی اجرا میشه اما بعدش یه صفحه باز میشه روش نوشتهwindows can check online for a solution to the problem میشه بگین مشکل از کجاست؟؟؟؟؟؟؟

    • فرهاد دلیرانی

      این چیزی که می گی باید بیشتر روی مدیریت حافظه باشه ، دقیق نمی دونم چون باید برنامه رو ببینم ، ایمیل کن

  • سلام میشه درباره این برنامه هشت وزیری که نوشتیند توضیحی بدیند من این برنامه هشت وزیرو باید برا استادم توضیح بدم (ممنون)

  • سلام میشه با روش الگوریتم ژنتیک یا ارضای محدودیت یا تپه نوردی کد برنامع ۸ وزیر رو بذارید با توضیح کاملش ؟؟؟!
    خیلی احتیاج دارم ممنون میشم

  • سلام آقای دلیرانی من درس هوش مصنوعی رو دارم و استادم یه سوال در بخش best frist داده می خواهم به من کمک کنید سوال اینه که می خواهیم از تهران بریم اهواز هم میتونیم از کرج بریم از قم بریم از دماوند بریم از نظر مسافت کوتاه ترین مسیر و انتخاب می کنیم و میریم قم از نظر مسافت کوتاه تره حالا شهرهایی که از تهران به اهواز هست تو مسیر قم را مینویسیم برنامش رو باید به روش ++c بنویسیم میشه کمک کنید خواهشن

  • سلام اقای دلیرانی
    خسته نباشید
    من مقاله ی شما درباره ی معمای ۸ وزیر و گردش اسب رو خوندم
    اما شما بیشتر درباره برنامه نویسیشون توضیح داده بودین
    من هنوز الگوریتم ساده ی این ۲تا رو متوجه نشدم
    می شه خواهش کنم الگوریتم ساده و به زبان فارسی و نه
    c
    این ۲تا رو در اختیار من بذارین
    ممنون می شم.

  • سلام

    حداکثر توی یک صفحه ی شطرتج ۸ وزیر جا میشود چون اگر بیشتر شود

    مثلا ۹ وزیر ، یا ستونی تکراری است یا سطری چون ۸×۸ است .

    پس به نظر شما چه جوری ۱۶ وزیر جا میشود ؟

    توی ۸ وزیر هم چک کنید فکر کنم جواب های اش خیلی کمتره .

    موفق باشید

نظر خود را بنویسید.

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