Bonjour,
Je cherche à résoudre une variante du problème du cavalier assez velue !
Le problème est le suivant :
J'ai un tableau de 5x5.
Il est de la forme :
-1 1 1 1 1
0 -1 1 1 1
0 0 -1 1 1
0 0 0 -1 1
0 0 0 0 -1
L'objectif est d'arriver à cette configuration :
-1 0 0 0 0
1 -1 0 0 0
1 1 -1 0 0
1 1 1 -1 0
1 1 1 1 -1
Donc une symétrie par rapport à la diagonale.
Pour cela, j'ai plusieurs contraintes.
Chaque déplacement intervertit les valeurs de départ et d'arrivée.
L'une des valeurs est obligatoirement -1.
Il y a une alternance entre les valeurs de départ, le premier coup doit être entre 0 et -1, le second entre 1 et -1, le troisième entre 0 et -1, ...
Les déplacements autorisés sont ceux du cavalier au échec.
La solution doit être en 32 coups ...
Sachant que je peux "lever" la pièce du tableau, ce n'est pas un parcours linéaire comme le problème du cavalier initial (deux déplacements qui se suivent n'ont pas forcément une case en commun).
Pour résoudre cela, j'ai essayé de modifier un peu les méthodes utilisées pour résoudre le problème d'origine.
Premier essai : Heuristique en se déplaçant sur les cases ayant le moins de déplacements possibles ensuite -> 24h à tourner sans résultat.
Deuxième essai : Heuristique en privilégiant les déplacements sur des cases qui ne sont pas dans leur position finale -> 24h aussi sans résultat.
Je suis preneur de toutes vos idées
Merci d'avance
-----