gioco del 15 e formalizzazione matematica

[Caroncino]

Salve,

Nel famoso gioco del 15 dovrei riuscire a portare la casella 1 al suo posto (cioè in alto a sinistra), da qualunque posizione essa si trovi, con il minor numero di spostamenti di caselle possibili. Ho scoperto sperimentalmente che risolvo il problema spostando la casella 1 diagonalmente a "zig zag" e poi eventualemte spostandomi in orizzontale o in verticale se incontro il lato superiore o sinistro del quadrato. In tal modo gni volta che muovo la casella 1 ho uno spostamento complessivo di 3 caselle in totale (compresa la 1), quando mi muovo a zig zag, e 5 postamenti di caselle quando mi muovo orizzontalmente o verticalmente. Ora questo dovrebbe essere l' "algoritmo ottimo di risoluzione". Ora il mio problema sta nel trovare una formalizzazione matematica che mi giustifichi tale algoritmo. Come posso fare?

[TomSawyer]

Se andassi solo orizzontalmente e verticalmente (cioe' se per esempio ti spostassi a sinistra fino a toccare il bordo, poi in alto) , allora dovresti spostare ogni volta 5 caselle, per far avanzare la 1. Invece, andando a zig-zag, come hai detto tu, sposti due caselle in meno che seguendo la prima strada. Non c'e' uno studio complicato sotto.

[motorhead]

lo trovi su wikipedia anche in italiano , ricordo di averlo visto

[Caroncino]

Se invece del quadrato avessi un rettangolo, magari fortemente sbilanciato, come posso giustificare che il mio caso peggiore è quando la casella 1 è in fondo a destra e il posto vuoto deve essere in alto a sinistra? Inoltre posso formalizzare un algoritmo che mi indichi qual è il percorso che nel minor tempo (e quindi con il minor numero di spostamenti di caselle) mi porti la casella 1 al suo posto?
Grazie