8puzzle2

کد و حل معمای eight puzzle (پازل هشت) با روش Back tracking

8puzzle2

بازی معمای هشت ( ۸-puzzle ) یکی از بازی های فکری است که احتمالا در دوران بچگی همه ی ما با آن خود را سرگرم می کردیم.

در شکل زیر بازی معمای هشت را می بینید:8puzzle

همین طور که می بینید ما یک صفحه ی ۳ در ۳ داریم که با ۸ کاشی با شماره های یک تا هشت پر شده اند. در این بازی شما می توانید کاشی های مجاور خانه ی خالی را هول دهید و به جای خانه ی خالی بیاورید مثالا فرض کنید کاشی شماره ی شش را به پایین هول دهیم. شکل زیر ظاهر می شود:8-puzzle

با این کار ما می توانیم جای کاشی ها رو عوض کنیم.

هدف از این بازی این است که کاشی ها را با جابه جایی به شکل زیر برسانیم و مسیری را که منتهی به جواب می شود را بدست بیاوریم:8puz

ما این سوال را با استفاده از روش عقبگرد ( Back Tracking) که نوعی روش جست و جو است حل می کنیم.

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

فرض کنید به ما این پازل را داده اند حل کنیم:

8-puzzle-eight

ما اینجا در این وضعیت سه کار می توانیم بکنیم:

یک :

شش را به پایین حل بدهیم :

8-puzzle-eight

دو:

یا ۵ را به چپ هل بدهیم:

8-puzzle-eight

سه :

یا هفت را به راست هول بدهیم:

8-puzzle-eight

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

 

Tree 8 puzzle open-mind.ir

حالا ما با جست و جوی درخت بالا می توانیم به جواب برسیم

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

در شکل بالا گره ها شماره گذاری شده است ، جست و جو به روش عقبگرد در دخت بالا به شکل زیر است:

۱ ,۲ ,۵,۱۰,۲۰

به ته درخت رسیدیم آن قدر بالا می رویم تا به نودی برسیم که بتوانیم از آن پایین بیاییم که اگر از مسیری که آمده ایم به عقب برگردیم اولین     نودی که می توانیم از آن پایین برویم گره ی ۵   است که اگر از آن پایین برویم به مسیر زیر به دست می آید:

۱,۲,۵,۱۱,۲۱

به جواب نرسیدیم دوباره کار قبل را تکرار می کنیم تا به جواب برسیم مسیر های زیر مسیرهایی است که تارسیدن به جواب تولید می شود

۱,۲,۵,۱۱,۲۲

۱,۲,۵,۱۱,۲۳

۱,۳,۶,۱۲,۲۴

۱,۳,۶,۱۳,۲۵

۱,۳,۷,۱۴,۲۶,۲۷

مسیر (۱,۳,۷,۱۴,۲۶,۲۷) به حل سوال منتهی می شود پس به جواب رسیده ایم و جست و جوی درخت را متوقف می کنیم.مسیر به دست آمده با خط پر رنگ در شکل مشخص شده است.

آیا قبل از حل مساله باید درخت حالات را تولید کرد و بعد در آن جست و جو کنیم؟

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

شاید یک سوال برای شما پیش آمده باشد و آن این است که چرا ما درخت حالت را تا عمق خاصی ساخته ایم در حالی که تا بی نهایت ممکن است عمق درخ ادامه داشته باشد؟

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

 

حالا بریم سراغ کد برنامه :

تابع مقایسه ی دو آرایه ی دو بعدی :

a و b دو آرایه ای هستند که قرار است مقایسه شوند و به صورت اشاره گر به تابع فرستاده شده اند.

n هم طول و عرض آرایه است.

خروجی به صورت bool است که یا مقدار True را دارد یا False.

 تابع حل سوال n puzzle :

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

این تابع به صورت بازگشتی است.

int **current_status : آرایه ی دو بعدی است که حالتی از پازل است که باید آن را حل کنیم

int **goal_status : آرایه ای دو بعدی است که هدف بازی است و باید به آن برسیم

در آریه ی  پازل خانه ی خالی را با صفر نمایش می دهیم.

vector <int> *path :  وکتوری از جنس اعداد صحیح است که مسیری را طی کرده ایم در آن قرار دارد که اعداد در آن به شرح زیر است:

۰: یعنی خانه ی خالی در پازل را به سمت بالا برده ایم

۱: یعنی خانه ی خالی در پازل را به سمت چپ برده ایم

۲: یعنی خانه ی خالی در پازل را به سمت پایین  برده ایم

۳: یعنی خانه ی خالی در پازل را به سمت راست برده ایم

int deep: حداکثر عمق درختی است که ما می توانیم به در درخت پیش برویم. اولین بار هنگام فراخوانی به deep مقدار ۱- را می دهیم.

int i_zeroPoint : مختصات i کاشی خالی است.

int j_zeroPoint : مختصات j کاشی خالی است.

int lastMove: حرکت قبلیمان در آن است تا دوباره آن را تکرار نکنیم و به مرحله ی قبل برویم. چون اگر به مرحله قبل برویم ممکن است توی حلقه ی هایی بی افتیم که مدت حل سوال را زیاد می کند. البته از vector <int> *path هم می توانستیم جای  lastMove استفاده کنیم!

 

این تابع بازگشتی است و درخت را در خودش می سازد.

تابع حل مسیله ی puzzle , Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square  , هشت پازل  ,  شانزده پازل , پازل , n پازل ، معمای هشت

تابع showPath :

این تابع حرکاتی را که باید روی خانه ی خالی انجام دهیم را که در وکتور  vector <int>* path قرار دارد روی حالت اولیه انجام می دهد و قدم به قدم پازل حل شده را نمایش می دهد.

 

 

در زیر کد کلی برنامه  هشت پازل (معمای هشت) را با سی پلاس پلاس می بینید که در Main آن یک مثال به به تابع فرستاده شده:

(قبل از نوشتن کد یک عکس از خروجی را قرار داده ام)

output of 8puzzle

 

 

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)

۲۱ دیدگاه

  • سلام سال نو مبارک
    میخواستم ببینم شما این کد برنامه معمای هشت را به زبان جاوا ندارید؟

  • سلام این الگوریتم A star هست؟

  • سلام کسی رو هم نمیشناسین که بتونه اینو به زبان جاوا پیاده سازی کنه

  • سلام و خسته نباشید
    ممنونم بابت این قطعه کد
    ولی ظاهرا این کد فقط با همون اعدادی که مثال زدین جواب درست میده !
    من اعداد دیگه میذارم ارور میده
    چیکارش باید کرد واسه رفع ارور ؟

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

      مطمینی ؟! یکی دوتا از از اون تست کیسات رو که موجب ارور شدن بده تا ببینم مشکل چی

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

          فرض کن پازل مرتب است و ما بهمش می زنیم و یک حالت نامرتب به دست می آید ! این حالت نامرتب را می توان حل کرد و به جواب رسید . حالا فرض کن مهره ها را از جای خود دربیاوریم و جایشان را عوض کنیم ! یک حالت نامرتب به دست می آید ولی الزاما به جواب نمی رسد و ممکن است جوابی نداشته باشد! همین طور ممکن است جواب ما مثلا با انجام ۲۰۰ حرکت به دست بیاید که سرچ چنین درختی بسیار سنگین خواهد بود و با این کامپیوتر های ما یکم سخته !به همین خاطر ما توی کد یک عمق تعریف می کنیم که من مقدار ۲۰ را مشخص کرده ام که می گوید تا عمق بیست توی درخت پایین برو اگر جواب پیدا نکردی دیگه ادامه نده و به بالا برگرد و یک شاخه دیگر از درخت را امتحان کن! خطای برنامه هم به خاطر این بود که وقتی تمام درخت را سرچ می کرد و جوابی پیدا نمی کرد در آخر یکی از وکتورمان پاپ می کرد که موجب خطا می شد! که با اضافه کردن یک دوتا if به کد درستش کردم و کد را آپدیت کردم!
          و در بالای کد یک ماکرو تعری کردم به اسم

          که عمق حداکثر درخت را مشخص می کند که می تونی دستی کم یا زیادش کنی ولی هرچه زیاد تر باشد مدت زمان بیشتری برنامه طول می کشد و ممکن است حافظه ی کامپیوترت آور فلا کند!
          یا ممکن است مثالی که داده ای در بیش از مثلا ۲۰۰ حرکت حل شود یا اصلا حلی نداشته باشد!

          و تشکر بابت نظر خوبت.

          • اینو در نظر نگرفته بودم 😀
            کاملا درسته . . .
            مرسی که اینقد با حوصله و کامل جواب دادین 🙂

      • با این مثال هم ارور داد
        با اینکه ۱ مرحله واسه حلش بیشتر نیاز نیست

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

          چک کردم درست بود می دونی مشکلت از کجاست ؟!

          هر دو تابع توی برنامه دو آرگومان دارند به نام

          که مختصات نقطه صفر را مشخص می کنند در حالی که تو تست کیس ها رو مرتب عوض می کنی ولی اون دوتا آرگومان را عوض نکردی به همین خاطر اشتباه جواب می ده 🙂 با این تست کیسی که تو دادی آرگومان ها دو تابع به این شکل می شود ، صفر تو در حالت فراخوانی برنامه در نقطه یک و صفر است :

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

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

  • سلام
    ببخشید این به چه زبانی هست
    و برای اینکه اجرا کنیم باید چه نرم افزاری رو نصب کنیم؟

  • میشه این پازل رو بصورت ۱۵تایی و به زبان جاوا بنویسید؟
    پازل با استفاده از فاصله منهتن میتونه حل بشه.کد این روشو اگر بذارید یا برام ایمیل کنید خیلی ممنون میشم

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

      سلام ، اگر توجه کرده باشید کد را به صورت پارامتری نوشته ام و می توانید با تغییرات کوچک آن را برای پانزده تایی در آورید. متاسفانه زیاد به جاوا مسلط نیستم

  • سلام
    نوشتن این برنامه با زبان جاوا همین قدر طولانی میشه؟
    روش دیگه ای برای نوشتنش نیست؟
    (عکس درخت- گراف حالات- نمایش داده نمیشه)

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

      بستگی به روش پیاده سازی داره ، مثلا می شد با سی پلاس پلاس همین رو توی برنامه ی کوچک تری نوشت ، تقریبا با جاوا هم همین قدر می شه، عکس رو هم دوباره می ذارم

پاسخ دهید

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