Bonjour !

J'aime bien chercher des algorithmes pour résoudre des petits jeux 2D en un temps minimum.
Mais ça fait plusieurs fois que je tombe sur un problème du type "coups non commutatifs".
C'est à dire que l'ordre des coups pour gagner la partie à une importance.
La question est : "peut-on résoudre ces problèmes avec l'algèbre linéaire ?"


Prenons par exemple ce petit problème sympa :

*******************************************
Soit une grille de dimension 3.
Cette grille est remplie aléatoirement avec tous les chiffres de 0 à 8.

Par exemple, on aura :

1 3 8
5 0 6
2 7 4

L'objectif est de déterminer le nombre de coups minimum pour classer les chiffres dans l'ordre suivant :

0 1 2
3 4 5
6 7 8

Les règles de transformation sont :
On ne peut permuter deux chiffres que si l'un des deux chiffres est 0
et si les deux chiffres sont sur des colonnes ou des lignes consécutives.

Variante :
Les règles de transformation sont :
On ne peut permuter deux chiffres que si l'un des deux chiffres est 0
et si les deux chiffres sont sur la même colonne ou la même ligne.
*******************************************


Je voudrais savoir si ce problème peut être résolu grâce à l'algèbre linéaire.
Quelqu'un est-il intéressé pour chercher la solution avec moi ?

Have fun