Tour du Cavalier (débutant)

**elishac** · 07/01/2009, 23h07

Bonjour,

j'ai un problème avec Caml light, je pense qu'il s'agit d'une histoire de parenthèse ou un truc comme ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let cases_voisines_restantes (n,p) (x,y) =
	let add_couple (x,y) (x',y')= (x+x', y+y') in
	let knight_moves = [(2,1);(1,2);(-1,2);(-2,1);(-2,-1);(-1,-2);(1,-2);(2,-1)] in
	let position_valide (n,p) (x,y) = 0<=x && x<n && 0<=y && y<p in
	let rec aux knight_moves = match knight_moves with
		|[]->[]
		|h::q->let case_a_tester = add_couple (x,y) h in 
			if position_valide (n,p) case_a_tester then case_a_tester ::(aux q)
							else aux q
	in
	aux knight_moves;;
let vect_cases_voisines_restantes (n,p)=
	let res=make_vect n (make_vect p [] ) in  
	for i=0 to n-1 do 
	for j=0 to p-1 do
	res.(i).(j)<- cases_voisines_restantes (n,p) (i,j)
	done done;
	res;;

Pour répondre à ma question, vous n'avez pas besoin de comprendre ce que font chacune des 2 fonctions (à mon avis).
Ma question est simple : je ne comprends pas pourquoi (vect_cases_voisines_restantes (8,8)).(0).(0) n'est pas égal à cases_voisines_restantes (8,8) (0,0) malgré la ligne

Code :

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

res.(i).(j)<- cases_voisines_restantes (n,p) (i,j)

dans le cas où i=j=0.

**gasche** · 08/01/2009, 14h08

Erreur classique du débutant.

Tu t'es trompé en créant ta matrice :

Code :

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

let res=make_vect n (make_vect p [] ) in

Le code correct est :

Code :

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

let res = make_matrix n p []

ou bien :

Code :

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

let res = init_vect n (fun _ -> make_vect p []) in

Pourquoi ?
Quand deux tableaux sont égaux, modifier l'un revient à modifier l'autre :

Code :

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

1
2
3
4
5
# let a = [|0; 0|];;
# let b = a;;
# b.(0) <- 1;;
# a;;
- : int vect = [|1; 0|]

Tu as essayé de créer ta matrice comme un tableau de tableau :

Code :

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

1
2
let colonne = make_vect p [] in
let res=make_vect n colonne in

Toutes les colonnes sont égales. Modifier l'une d'entre elles va donc modifier toutes les autres, d'où des bugs imprédictibles.

**elishac** · 08/01/2009, 17h51

ok, merci pour la réponse, très complète.
Je ne connaissais ni make_matrix ni init_vect, donc je n'aurais pas pu deviner où était l'erreur.
init_vect n'est pas présente dans l'aide, je n'ai pas compris ce qu'elle fait.

**gasche** · 08/01/2009, 21h18

init_vect n'est pas présente dans l'aide

Si : http://caml.inria.fr/pub/docs/manual...node14.18.html

**elishac** · 08/01/2009, 22h31

ok. Merci. (elle ne l'était pas dans l'aide "F1").

Voici à présent la procédure complète que je voudrais réaliser.
Pouvez-vous m'aider à la corriger ? Merci d'avance.

Enoncé :
Créer une procédure qui donne le chemin parcouru par un cavalier (pièce qui se déplace en L ; voir wikipédia pour plus d'informations) qui aura été une et une seule fois sur chaque case d'un échiquier de taille n*p (n est le nombre de lignes, et p celui de colonnes).
Algorithme : (backtracking).
On crée une matrice de taille n*p, nommée matrice_cases_voisines_restantes, dont l'élément d'indice (i,j) est une liste contiendra à tout instant les cases qui sont accessibles par le cavalier depuis la case (i,j) et qui n'ont pas encore été testées.
On l'initialise en mettant dans l'élément d'indice (i,j) la liste de toutes les cases accessibles par le cavalier depuis (i,j).
On crée alors une fonction auxiliaire récursive nommée 'solution' qui prend en argument les cases déjà parcourues (liste cases_parcourues) et la matrice matrice_cases_voisines_restantes ; et renvoie la solution au probleme (liste cases_parcourues).
Elle est initialisée avec la matrice matrice_cases_voisines_restantes créée juste avant, et cases_parcourues = [].
Le cas d'arrêt est quand le nombre de cases parcourues est égal au nombre total de cases n*p.
Si ce n'est pas le cas d'arret, soit (x,y) case sur laquelle se trouve le cavalier (= hd cases_parcourues). S'il reste encore des cases voisines accessibles depuis (x,y) à tester, alors en prendre une, l'enlever à la liste des cases voisines accessibles depuis (x,y), vérifier qu'elle n'a pas déjà été parcourue, et la tester.
S'il ne reste plus de cases à tester, alors on fait du "backtracking" : on enleve la derniere case parcourue (s'il y en a une; sinon, renvoyer 'pas de solution') et on recommence (on ne repassera pas par cette case là car elle a été supprimée des cases_voisines_restantes quand on est passé dessus la premiere fois).

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
let tour_cavalier (n,p) =
	let rec appartient a = function
		|[]->false
		|h::q-> if h=a then true else appartient a q
	in
	(*debut de l'initialisation de matrice_cases_voisines_restantes *)
	let cases_voisines_restantes (x,y) =
		let add_couple (x,y) (x',y')= (x+x', y+y') in
		let knight_moves = [(2,1);(1,2);(-1,2);(-2,1);(-2,-1);(-1,-2);(1,-2);(2,-1)] in
		let position_valide (x,y) = 0<=x && x<n && 0<=y && y<p in
		let rec aux = function
			|[]->[]
			|h::q->let case_a_tester = add_couple (x,y) h in 
				if position_valide case_a_tester then case_a_tester ::(aux q) else aux q
		in
		aux knight_moves
	in
	let matrice_cases_voisines_restantes =
		let res=make_matrix n p [] in  (*matrice n*p avec la liste des cases_voisines_restantes*)
		for i=0 to n-1 do 
		for j=0 to p-1 do
		res.(i).(j)<- cases_voisines_restantes (i,j)
		done done;
		res
	in
	(* fin de l'initialisation de matrice_cases_voisines_restantes *)
	let rec solution cases_parcourues matrice_cases_voisines_restantes =
		if list_length cases_parcourues = n*p then cases_parcourues (*cas d'arret*) else
		let (x,y)= hd cases_parcourues in
		match matrice_cases_voisines_restantes.(x).(y) with
			|h::q-> matrice_cases_voisines_restantes.(x).(y) <- q (* on enleve la case que l'on va tester*) ;
				if (appartient h cases_parcourues) then solution cases_parcourues matrice_cases_voisines_restantes (*si la case à tester a déjà été parcourue, ne pas la tester*)
				else solution (h::cases_parcourues) matrice_cases_voisines_restantes
			|[]-> (* s'il n'y a plus de cases à tester, alors (pour peu que ce soit possible), on enleve la derniere case parcourue, et on recommence (backtracking) ; on ne repassera pas par cette case là car elle a été supprimée des cases_voisines_restantes quand on est passé dessus la premiere fois *)
				(match cases_parcourues with
				|_::tl -> solution tl matrice_cases_voisines_restantes
				|[] -> failwith "pas de solution")
	in
	solution [(0,0)] matrice_cases_voisines_restantes ;;

**gasche** · 09/01/2009, 08h52

Je pense que l'approche globale n'est pas efficace.

Tout d'abord, ton cas d'arrêt correspond à celui où le cavalier a parcouru toutes les cases. Es-tu certain que ce cas est possible en général ? Intuitivement (je n'ai jamais étudié la question) qu'il y a sans doute souvent (ça dépend de la taille de l'échiquier et peut-être du point de départ) des cases inaccessibles. Si c'était avéré, cela voudrait dire que ton algorithme ne peut en général pas renvoyer de solution (ce qui n'est pas très informatif).

Il serait à mon avis plus intéressant de te demander "quelle est la surface maximale que je peux couvrir ?". C'est une information plus facile à récolter que le chemin lui-même, et à priori au moins aussi informative.

Ensuite, je pense que ton approche du backtracking n'est pas efficace. Tu utilises des listes, donc la recherche et le remplacement sont en temps linéaire, ce qui est assez couteux. Au passage ta fonction "appartient" existe déjà et s'appelle "mem".

Pourquoi ne pas tout simplement utiliser une matrice de booléens ? Tu as une matrice qui contient "vrai" si tu n'es pas encore passé sur la case, ainsi que la position courante de ton cavalier. À partir d'une position, tu peux alors regarder l'ensemble des cases accessibles qui sont marquées "vrai", et pour chaque :
- la marquer faux
- rappeler la procédure en partant de cette position
- la re-marquer vrai (backtracking)

Si j'ai bien compris ce que tu veux faire, cette approche a toutes les chances de marcher et d'être beaucoup plus efficace.

**elishac** · 09/01/2009, 12h34

Bonjour, merci pour la réponse.

Tout d'abord, ton cas d'arrêt correspond à celui où le cavalier a parcouru toutes les cases. Es-tu certain que ce cas est possible en général ?

Oui c'est quasiment toujours possible, si l'échiquier est assez grand. Mais si l'échiquier est petit, l'algorithme aura vite fait d'examiner toutes les solutions (il y a un failwith "pas de solution" quand il a fini de tout faire).

Intuitivement (je n'ai jamais étudié la question) qu'il y a sans doute souvent (ça dépend de la taille de l'échiquier et peut-être du point de départ) des cases inaccessibles.

ça dépend de la taille, comme expliqué précédemment, mais pas du point de départ, pour des raisons de symétrie (commencer par la fin, retourner l'échiquier, etc.)

Si c'était avéré, cela voudrait dire que ton algorithme ne peut en général pas renvoyer de solution (ce qui n'est pas très informatif).

je trouve que "pas de solution" est assez informatif, vu la question posée :-).

Tu utilises des listes, donc la recherche et le remplacement sont en temps linéaire, ce qui est assez couteux

j'ai pas compris. Pour un vecteur (non trié) la recherche est aussi linéaire, non? Et pour un remplacement, je ne sais pas très bien ce que ça veut dire. Je ne remplace pas un élément du milieu de la liste, j'ajoute ou j'enlève le premier seulement. Veux-tu dire que l'appel de f h::l (où f est une fonction récursive, h un élément et l une liste) provoque le recopiage de toute la liste l, alors que : "let rec f v= v.(0)<-0 ; f v" ne provoque pas le recopiage de tout le vecteur v ? J'avais cru comprendre que les listes étaient justement plus adaptées aux fonctions récursives...

Au passage ta fonction "appartient" existe déjà et s'appelle "mem".

ok, je ne le connaissais pas, et je préfère de toute façon me contenter de fonctions simples, quitte à réécrire les plus complexes.

Pourquoi ne pas tout simplement utiliser une matrice de booléens ?

oui, c'est une autre solution, je l'avais envisagée. Le problème c'est que cette structure ne donne pas directement le chemin parcouru. Il faudrait une variable supplémentaire (si c'est une liste, ce serait équivalent à mon algorithme, à mon avis), où alors, au lieu d'une matrice de booléens, une matrice d'entiers, où l'entier est égal à -1 si la case n'a pas encore été parcourue et sinon il représente la ieme case parcourue. Est-ce vraiment plus simple ?

Pourquoi ne pas tout simplement utiliser une matrice de booléens ? Tu as une matrice qui contient "vrai" si tu n'es pas encore passé sur la case, ainsi que la position courante de ton cavalier. À partir d'une position, tu peux alors regarder l'ensemble des cases accessibles qui sont marquées "vrai", et pour chaque :
- la marquer faux
- rappeler la procédure en partant de cette position
- la re-marquer vrai (backtracking)

Je pense que l'approche globale n'est pas efficace. Je n'ai pas bien compris ton algorithme (la dernière ligne " la re-marquer vrai (backtracking)" m'est obscure), mais d'après ce que j'ai compris, tu vas tester tous les chemins possibles. Or il y en a beaucoup dès que m et n sont assez grands (des milliards, même quand m et n sont inférieurs à 10). Or il existe une optimisation (que je n'avais pas présentée pour ne pas alourdir la procédure déjà assez longue) assez intuitive, qui consiste, au lieu de prendre une case à tester au hasard, de prendre celle dont le nombre de cases accessibles est le plus petit. Bref, la méthode de backtracking est plus efficace que celle de l'arbre où on appelle récursivement toutes les possibilités à partir d'une case donnée, et ceci même s'il existe un échappement pour s'arrêter dès qu'on a trouvé une solution (d'ailleurs, je ne sais pas si l'appel de "f a ; f b" où f est récursive provoque l'appel de "f a", puis celui de "f b", ou alors les deux en même temps. Si c'est les deux en même temps, ton algorithme est encore moins efficace. Sinon, tu pourrais rajouter un échappement pour tout arrêter dès que l'on trouve une solution - ça me parait compliqué)

Indépendamment de toute amélioration de l'algorithme, pourquoi la procédure ne marche pas telle quelle ?

**gasche** · 09/01/2009, 17h35

Tu aurais du signaler l'erreur que tu avais, on aurait sans doute pu répondre sans tester.

J'ai testé ton code et :

Uncaught exception: Failure "hd"

Il n'y a qu'un seul "hd" dans ton programme :

Code :

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

      let (x,y)= hd cases_parcourues in

L'erreur est lancée quand cases_parcourues devient vide. Quand est-ce ?
Au départ elle ne l'est pas, tu mets (0, 0). Ensuite elle est en général conservée, sauf dans un cas :

Code :

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

1
2
3
          (match cases_parcourues with
           |_::tl -> solution tl matrice_cases_voisines_restantes
           |[] -> failwith "pas de solution")

Que se passe-t-il quand cases_parcourues ne contient plus qu'un élément ? Ce code l'enlève, la fonction est rappelée sur la liste vide, et boum.

Rustine rapide :

Code :

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

1
2
3
          (match cases_parcourues with
           | [] | _::[] -> failwith "pas de solution"
           |_::tl -> solution tl matrice_cases_voisines_restantes)

Remarque : si on inverse les deux lignes de ce filtrage, ça ne marche à nouveau plus. Pourquoi ? En règle générale il vaut mieux traiter le cas [] en premier.

On se rend ensuit compte que c'est bête, on teste la taille ici alors qu'on aurait pu le faire au début :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  let rec solution cases_parcourues matrice_cases_voisines_restantes =
    if list_length cases_parcourues = n*p then cases_parcourues (*cas d'arret*) else
      match cases_parcourues with
      | [] -> failwith "pas de solution"
      | (x, y) :: reste_cases_parcourues ->
          match matrice_cases_voisines_restantes.(x).(y) with
          | h::q->
              matrice_cases_voisines_restantes.(x).(y) <- q (* on enleve la case que l'on va tester*) ;
              if (appartient h cases_parcourues)
              then solution cases_parcourues matrice_cases_voisines_restantes
                (*si la case à tester a déjà été parcourue, ne pas la tester*)
              else solution (h::cases_parcourues) matrice_cases_voisines_restantes
          | []-> solution reste_cases_parcourues matrice_cases_voisines_restantes
              (* s'il n'y a plus de cases à tester, alors (pour peu
                 que ce soit possible), on recommence sans la première
                 case parcourue (backtracking) ; on ne repassera pas
                 par cette case là car elle a été supprimée des
                 cases_voisines_restantes quand on est passé dessus la
                 premiere fois *)
  in

Ça marche et c'est plus joli. Enfin, ça marche façon de parler. Ça affiche "pas de solution" pour toutes les dimensions que j'ai essayées (de (2,2) à (30, 30) environ).

Comme je suis têtu, j'ai donc implémenté la mesure du nombre de mouvements :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  let max_mouvs = ref 0 in
  let rec solution cases_parcourues matrice_cases_voisines_restantes =
    let taille_parcours = list_length cases_parcourues in
    max_mouvs := max !max_mouvs taille_parcours;
    if taille_parcours = n*p then cases_parcourues (*cas d'arret*) else
      match cases_parcourues with
      | [] -> failwith (printf__sprintf "pas de solution, %d mouvements au mieux" !max_mouvs)
      | (x, y) :: reste_cases_parcourues ->
          match matrice_cases_voisines_restantes.(x).(y) with
          | h::q->
              matrice_cases_voisines_restantes.(x).(y) <- q (* on enleve la case que l'on va tester*) ;
              if (appartient h cases_parcourues)
              then solution cases_parcourues matrice_cases_voisines_restantes
                (*si la case à tester a déjà été parcourue, ne pas la tester*)
              else solution (h::cases_parcourues) matrice_cases_voisines_restantes
          | []-> solution reste_cases_parcourues matrice_cases_voisines_restantes
              (* s'il n'y a plus de cases à tester, alors (pour peu
                 que ce soit possible), on recommence sans la première
                 case parcourue (backtracking) ; on ne repassera pas
                 par cette case là car elle a été supprimée des
                 cases_voisines_restantes quand on est passé dessus la
                 premiere fois *)
  in

On se rend compte qu'il fait "presque" l'échiquier. Pour (8,8) il en fait 53 sur 64, ce qui n'est pas mal. Pour (20, 20), 387. Comme je suis toujours têtu, je décide de le paramétrer par la case de départ (symétrie... mon oeil !) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
let tour_cavalier (n,p) depart =
  let rec appartient a = function
  |[]->false
  |h::q-> if h=a then true else appartient a q
  in
  (*debut de l'initialisation de matrice_cases_voisines_restantes *)
  let cases_voisines_restantes (x,y) =
    let add_couple (x,y) (x',y')= (x+x', y+y') in
    let knight_moves = [(2,1);(1,2);(-1,2);(-2,1);(-2,-1);(-1,-2);(1,-2);(2,-1)] in
    let position_valide (x,y) = 0<=x && x<n && 0<=y && y<p in
    let rec aux = function
    |[]->[]
    |h::q->let case_a_tester = add_couple (x,y) h in 
      if position_valide case_a_tester then case_a_tester ::(aux q) else aux q
    in
    aux knight_moves
  in
  let matrice_cases_voisines_restantes =
    let res=make_matrix n p [] in  (*matrice n*p avec la liste des cases_voisines_restantes*)
    for i=0 to n-1 do 
      for j=0 to p-1 do
        res.(i).(j) <- cases_voisines_restantes (i,j)
      done done;
    res
  in
  (* fin de l'initialisation de matrice_cases_voisines_restantes *)
  let max_mouvs = ref 0 in
  let rec solution cases_parcourues matrice_cases_voisines_restantes =
    let taille_parcours = list_length cases_parcourues in
    max_mouvs := max !max_mouvs taille_parcours;
    if taille_parcours = n*p then cases_parcourues (*cas d'arret*) else
      match cases_parcourues with
      | [] -> failwith (printf__sprintf "pas de solution, %d mouvements au mieux" !max_mouvs)
      | (x, y) :: reste_cases_parcourues ->
          match matrice_cases_voisines_restantes.(x).(y) with
          | h::q->
              matrice_cases_voisines_restantes.(x).(y) <- q (* on enleve la case que l'on va tester*) ;
              if (appartient h cases_parcourues)
              then solution cases_parcourues matrice_cases_voisines_restantes
                (*si la case à tester a déjà été parcourue, ne pas la tester*)
              else solution (h::cases_parcourues) matrice_cases_voisines_restantes
          | []-> solution reste_cases_parcourues matrice_cases_voisines_restantes
              (* s'il n'y a plus de cases à tester, alors (pour peu
                 que ce soit possible), on recommence sans la première
                 case parcourue (backtracking) ; on ne repassera pas
                 par cette case là car elle a été supprimée des
                 cases_voisines_restantes quand on est passé dessus la
                 premiere fois *)
  in
  solution [depart] matrice_cases_voisines_restantes ;;

Sur (8,8), le nombre de cases parcourues varie pas mal en fonction du départ :
0 0 : 53
0 1 : 56
0 2 : 57
1 1 : 56
3 3 : 59
4 5 : 60

Quand j'aurai plus de temps, je testerai avec des matrices, en espérant que ce soit nettement plus rapide et que je pourrai donc triompher lâchement.

**gasche** · 09/01/2009, 19h40

Haha, j'ai testé avec des matrices, et je n'ai pas été déçu.

Je commence avec le code suivant, qui reprend des bouts du tien et met en place exactement l'algorithme que j'avais décrit :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
let tour_cavalier_2 (n, p) depart =
  let mouvements = [(2,1);(1,2);(-1,2);(-2,1);(-2,-1);(-1,-2);(1,-2);(2,-1)] in
  let position_valide (x,y) = 0<=x && x<n && 0<=y && y<p in
  let prefix ++ (x, y) (x', y') = x + x', y + y' in
  let echiquier = make_matrix n p true in
  let case_vierge (x, y) = echiquier.(x).(y) in
  let modifie (x, y) v = echiquier.(x).(y) <- v in
  let nb_mouv_max = ref 0 in
  let rec explore nb_mouv pos =
    nb_mouv_max := max !nb_mouv_max nb_mouv;
    let deplace mouvement =
      let pos' = pos ++ mouvement in
      if position_valide pos' && case_vierge pos' then begin
        modifie pos' false;
        explore (nb_mouv + 1) pos';
        modifie pos' true
      end in
    do_list deplace mouvements in
  modifie depart false;
  explore 1 depart;
  !nb_mouv_max;;

Confiant, je le lance sur (8, 8) (0, 0).
...
Rien. Il tourne encore.

J'ai soupçonné une boucle infinie. Pour tester j'enlève le "modifie pos' true" à la fin de "deplace" (ça me fait une fonction tour_cavalier_2bis). Intuitivement je sais qu'il doit être là, mais il t'a fait douter alors essayons. Réponse instantanée : 53.

Tu aurais raison ? Je le remet, et je teste sur (4, 5). Ça marche... et il trouve 20 cases ! Pourtant ton algorithme avait trouvé "17 mouvements au mieux". Mon code serait-il faux ?

Je fais une version modifiée pour pouvoir retourner le chemin trouvé. L'idée c'est qu'au lieu de mettre soit "vrai" (pas encore passé) soit "faux" dans la matrice, on met "rien" (None) ou "je viens de la position machin" (Some pos). Pour pouvoir s'arrêter dès qu'on croit avoir trouvé une solution, je crée une exception qui renvoie la position d'arrêt, et je la rattrape (regarde bien ça, c'est trop simple à rajouter et ça marche super bien; une astuce classique) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
exception Arret of (int * int);;
 
let tour_cavalier_3 (n, p) depart =
  let mouvements = [(2,1);(1,2);(-1,2);(-2,1);(-2,-1);(-1,-2);(1,-2);(2,-1)] in
  let position_valide (x,y) = 0<=x && x<n && 0<=y && y<p in
  let prefix ++ (x, y) (x', y') = x + x', y + y' in
  let echiquier = make_matrix n p None in
  let case (x, y) = echiquier.(x).(y) in
  let modifie (x, y) v = echiquier.(x).(y) <- v in
  let nb_mouv_max = ref 0 in
  let rec explore nb_mouv pos =
    nb_mouv_max := max !nb_mouv_max nb_mouv;
    if nb_mouv = n * p then raise (Arret pos);
    let deplace mouvement =
      let pos' = pos ++ mouvement in
      if position_valide pos' && case pos' = None then begin
        modifie pos' (Some pos);
        explore (nb_mouv + 1) pos';
        modifie pos' None
      end in
    do_list deplace mouvements in
  modifie depart (Some depart);
  try explore 1 depart; failwith "pas de solution"
  with Arret pos_finale ->
    let rec chemin acc pos =
      if pos = depart then acc
      else
        let (Some pos) = case pos in
        chemin (pos :: acc) pos in
    chemin [] pos_finale
;;

Je l'appelle sur (4,5), il me renvoie un chemin résultat, j'essaie sur un bout de papier et... ça marche ! Je ré-essaie sur (8,8), temps de calcul trop long, j'ai encore interrompu le calcul.
J'ai testé sur (5,5), (6,6) etc., et à chaque fois, selon la position de départ, soit il trouve relativement vite, soit je dois l'arrêter. Voici les positions de départ qui marchent bien :
5 5 : (0,0)
5 6 : (0,1)
6 6 : (1,1)
6 7 : (1,1)

Pour 7 7 et au delà, je n'ai trouvé aucune position de départ (je n'ai testé que 0 0, 0 1 et 1 1, je pense que ça doit être les trois seules intéressantes, mais je n'en suis pas sûr) qui renvoie un résultat : ça tourne, ça tourne, et on ne voit rien (une idée intéressante serait de coder un truc qui donne une idée de la progression de l'algorithme).

Conclusion : tu avais en fait raison, il est possible de tout couvrir, mais pas avec ton algorithme qui est "faux" : c'est une heuristique qui renvoie vite et trouve d'assez bons chemins (grand nombre de cases parcourues), mais elle n'est pas assez bonne pour trouver une véritable réponse. Ma version avec un "vrai" backtracking trouve des solutions pour de petits échiquiers, mais elle peine à partir de 7 7.
Y a-t-il un moyen d'accélérer le calcul ? Des cas que l'on peut ne pas essayer ? Des symétries à repérer ?

Au passage, je n'ai pas testé ta méthode du "on commence par les cases avec le moins de voisines disponibles" parce qu'elle est délicate à implémenter avec ma représentation (mais ça doit être possible).

J'ai aussi transformé ton algorithme en l'algorithme correct (il suffit d'enlever la ligne matrice_cases_restantes.(x).(y) <- q), mais il est trop lent pour donner un résultat au delà de (4, 4). J'ai aussi comparé nos deux versions de l'algorithme imparfait (ton code, corrigé par mes soins, et mon tour_cavalier_2), la différence de performances est écrasante. Pour (60, 60), le tien prend entre 5 et 10 secondes pour répondre, le mien répond instantanément. Et l'écart se creuse quand on augmente. C'est mesuré à la louche en comptant à haute voix, il existe des moyens plus sérieux de faire ça, mais c'est tellement flagrant que ce n'est pas la peine.

Un résultat contrasté, donc. Je suis content parce que ma méthode est effectivement plus rapide que la tienne, mais les deux sont "fausses", pas de bol, et la seule méthode correcte que l'on ait pour l'instant est trop lente pour essayer (8,8). Tu as des idées pour améliorer ça ?

En tout cas, j'espère que tu as appris des choses au passage. Et n'hésite pas à poser des questions sur le code si tu ne comprends pas quelque chose (il n'est pas forcément des plus pédagogiques, désolé).

**elishac** · 09/01/2009, 21h36

(pourquoi, quand j'ai actualisé la page à l'instant, chargée la première fois il y a 2 minutes, j'ai vu un nouveau message, écrit à 19h40, alors qu'il est 21h15 ?)

merci pour ta réponse très complète.
tu as écrit beaucoup de choses, j'ai du mal à digérer.
Reprenons dans l'ordre :
je vois effectivement l'erreur "hd failure", qui provient de "hd cases_parcourues". Ok, j'ai compris que j'ai fait mon "failwith pas de solution" un peu trop tard, après avoir utilisé "hd cases_parcourues". Une solution (certes redondante) à ce problème serait je pense de remplacer <<let (x,y)= hd cases_parcourues in>> par <<if list_length cases_parcourues=0 then failwith "pas de solution" else let (x,y)= hd cases_parcourues in>>. La dernière solution que tu proposes marche aussi à mon avis, et elle est certes plus jolie.

Je m'arrête là pour l'instant, et je ne considère pas encore les optimisations que tu proposes avec le renvoi du chemin maximum ou de la case initiale.

Je ne comprends pas (théoriquement) pourquoi cela ne marcherait pas (et je ne comprends pas pourquoi "Pour (8,8) il en fait 53 sur 64", dans l'implémentation avec le chemin maximum mais sans case initiale).
En effet, je suis en mesure de te présenter à la main un exemple d'un chemin qui marche pour un échiquier (8,8) ; donc l'algorithme devrait au moins trouver le mien, non ? (d'ailleurs, il y a des milliards de chemins pour un (8,8)).

**gasche** · 09/01/2009, 22h06

Ton algo ne trouve pas tout simplement parce qu'il n'essaie pas toutes les possibilités. En effet, si tu te trouves sur une case A et que tu essaies de passer par une case B, et que ça ne marche pas, tu essaies en passant par d'autres, mais la case B a déjà été retirée des possibilités partant de A. Ça veut dire que si plus tard pendant la recherche (en étant revenu plusieurs fois en arrière) tu te retrouves en A par un autre chemin, tu ne vas pas ré-essayer de passer par B, alors que peut-être cette fois-ci c'était le bon choix.

**elishac** · 09/01/2009, 23h28

Ah oui bien vu !!
Je vois une manière (couteuse?) de palier à ce problème :
on réinitialise (grâce à matrice_cases_voisines_restantes créée au tout début) toutes les cases qui ne font pas partie de cases_parcourues, sauf la dernière que l'on vient de tester (sinon on tournerait en rond).
Par contre, il faut bien différencier matrice_cases_voisines_restantes créée au tout début et matrice_cases_voisines_restantes créée en cours de boucle "rec". Dans la suite de ce post, soit donc M la matrice_cases_voisines_restantes créée au tout début (on garde le même nom pour matrice_cases_voisines_restantes créée en cours de boucle "rec").
Pour ce faire, une solution est de réinitialiser de proche en proche toutes les cases de degré 2 (ou degré n représente le nombre de fois que l'on a été en arrière).
Concrètement, l'endroit où ça se ferait, c'est quand on veut revenir en arrière :

Code :

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

1
2
3
 match matrice_cases_voisines_restantes.(x).(y) with
 | h::q-> ...
 | []-> solution reste_cases_parcourues matrice_cases_voisines_restantes

Juste avant d'appeler de nouveau "solution", on pourrait réinitialiser toutes les cases accessibles depuis (x,y) (la dernière case testée).
Cela donnerait un truc du genre :

Code :

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

1
2
3
4
5
 match matrice_cases_voisines_restantes.(x).(y) with
 | h::q-> ...
 | []-> Pour chaque case (i,j) de la liste M.(x).(y) faire :
   matrice_cases_voisines_restantes.(i).(j) <- M.(i).(j)  fin du faire ; 
solution reste_cases_parcourues matrice_cases_voisines_restantes

**elishac** · 10/01/2009, 03h33

Voilà plus précisément ce que ça donnerait :
(j'ai nommé matrice_cases_voisines_initiale la matrice initialement créée qui donne les cases voisines de chacune des cases de l'échiquier ; j'ai également écrit, de manière un peu abstraite, la boucle que j'avais écrite dans mon précédent message ; je ne suis pas sûr du résultat).

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
let tour_cavalier (n,p) =
	let rec apply_to_list f = function 
		|[]->()
		|h::q-> f h ; apply_to_list f q
	in	
	let rec appartient a = function
		|[]->false
		|h::q-> if h=a then true else appartient a q
	in
	(*debut de l'initialisation de matrice_cases_voisines_initiale *)
	let cases_voisines_restantes (x,y) =
		let add_couple (x,y) (x',y')= (x+x', y+y') in
		let knight_moves = [(2,1);(1,2);(-1,2);(-2,1);(-2,-1);(-1,-2);(1,-2);(2,-1)] in
		let position_valide (x,y) = 0<=x && x<n && 0<=y && y<p in
		let rec aux = function
			|[]->[]
			|h::q->let case_a_tester = add_couple (x,y) h in 
				if position_valide case_a_tester then case_a_tester ::(aux q) else aux q
		in
		aux knight_moves
	in
	let matrice_cases_voisines_initiale =
		let res=make_matrix n p [] in  (*matrice n*p avec la liste des cases_voisines_restantes*)
		for i=0 to n-1 do 
		for j=0 to p-1 do
		res.(i).(j)<- cases_voisines_restantes (i,j)
		done done;
		res
	in
	(* fin de l'initialisation de matrice_cases_voisines_initiale *)
let rec solution cases_parcourues matrice_cases_voisines_restantes =
    if list_length cases_parcourues = n*p then cases_parcourues (*cas d'arret*) else
      match cases_parcourues with
      | [] -> failwith "pas de solution"
      | (x, y) :: reste_cases_parcourues ->
          match matrice_cases_voisines_restantes.(x).(y) with
          | h::q->
              matrice_cases_voisines_restantes.(x).(y) <- q (* on enleve la case que l'on va tester*) ;
              if (appartient h cases_parcourues)
              then solution cases_parcourues matrice_cases_voisines_restantes
                (*si la case à tester a déjà été parcourue, ne pas la tester*)
              else solution (h::cases_parcourues) matrice_cases_voisines_restantes
          | []-> apply_to_list (fun (i,j)-> matrice_cases_voisines_restantes.(i).(j) <- matrice_cases_voisines_initiale.(i).(j)) matrice_cases_voisines_initiale.(x).(y);
		solution reste_cases_parcourues matrice_cases_voisines_restantes
 
in
	solution [(0,0)] matrice_cases_voisines_initiale ;;

Remarque : cette fois-ci, je croyais que l'algorithme allait examiner toutes les solutions, mais je reçois toujours "pas de solution" ?!

**gasche** · 10/01/2009, 11h03

Toi, les problèmes de partage entre tableaux, tu aimes ça !

Même problème que précédement. matrice_..._initiale (quand est-ce que tu réfléchis à un nom plus court ?) et matrice_..._restantes sont le même tableau, donc modifier l'un modifie l'autre, donc c'est exactement le même algorithme qu'avant.

Pour avoir ce que tu voulais, il faut "copier" matrice_..._initiale pour obtenir un tableau ayant les même valeurs, mais qui soit désolidarisé.

Code :

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

solution [(0,0)] (copy_vect matrice_cases_voisines_initiale);;

Sauf que je t'ai tendu un piège. Cette ligne est incorrecte. Quelle est la correction à apporter ?

Une fois qu'on a mis le bon code, on se rend compte que... ça ne marche pas. Plus précisément il boucle, semble-t-il à l'infini (je l'ai laissé le temps de mon petit-dej.). C'est parce que tu as oublié une partie de ton algo :

on réinitialise toutes les cases qui ne font pas partie de cases_parcourues

.

Correction :

Code :

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

1
2
3
4
5
6
              do_list
                (fun (i,j)->
                   if not (mem (i, j) cases_parcourues) then
                     matrice_cases_voisines_restantes.(i).(j) <-
                       matrice_cases_voisines_initiale.(i).(j))
                matrice_cases_voisines_initiale.(x).(y);

Tu remarqueras au passage que le coup du "je sors de mon berceau, je découvre le monde et je recode toutes les fonctions" c'est mignon 5 minutes, mais maintenant t'es une grande personne, va lire la doc et utilise les noms de fonction standard au lieu de tout recoder en moins joli.
Et je n'ai pas non plus parlé de transformer ton "aux" (qui est un filter) en list_it (ou, encore mieux, it_list).

Cette dernière version du code marche. Je l'ai testée sur (5,5) et ça donne un résultat, (5,6) aussi (assez lentement), mais comme t'es assez têtu pour refuser de paramétrer sur la case de départ, il commence par (0,0) qui n'est pas forcément un bon choix et bute sur (6,6).

Question performances par contre c'est toujours aussi mauvais, sur (5,5) ton code met quelques secondes (entre 3 et 5 je dirais) pour répondre alors que ma version matricielle répond quasi-instantanément.

J'ai eu ce matin une idée pour couper des mauvaises branches d'explorations plus tôt : repérer les cases devenues inaccessibles. Je vais voir si on peut la mettre en pratique.

**gasche** · 10/01/2009, 12h37

Bon, j'ai encore tripoté, et le résultat est tout à fait drôle.

Pour commencer je voudrais revenir rapidement sur la version matricielle du backtracking, parce qu'ensuite je change des choses et si tu n'as pas compris là, ça va être difficile :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
  let rec explore nb_mouv pos =
    nb_mouv_max := max !nb_mouv_max nb_mouv;
    if nb_mouv = n * p then raise (Arret pos);
    let deplace mouvement =
      let pos' = pos ++ mouvement in
      if position_valide pos' && case pos' = None then begin
        modifie pos' (Some pos);
        explore (nb_mouv + 1) pos';
        modifie pos' None
      end in
    do_list deplace mouvements in
  modifie depart (Some depart);
  try explore 1 depart; failwith "pas de solution"
  with Arret pos_finale -> (* ... fin du code *)

Le code est plutôt clair : on cherche une solution, quand on la trouve on lance l'exception, et à la fin on la rattrappe. Comment s'effectue précisément la recherche ?

On a une matrice qui contient des (int * int) option : si une case vaut None, elle est vierge, ça veut dire qu'on n'est jamais passé dessus. Si elle vaut "Some pos", on est passé dessus en venant de pos.

Depuis la case courante, on regarde la liste des voisins. Pour chaque voisin valide et dont la case est vierge (pas encore passé dessus) :
- on met sa case à (Some pos_courante)
- on explore à partir de ce voisin
- on met sa case à None

La troisième opération avait l'air de t'étonner, mais elle est en fait naturelle : si l'exploration à partir du voisin aboutit (trouve une solution), alors elle lance une exception et cette troisième opération ne sera pas effectuée. Si on la fait, c'est donc que le choix du voisin était une erreur, et qu'on veut "revenir en arrière". On remet donc sa case vierge, avant de choisir un autre voisin, pour qu'éventuelle cette case puisse être choisie à nouveau plus tard. C'est pour cela que j'ai dit que cette opération représentait le "backtracking".

Je mets maintenant en place mon optimisation : mon idée est de savoir, pour chaque case, à partir de combien de cases vierges différentes je pourrai y accéder. Imagine par exemple la configuration suivante :
O O X O + ...
X X X O O ...

O représente une case vierge, X une case prise, et + la position courante de la recherche. La case en haut à gauche a un nombre d'accès de 0 : toutes les cases qui permettent d'y aller ont déjà été empruntées. Quand je repère ce genre de choses, je sais que quelle que soit l'exploration future vers la droite, je ne pourrai jamais remplir l'échiquier. Je peux donc terminer plus rapidement avec une erreur, pour reprendre l'exploration plusieurs coups avant de m'être mis dans cette situation inextricable.

Au lieu d'une seule exception "Arret of (int * int)" j'utilise donc deux exceptions, "Solution ..." et "Echec" (qui signale une situation impossible) :

Code :

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

1
2
exception Solution of (int * int);;
exception Echec;;

J'ai aussi créé une fonction "do_voisins" qui factorise l'idée "effectue cette action sur tous les voisins valides" :

Code :

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

1
2
3
4
5
6
let do_voisins (x,y) action =
    let position_valide (x,y) = 0<=x && x<n && 0<=y && y<p in
    do_list (fun (dx, dy) ->
               let pos' = (x+dx, y+dy) in
               if position_valide pos' then action pos')
      [(2,1);(1,2);(-1,2);(-2,1);(-2,-1);(-1,-2);(1,-2);(2,-1)] in

Je représente le "nombre d'accessibilités" par une matrice "accessibilite", que j'initialise en chaque case en ajoutant 1 pour chaque voisin (je réutilise donc l'opération do_voisins) :

Code :

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

1
2
3
4
5
6
7
8
  let accessibilite =
    let mat = make_matrix n p 0 in
    for i = 0 to n - 1 do
      for j = 0 to p - 1 do
        do_voisins (i,j) (fun _ -> mat.(i).(j) <- mat.(i).(j) + 1)
      done
    done;
    mat in

Je modifie alors ma fonction d'exploration :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
  let rec explore nb_mouv pos_pere pos =
    if nb_mouv = n * p then raise (Solution pos);
    try do_voisins pos
      (fun ((x, y) as pos') ->
         if case pos' = None then
           let access = accessibilite.(x).(y) in
           modifie pos' (Some pos);
           accessibilite.(x).(y) <- access - 1;
           explore (nb_mouv + 1) pos pos';
           modifie pos' None;
           accessibilite.(x).(y) <- access;
           if access = 1 then raise Echec)
    with Echec -> ()
  in

Si tu as compris l'idée du backtracking précédent, c'est pareil : je commence par baisser le nombre d'accessibilité de la case que je vais tester, puis je le remonte après l'exploration pour "annuler" le changement. Je teste ensuite si l'accessibilité est 1 : si elle est 1, ça veut dire que pendant l'exploration de pos' elle était à 0, mais que pos' n'a pas donné de solution. pos' est donc inaccessible et je peux couper l'exploration. Je rattrappe l'exception Echec au niveau de "pos" : si l'un des voisins devient inaccessible, ce n'est pas la peine de regarder les autres voisins, et on peut arrêter tout de suite l'exploration à ce niveau (-> () ).

Je pense que le code est juste, il renvoie le même résultat que mes fonctions précédentes, beaucoup plus rapidement que tes manipulations de listes, mais un peu plus lentement que ma fonction d'avant (il y a les matrices à gérer en plus). L'ajout d'une instruction de debuggage montre qu'en fait, pour le cas simple (5, 5), l'exploration n'est jamais coupee; Echec n'est jamais levée, la solution est trouvée avant qu'un cas d'inacessibilité se présente.

J'ai été un peu déçu par ce résultat alors j'ai essayé un truc un peu stupide : au lieu de couper quand la case devient inaccessible (accessibilité 0), on coupe dès qu'elle a moins de 4 accessibilités. Ça a l'air débile (et intuitivement ça ne devrait pas marcher dans les coins) parce qu'on va rater des solutions qui pourraient être les bonnes. Mais en pratique, ça marche bien, très bien même : il trouve une solution pour (8, 8) !

Comme j'étais incrédule, j'ai codé au passage une fonction d'affichage du chemin trouvé :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
let affiche_chemin (n, p) chemin =
  let mat = make_matrix n p 0 in
  let coup = ref 0 in
  let joue (x, y) = incr coup; mat.(x).(y) <- !coup in
  do_list joue chemin;
  for i = 0 to n - 1 do
    for j = 0 to p - 1 do
      printf__printf "%-3d" mat.(i).(j)
    done;
    print_newline ()
  done

Récapitulation de ma fonction optimisée :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
let tour_cavalier_5 (n, p) depart =
  let echiquier = make_matrix n p None in
  let do_voisins (x,y) action =
    let position_valide (x,y) = 0<=x && x<n && 0<=y && y<p in
    do_list (fun (dx, dy) ->
               let pos' = (x+dx, y+dy) in
               if position_valide pos' then action pos')
      [(2,1);(1,2);(-1,2);(-2,1);(-2,-1);(-1,-2);(1,-2);(2,-1)] in
  let accessibilite =
    let mat = make_matrix n p 0 in
    for i = 0 to n - 1 do
      for j = 0 to p - 1 do
        do_voisins (i,j) (fun _ -> mat.(i).(j) <- mat.(i).(j) + 1)
      done
    done;
    mat in
  let case (x, y) = echiquier.(x).(y) in
  let modifie (x, y) v = echiquier.(x).(y) <- v in
  let rec explore nb_mouv pos_pere pos =
    if nb_mouv = n * p then raise (Solution pos);
    try do_voisins pos
      (fun ((x, y) as pos') ->
         if case pos' = None then
           let access = accessibilite.(x).(y) in
           modifie pos' (Some pos);
           accessibilite.(x).(y) <- access - 1;
           explore (nb_mouv + 1) pos pos';
           modifie pos' None;
           accessibilite.(x).(y) <- access;
           if access <= 5 then raise Echec)
    with Echec -> ()
  in
  try explore 1 depart depart; failwith "pas de solution"
  with Solution pos_finale ->
    let rec chemin acc pos =
      if pos = depart then acc
      else
        let (Some pos) = case pos in
        chemin (pos :: acc) pos in
    chemin [] pos_finale
;;

Voici la solution pour (8, 8) :

#affiche_chemin (8,8) (tour_cavalier_5 (8,8) (0, 0));;
1 46 35 58 29 18 9 0
36 59 28 45 10 63 30 17
47 2 61 34 57 32 19 8
60 37 44 27 62 11 16 31
43 48 3 56 33 24 7 20
38 55 40 51 26 21 12 15
49 42 53 4 23 14 25 6
54 39 50 41 52 5 22 13
- : unit = ()

L'heuristique utilisée est assez curieuse. Théoriquement, elle devrait échouer sur des problèmes solubles (tous ceux où on passe forcément par une accessibilité inférieure à 4 à un moment donné), mais les solutions qu'elle trouve sont valides (car le cas d'arrêt Solution ne dépend pas de ça).

Elle trouve une solution pour (8, 8) et (10, 10), mais pas pour (9, 9) ou (12, 12). Je ne comprends pas très bien pourquoi, mais je n'ai pas réfléchi à la structure du problème.

De plus, la recherche de solution dépend beaucoup du choix de la coupure : si on met 4 ou 6 à la place de 5, ça ne marche visiblement plus aussi bien. Il faudrait faire des tests plus poussés pour comprendre de quoi il retourne.

**elishac** · 10/01/2009, 13h47

Encore une fois merci pour ces réponses poussées.
Revenons lentement sur les idées proposées.

Code :

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

solution [(0,0)] (copy_vect matrice_cases_voisines_initiale);;

je ne vois pas pourquoi ça ne marcherait pas.

Une fois qu'on a mis le bon code, on se rend compte que... ça ne marche pas. Plus précisément il boucle, semble-t-il à l'infini (je l'ai laissé le temps de mon petit-dej.). C'est parce que tu as oublié une partie de ton algo :

on réinitialise toutes les cases qui ne font pas partie de cases_parcourues

Je croyais que, si on réinitialisait de proche en proche toutes les cases de degré 2, on aurait réinitialisé toutes les cases. Pourquoi serait-ce faux ?

Tu remarqueras au passage que le coup du "je sors de mon berceau, je découvre le monde et je recode toutes les fonctions" c'est mignon 5 minutes, mais maintenant t'es une grande personne, va lire la doc et utilise les noms de fonction standard au lieu de tout recoder en moins joli.

Ca c'est pour toi qui est habitué aux fonctions évoluées. Moi, il faut que je les fasse moi meme pour comprendre ce qu'elles font, sinon je suis perdu

.

comme t'es assez têtu pour refuser de paramétrer sur la case de départ

Il y a une raison à cela. Pour la plupart des échiquiers (ceux qui sont de taille paire et n,p>5, par exemple), on peut montrer mathématiquement que toutes les cases sont équivalentes (ça provient du fait qu'il existe un tour où la case de départ est accessible à partir de la case d'arrivée, donc que l'on peut commencer où l'on veut, en se mordant la queue).

J'ai eu ce matin une idée pour couper des mauvaises branches d'explorations plus tôt : repérer les cases devenues inaccessibles. Je vais voir si on peut la mettre en pratique.

oui. Sauf erreur, cela revient en gros à considérer mon algorithme de recherche de la case ayant le minimum de possibilités, et je pense que ma méthode est plus simple à implémenter (il suffit de créer une fonction qui donne le minimum d'une liste, en gros).

ps: je n'ai toujours pas bien compris pourquoi l'utilisation de listes est plus couteuse, alors qu'elles sont en theorie plus adaptées aux fonctions recursives.

**Jedai** · 10/01/2009, 14h31

C'est bien de chercher dans votre coin, mais vous pourriez aussi regarder autour de vous et voir ce que d'autres ont fait. Le problème du tour du cavalier est classique et effectivement, comme l'a dit elishac, la case de départ importe peu et tous les échiquiers à partir d'un certain rang ont une solution. Il y a même une heuristique qui donne ces solutions en temps record (et elishac en a parlé au début) : on classe les cases en fonctions du nombres de cases auxquelles elles peuvent accéder (pas à partir desquelles elles sont accessible).

Quelques solutions en Haskell.

--
Jedaï

alex_pi · 10/01/2009, 15h51

Envoyé par Jedai

on classe les cases en fonctions du nombres de cases auxquelles elles peuvent accéder (pas à partir desquelles elles sont accessible).

C'est pas rigoureusement la même chose ?

**Jedai** · 10/01/2009, 19h12

Envoyé par alex_pi

C'est pas rigoureusement la même chose ?

Ca m'apprendra à poster sans réfléchir...

Néanmoins il semblerait que l'heuristique ait été mal implémentée puisqu'apparemment les performances restent décevantes (par rapport aux 0.05s que met l'une des solutions Haskell que j'ai posé pour résoudre un 40x40).

--
Jedaï

**gasche** · 10/01/2009, 19h39

Bah, je l'ai pas complètement implémentée, j'ai juste mis en place le décompte et pruné comme un gros sale. Je vais tester en triant comme suggéré (j'avais prévu de le faire mais j'ai fait d'autres choses), ça devrait effectivement marcher.

C'est bien de chercher dans votre coin, mais vous pourriez aussi regarder autour de vous et voir ce que d'autres ont fait.

Oui et non. Ton ton est assez sec et on dirait que tripoter dans son garage, c'est sale. Je ne suis pas vraiment d'accord et j'ai regardé ça parce que ça m'amusait d'expérimenter sur un petit truc, et je trouve que la phase de bidouillage/recherche_perso apporte des choses que "hoho on va regarder ce que disent les bons sur google" n'a pas. Clairement s'il s'était agit de googler la meilleure façon de résoudre un sudoku (par exemple) je n'aurais rien fait.

Tour du Cavalier (débutant)

Caml

Discussions similaires

Partager

Partager