مربع هشت (8-puzzle)

در یک مربع 3 در 3 که شامل 9 خانه کوچک است ، هشت مربع شماره گذاری شده قرار داده ایم . یکی از خانه ها نیز خالی است . مسئله با یک حالت اولیه شروع می شود . هدف چیدن مربع های شماره گذاری شده به ترتیب روبرو است ( حالت هدف ) :

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

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