Feladat: S.15 Korcsoport: - Nehézségi fok: -
Füzet: 2006/február, 103. oldal  PDF file
Témakör(ök): Nehezebb feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Í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, ...).