Az S. 15. feladat (2006. február)

S. 15. Írjunk programot Sam Lloyd híres tologatós játékának -- pontosabban a 3×3-as változatának -- kirakására. Egy 3×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:

Beküldendő a program forráskódja (s15.pas, s15.cpp, ...).

(10 pont)

A beküldési határidő 2006. március 16-án LEJÁRT.

Statisztika:

4 dolgozat érkezett.
10 pontot kapott:	Engedy Balázs, Nikházy László.
9 pontot kapott:	Ureczky Bálint.
3 pontot kapott:	1 versenyző.

A KöMaL 2006. februári informatika feladatai