حل معمای 8 (8puzzle) به روش های مختلف

حل معماي 8 (پازل 8 ) به روش هاي مختلف

صورت مسئله:

اين مسئله جورچين اعداد است!
معمای 8 شامل یک صفحه 3×3 با 8 مربع شماره دار است. همه شما با این معما آشنا هستید. نکته مهم این است که به جای اینکه بگوییم «مربع شماره 4 را به داخل فضای خالی حرکت بده» بهتر است بگوییم «فضای خالی جایش را با مربع سمت چپش عوض کند.»

فرموله سازی حل معمای 8

عملگر ها : فضای خالی به سمت بالا، پایین، چپ و يا راست حرکت می کند.
آزمون هدف : آیا با شکل 1-2 مطابقت دارد؟
هزینه مسیر : هر قدم ارزش 1 دارد. بنابراین هزینه مسیر همان طول مسیر است.

معمای 8 متعلق به خانواده Sliding-block Puzzles است. این کلاس عمومی به عنوان NP-complete شناخته می شود.

سورس بازي پازل به 4 زبان

C#.Net

vb.net

++C

و به زبان VB

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

C++

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

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