15-ös játék
Forrás: Skiena, Revilla Programming Challenges
Valószínűleg mindenki találkozott már a 15-ös játék valamelyik változatával, ha nem is tudta, hogy ez a neve a játéknak. Egy $4 \times 4$-es táblán 15 tologatható négyzet alakú elem és egy üres hely található. A 15 elemnek van egy eredeti sorrendje (ami lehet egyszerűen egy számsor, de lehet egy kép is), majd "megkeverik" az elemeket. Feladatunk az eredeti sorrend visszaállítása. Az egyetlen megengedett lépés, hogy az üres helyre tolhatjuk valamelyik - az üres hellyel szomszédos - elemet.
Feladat
Egy adott táblára döntsük el, hogy megoldható-e a játék, és ha igen, adjunk meg egy megoldást.
Bemenet
A bemenet az elemek kezdeti elrendezését adja meg, négy sorban négy-négy szóközzel elválasztott számmal. A kirakós darabjait az 1, 2, ..., 15 számok jelzik, az üres helyet pedig a 0. A cél mindig az
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0állapot elérése.
Kimenet
Ha a feladvány nem oldható meg, a kimenet egyetlen sorába írjuk a következőt:
"Nincs megoldás."
Ha megoldható, akkor adjunk meg egy lehetséges megoldást. A megoldást úgy kódoljuk, hogy az üres hely "mozgásának" irányát adjuk meg lépésenként. Fel - F, Le - L, Balra - B, Jobbra - J. A lépések kódját egyetlen sorba írjuk, szóközök nélkül.
Példa
| 15.be | 15.ki |
|
2 3 4 0 1 5 7 8 9 6 10 12 13 14 11 15 |
BBBLJLJLJ |
|
13 1 2 4 5 0 3 7 9 6 10 12 15 8 11 14 |
Nincs megoldás. |