Puzzle de 8 P68428


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • 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
    
  • Information
    Author
    Jordi Petit
    Language
    Catalan
    Official solutions
    Python
    User solutions
    Python