Írjunk programot Sam Lloyd híres tologatós játékának ‐ pontosabban a $3\times 3$-as változatának ‐ kirakására. Egy $3\times 3$-as, négyzet alakú dobozban $8$ kis kocka van, megszámozva $1$-től $8$-ig, egy hely pedig üresen marad. Egy lépés abból áll, hogy valamelyik szomszédos kockát az üres helyre toljuk. Azt kell elérnünk, hogy az első sorban (balról jobbra) az 1, 2, 3-as, a második sorban a 4, 5, 6-os, a legalsó sorban a 7, 8-as kockák legyenek, az üres hely pedig a jobb alsó sarokban legyen.
A program a standard bemenetről olvassa be a kiinduló állapotot. Az állapot leírása három sorból fog állni soronként három, szóközökkel elválasztott számmal. Az üres mezőt a $0$ jelenti.
A program keresse meg a legrövidebb (a lehető legkevesebb lépésből álló) megoldást és írja ki a standard kimenetre. Ha több legrövidebb megoldás van, akkor bármelyiket kiírhatja. A lépéseket az éppen arrébb tolt kockák számával kódoljuk. A számjegyeket egyetlen sorba írjuk, közvetlenül egymás után. Ha a feladatnak nincs megoldása, akkor írjuk ki azt, hogy ,,nincs megoldás''.
Példák: