Discussion :

[Médinoc]

En gros, tu fais un parcours en largeur?

[mohsenuss91]

En gros, tu fais un parcours en largeur?

Exactement, mais sans générer l'arbre et rechercher la solution dedans mais plutôt une utilisant une file d'attente (frontière).

[Médinoc]

En fait, plutôt qu'un arbre, c'est un graphe, et même un graphe bidirectionnel (donc, avec cycles).

Un parcours en largeur, en vérifiant chaque fois qu'on n'a pas déjà parcouru le nœud, me paraît donc approprié.
Surtout si au passage, tu mémorises pour chaque nœud un pointeur vers le nœud "précédent", ce qui te donnera une liste chaînée de la solution vers le départ.

...Et en inversant cette liste chaînée, un parcours du départ à l'arrivée.

Edit: En fait, ce graphe, c'est un graphe qu'on construit en même temps qu'on le parcoure. J'ignore quelle est la vraie proportion de positions impossibles dans un Taquin (mais je sais qu'il y en a), mais pour un taquin de 9*9, je placerais une borne supérieure au nombre de positions possibles à 9! = 362880.

[mohsenuss91]

ok,je vais pas générer un graphe et puis chercher mais plutôt j'utilise une lise chainée (frontière), je sauvegarde pour chaque nœud son prédécesseur (son père) et une fois que je trouve le but j'empile le chemin (du nœud but jusqu'au racine) et j’arrête, donc le premier but trouvé c'est le bon.

[Sve@r]

Edit: En fait, ce graphe, c'est un graphe qu'on construit en même temps qu'on le parcoure. J'ignore quelle est la vraie proportion de positions impossibles dans un Taquin (mais je sais qu'il y en a), mais pour un taquin de 9*9, je placerais une borne supérieure au nombre de positions possibles à 9! = 362880.

Salut

Ce problème me turlupinait alors je l'ai résolu.
Le problème de la recherche récursive en profondeur, c'est que soit on peut partir dans une direction impossible, soit on peut partir dans une direction possible mais longue alors qu'il y a une autre solution plus courte.

Donc je suis parti sur une autre approche: stockage et évaluation de toutes les positions après 1 permutations, puis 2, puis 3, etc. en utilisant une liste chainée en 2 dimensions
Cette liste chainée permet de gérer les profondeurs. Donc le premier élément contiendra son niveau (1), un pointeur vers le niveau suivant (2) et un pointeur vers toutes les positions obtenues après toutes les permutations possibles de la position de départ.
Le second élément contiendra son niveau (2), un pointeur vers le niveau 3 et un pointeur vers toutes les positions obtenues après toutes les permutations possibles des positions trouvées au niveau 1.
Et etc etc. Et dès qu'une position correspond à la position gagnante, son pointeur est renvoyé. Comme chaque position possède un pointeur vers sa postion issue du niveau précédent, il ne reste qu'à affficher la chaine remontant vers la position initiale.

Je n'ai pas tenté d'optimiser (élimination des position déjà trouvées) parce que je n'ai pas eu le temps (et puis je ne suis pas certain qu'il y en ait tant que ça). Toutefois je note l'idée de mettre une limite.

Actuellement je résous un jeu jusqu'à 13 permutations et je tente 15 mais bon, déjà que 13 c'était assez long... enfin c'est l'ordi qui bosse donc...

Positions en cours

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
	ushort depart[3][3]={
		{2, 0, 3},
		{7, 1, 6},
		{5, 8, 4},
	};
 
	ushort goal[3][3]={
		{1, 2, 3},
		{4, 5, 6},
		{7, 8, 0},
	};

Etat du calcul
prof=1 (3 positions)
prof=2 (8 positions)
prof=3 (24 positions)
prof=4 (64 positions)
prof=5 (192 positions)
prof=6 (512 positions)
prof=7 (1536 positions)
prof=8 (4096 positions)
prof=9 (12288 positions)
prof=10 (32768 positions)
prof=11 (98304 positions)
prof=12 (262144 positions)
...

Si demain il a fini je viendrai donner le résultat...

[edit]Ok, il a fini (en près de 16h quand-même !!!)
Voici le résultat

prof=1 (3 positions)
prof=2 (8 positions)
prof=3 (24 positions)
prof=4 (64 positions)
prof=5 (192 positions)
prof=6 (512 positions)
prof=7 (1536 positions)
prof=8 (4096 positions)
prof=9 (12288 positions)
prof=10 (32768 positions)
prof=11 (98304 positions)
prof=12 (262144 positions)
prof=13 (786432 positions)
prof=14 (2097152 positions)

Trouvé en 15 permutations
0xdd14290 => Position (0x1844dc28, (nil))
1, 2, 3,
4, 5, 6,
7, 8, 0,
0xa4d2298 => Position (0xdd14290, 0xdd142b0)
1, 2, 3,
4, 5, 6,
7, 0, 8,
0x8feaf40 => Position (0xa4d2298, 0xa4d22b8)
1, 2, 3,
4, 0, 6,
7, 5, 8,
0x88e2b28 => Position (0x8feaf40, 0x8feaf60)
1, 2, 3,
0, 4, 6,
7, 5, 8,
0x8645cb0 => Position (0x88e2b28, 0x88e2b48)
0, 2, 3,
1, 4, 6,
7, 5, 8,
0x8564c18 => Position (0x8645cb0, 0x8645cd0)
2, 0, 3,
1, 4, 6,
7, 5, 8,
0x8511240 => Position (0x8564c18, 0x8564c38)
2, 3, 0,
1, 4, 6,
7, 5, 8,
0x84f5008 => Position (0x8511240, 0x8511260)
2, 3, 6,
1, 4, 0,
7, 5, 8,
0x84ea8b0 => Position (0x84f5008, 0x84f5028)
2, 3, 6,
1, 0, 4,
7, 5, 8,
0x84e7058 => Position (0x84ea8b0, 0x84ea8d0)
2, 3, 6,
0, 1, 4,
7, 5, 8,
0x84e5b60 => Position (0x84e7058, 0x84e7078)
2, 3, 6,
7, 1, 4,
0, 5, 8,
0x84e5448 => Position (0x84e5b60, 0x84e5b80)
2, 3, 6,
7, 1, 4,
5, 0, 8,
0x84e5190 => Position (0x84e5448, 0x84e5468)
2, 3, 6,
7, 1, 4,
5, 8, 0,
0x84e5098 => Position (0x84e5190, 0x84e51b0)
2, 3, 6,
7, 1, 0,
5, 8, 4,
0x84e5020 => Position (0x84e5098, (nil))
2, 3, 0,
7, 1, 6,
5, 8, 4,
(nil) => Position (0x84e5020, (nil))
2, 0, 3,
7, 1, 6,
5, 8, 4,

[edit2]En rajoutant juste un flag pour vérifier que la permutation "après" ne correspond pas à la premutation "avant" (style 0, 1, 2 donnera 1, 0, 2 qui, lui, redonne 0, 1, 2) l'effet boomerang est phénoménal

prof=1 (3 positions)
prof=2 (5 positions)
prof=3 (10 positions)
prof=4 (14 positions)
prof=5 (28 positions)
prof=6 (44 positions)
prof=7 (88 positions)
prof=8 (128 positions)
prof=9 (256 positions)
prof=10 (392 positions)
prof=11 (784 positions)
prof=12 (1160 positions)
prof=13 (2320 positions)
prof=14 (3512 positions)
Trouvé en 15 permutations
0x92bee90 => Position (0x92f14c8, (nil))
1, 2, 3,
4, 5, 6,
7, 8, 0,
0x92a4b58 => Position (0x92bee90, 0x92beeb0)
1, 2, 3,
4, 5, 6,
7, 0, 8,
0x9294340 => Position (0x92a4b58, 0x92a4b78)
1, 2, 3,
4, 0, 6,
7, 5, 8,
0x928bce8 => Position (0x9294340, 0x9294360)
1, 2, 3,
0, 4, 6,
7, 5, 8,
0x9286270 => Position (0x928bce8, 0x928bd08)
0, 2, 3,
1, 4, 6,
7, 5, 8,
0x92832d8 => Position (0x9286270, 0x9286290)
2, 0, 3,
1, 4, 6,
7, 5, 8,
0x92815e0 => Position (0x92832d8, 0x92832f8)
2, 3, 0,
1, 4, 6,
7, 5, 8,
0x9280748 => Position (0x92815e0, 0x9281600)
2, 3, 6,
1, 4, 0,
7, 5, 8,
0x927fcf0 => Position (0x9280748, 0x9280768)
2, 3, 6,
1, 0, 4,
7, 5, 8,
0x927f758 => Position (0x927fcf0, 0x927fd10)
2, 3, 6,
0, 1, 4,
7, 5, 8,
0x927f420 => Position (0x927f758, 0x927f778)
2, 3, 6,
7, 1, 4,
0, 5, 8,
0x927f288 => Position (0x927f420, 0x927f440)
2, 3, 6,
7, 1, 4,
5, 0, 8,
0x927f150 => Position (0x927f288, 0x927f2a8)
2, 3, 6,
7, 1, 4,
5, 8, 0,
0x927f098 => Position (0x927f150, (nil))
2, 3, 6,
7, 1, 0,
5, 8, 4,
0x927f020 => Position (0x927f098, (nil))
2, 3, 0,
7, 1, 6,
5, 8, 4,
(nil) => Position (0x927f020, (nil))
2, 0, 3,
7, 1, 6,
5, 8, 4,

Et je monte jusqu'à 21 en un temps raisonnable (moins d'une minute)...