Gyermekkorom egyik kedvenc játéka volt a 16-puzzle, amelynek lényege, hogy egy 4x4 mezőből álló táblán számok találhatók 1-től 15-ig, valamint egyetlen üres mező.

A cél, hogy a mezőket úgy rendezzük át, hogy azok sorfolytonosan növekvő sorrendben legyenek, a tábla jobb alsó sarka pedig az üres mező legyen.

Adott az alábbi táblánk:

Adjuk meg az optimális, 10 lépésből álló megoldását a feladatnak!