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×3 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.
Input
1 2 3 0 4 6 7 5 8
Output
3
Input
5 1 0 3 4 2 7 8 6
Output
14
Input
3 1 5 2 4 6 7 8 0
Output
14
Input
1 2 3 4 5 6 7 8 0
Output
0
Input
1 2 8 7 4 3 0 5 6
Output
16
Input
8 1 2 0 4 3 7 6 5
Output
None
- Author
- Jordi Petit
- Language
- Catalan
- Official solutions
- Python
- User solutions
- Python