حل معمای پازل 8 با جستجوی دوطرفه

[yasemi]

کسی تا حالا با جستجوی دو طرفه پازل 8 رو حل کرده ممنون میشم کمک کنید

[qwerty11]

میشه بگین کجاشو مشکل دارین !؟ چون به نظر مساله ی سختی نیست :گیج:

از مبدا و مقصد شروع به جستجوی اول سطح کنین (البته نوع جستجو مهم نیست و من فرض کردم شما میخوای جواب بهینه رو به دست بیاری) و برای هر کدوم یه لیست در نظر بگیرین که گره هایی رو نگهداری میکنه که تولید شدن. برای هر کدوم هم یه صف در نظر بگیرین. وقتی مثلاً از مبدا به یه گره رسیدیم :

1- این گره نه توی لیست اول وجود داره اما توی لیست دوم نیست. ===> به لیست اول اضافه کنینش و داخل صف مربوطه بندازینش.
2- این گره توی لیست دوم وجود داره. ===> مساله حل شده و شما میتونین جواب رو چاپ کنین.
3- این گره توی لیست اول وجود داره اما توی لیست دوم نیست. ===> هیچ کاری انجام ندین.

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

موفق باشین :)

[yasemi]

لطفا بیشتر توضیح بدید ممنون میشم. حالات های مختلفی که پیش میاد رو چطور چک کنم مثلا وقتی یکی از پازل ها 3 تا فرزند داره و اون یکی مثلا 4 تا ؟

[qwerty11]

لطفا بیشتر توضیح بدید ممنون میشم. حالات های مختلفی که پیش میاد رو چطور چک کنم مثلا وقتی یکی از پازل ها 3 تا فرزند داره و اون یکی مثلا 4 تا ؟
خوب وقتی یکیش 3 تا و اون یکی 4 تا فرزند داشته باشه چه مشکلی پیش میاد !؟ راستش اصلاً منظورتونو نفهمیدم :| شما لطف کنین و راه حلی که تو ذهنتون دارین رو بگین تا من نظرمو بگم.

[yasemi]

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

ممنون

[qwerty11]

خوب اینی که شما گفتین همون جواب مساله هستش. اما اینکه چیکار کنین کدتون جمع و جور و کم بشه برمیگرده به توانایی برنامه نویسی خودتون... مثلاً برای اینکه تست کنین یه گره تو اون طرف وجود داره یا نه میتونین از map استفاده کنین که هم راحته و هم برنامتونو خیلی سریع میکنه. یا مثلاً به این نکته توجه کنین که میتونین حالت یک گره رو توی یه string ذخیره کنین و دیگه مجبور نیستین کلاس تعریف کنیین... و ...

[yasemi]

به نظر میشه این برنامه رو با بانک اطلاعاتی نوشت ؟

[qwerty11]

چرا آخه از بانک اطلاعاتی استفاده کنیم !؟
چه مزیتی داره !؟
به نظر من که اصلاً نیازی به این کار نیست !

[yasemi]

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

[qwerty11]

1- اگر چی زیاد میشد قاطی میکرد !؟

2- از نظر زمانی قاطی میکرد یا حافظه ای !؟

3- ببین ! شما حالت یه گره رو میتونین تو یه string که 9 تا خونه داره نگهداری کنین ! کلاً هم 9 فاکتوریل تا حالت داری که به نصف حالتاش نمیشه رفت. یعنی کلاً به 1632960 بایت احتیاج دارین در بدترین حالت ! در حالی که شما میتونین تا 10 میلیون بایت از حافظه قرض بگیری ! بگذریم از اینکه میشه حالت یه گره رو با یه int هم نشون داد... پس قاعدتاً نباید مشکل کمبود حافظه داشته. اینکه بیاین یه کلاس تعریف کنین که حالت یه گره رو نشون بده هم کارتون رو سخت میکنه و هم حافظه ی زیادی مصرف میکنه... بعضی وقتا باید پا روی عادت گذاشت و به راه حلهای دیگه هم فکر کرد... امیدوارم کمکت کرده باشم.

[yasemi]

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

[qwerty11]

خوب من از کجا بدونم !؟ حداقل کدی که نوشتی رو بزار تا بشه در موردش نظر داد.

[yasemi]

توی جستجوی آرایه خیلی طول میده این mao رو که میگی چطور برای آرایه دوبعد استفاده کنم و چطور جستجو کنم

ممنون