یک برنامه (به زبان C یا Java) با الگوریتم جستجوی عمومی بنویسید که بازی 8 را به روش جستجو انجام می دهد. به این ترتیب که کاربر یک حالت ورودی و یک حالت هدف از بازی 8 را به برنامه می دهد. سپس برنامه از کاربر می پرسد که به کدامیک از استراتژی های انتخاب (گرهی در حافظه برای باز کردن فرزندانش) مساله را باید حل کند.
- استراتژی انتخاب عمقی
- استراتژی انتخاب سطحی
- استراتژی انتخاب حریصانه کشف کنندگی با تابع کشف کنندگی h1
- استراتژی انتخاب حریصانه کشف کنندگی با تابع کشف کنندگی h2
- استراتژی انتخاب A* با تابع کشف کنندگی h1
- استراتژی انتخاب A* با تابع کشف کنندگی h2
- استراتژی انتخاب کمترین هزینه (با فرض اینکه هزینه حرکت های افقی دو برابر هزینه حرکتها عمودی باشد)
- استراتژی انتخاب تکراری عمیق شونده
پس از اینکه کاربر گزینه را انتخاب کرد. برنامه در خروجی
- یک مسیر از حالت ورودی به حالت هدف را چاپ خواهد کرد، و
- تعداد گام هایی که الگوریتم برای پیدا کردن مسیر انجام داده است را چاپ خواهد کرد.
توابع کشف کنندگی h1 و h2 بصورت زیر هستند.
h1(s)= تعداد مربعهایی که در سر جای خودشان با توجه به حالت هدف هستند
h2(s)=تعداد گامهایی که می تواند به حالت هدف رسید با این آزادی که بتوان از روی مربعها بصورت افقی و عمودی رد شد
h2(s)=تعداد گامهایی که می تواند به حالت هدف رسید با این آزادی که بتوان از روی مربعها بصورت افقی و عمودی رد شد