# Puzzle de 8

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:

![image](puzzle8.png){width="5cm"}

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.

## Informació del problema

Autoria: Jordi Petit

Generació: 2026-01-25T11:35:25.332Z

© *Jutge.org*, 2006--2026.\
<https://jutge.org>
