Puzzle de 8 P68428

Un puzzle de 8 és un trencaclosques on hi ha 8 peces numerades de l’1 al 8 en un tauler de 3 per 3 posicions, tot deixant un forat. A cada moviment es pot desplaçar una peça cap al seu forat adjacent. Començant amb les peces a l’atzar, l’objectiu és reordenar-les aplicant moviments de forma que quedin com es veu a la figura següent:

Descriurem una configuració del puzzle amb una matriu de $3\times3$ nombres, usant el valor 0 pel forat. Així, l’objectiu és arribar a la configuració final

    1 2 3
    4 5 6 
    7 8 0

Per exemple, es pot solucionar el puzzle

    1 2 3
    4 5 6 
    7 8 0

amb 3 moviments:

    1 2 3       1 2 3       1 2 3       1 2 3
    0 4 6       4 0 6       4 5 6       4 5 6
    7 5 8       7 5 8       7 0 8       7 8 0

Escriviu un programa que calculi el mínim nombre possible de moviments per resoldre un puzzle donat (o que digui que no es pot).

Entrada

L’entrada conté una permutació dels naturals del 0 al 8.

Sortida

La sortida és el nombre mínim de moviments per resoldre el puzzle, o None si no es pot.