Përshkruani një algoritëm për të zgjidhur lojën "8 puzzles".
8-puzzle është një puzzle rrëshqitëse që kërkon që lojtarit të rrëshqisë pllaka të numerizuara në një rrjet 3x3 për të përfunduar puzzlin. Algoritmi për zgjidhjen e këtij puzzli përfshin një teknikë kërkimi të gjerë. Kjo përfshin krijimin e një liste të nyjeve që përmban gjendjen aktuale të puzzlit (pozicioni dhe renditja e katroreve) si dhe gjendjet e mëparshme (për të minimizuar kërkimet për gjendje të dyfishta). Algoritmi pastaj fillon të lëvizë secilën pllakë në hapësirën bosh dhe vlerëson nëse gjendja e re që rezulton është një nyje e synuar (dmth fundi i puzzlit). Nëse nuk është, programi kalon në nyjen e ardhshme, duke mbajtur gjurmë të nyjeve tashmë të vizituara dhe duke regjistruar vazhdimisht gjendjet e reja për vlerësim të mëtejshëm. Pasi të identifikohet nyja e synuar, programi llogarit rrugën optimale nga nyja fillestare në nyjen e synimit.