Début commentaires TIPE

let M=3 and N=4;; (*On modifie ici les dimensions qu'on donne à l'échiquier, M est la longueur horizontale*)

(*On commence par créer les matrices et objets qui nous serviront plus tard*)
type POSITION = {mutable x: int; mutable y: int};;
let parcours = make_matrix M N 0;;
let poids = make_matrix M N 0;;

(*On initialise les matrices "parcours" et "poids" qu'utilisent les programmes finaux*)
let initialiserParcours mat =
 for i=0 to M-1 do
  for j=0 to N-1 do
   mat.(i).(j) <- 0
  done
 done;;

let initialiserPoids mat =
 let nb_accessibles = ref 0 and deltaX = [|2;1;-1;-2;-2;-1;1;2|] and deltaY = [|1;2;2;1;-1;-2;-2;-1|] in
  for i=0 to M-1 do
   for j=0 to N-1 do
    nb_accessibles := 0;
    for k=0 to 7 do
     if (i+deltaX.(k) >= 0 && i+deltaX.(k) < M) && (j+deltaY.(k) >= 0 && j+deltaY.(k) < N ) then
      nb_accessibles := !nb_accessibles + 1
     done;
    mat.(i).(j) <- !nb_accessibles;
   done;
 done;;

(*Premier programme destiner à afficher de façon lisible les matrices qui donneront les parcours du cavalier*)
let afficher mat =
let n=vect_length mat and m=vect_length mat.(0) in
 print_newline();
 for i=0 to N-1 do
  for j=0 to M-1 do
   if (mat.(j).(i))>99 then begin print_int mat.(j).(i); print_string "|"; end
   else if (mat.(j).(i))>9 then begin print_string " "; print_int mat.(j).(i); print_string "|"; end
   else begin print_string "  "; print_int mat.(j).(i); print_string "|"; end
  done;
  print_newline();
 done
;;

(*1er programme pour l'application de l'heuristique de Warnsdorff: il met à jour la matrice poids à chaque déplacement du cavalier*)
let miseAJourPoids p =
 let deltaX = [|2;1;-1;-2;-2;-1;1;2|] and deltaY = [|1;2;2;1;-1;-2;-2;-1|] (*modélisent tous les déplacements du cavalier*) and pCur=ref { x=0; y=0 } in
  for i = 0 to 7 do
   begin
   (!pCur).x <- p.x + deltaX.(i);
   (!pCur).y <- p.y + deltaY.(i);
    if ((!pCur).x >= 0 && (!pCur).x < M) && ((!pCur).y >= 0 && (!pCur).y < N ) (*on vérifie si le déplacement est possible sans sortir de l'échiquier*) then
     poids.((!pCur).x).((!pCur).y) <- poids.((!pCur).x).((!pCur).y) - 1;
   end
  done
;;

(*Programme coeur pour l'heuristique: il détermine la prochaine case sur laquelle devra se déplacer le cavalier*)
let Warnsdorff p =
 let deltaX = [|2;1;-1;-2;-2;-1;1;2|] and deltaY = [|1;2;2;1;-1;-2;-2;-1|] (*modélisent tous les déplacements du cavalier*)
 and pMin = ref { x=0; y=0 } and poidsMin = ref 9 and iMin = ref 0 in
  miseAJourPoids p;
  for i = 0 to 7 do (*cad pour chaque déplacement*)
   begin
   (!pMin).x <- p.x + deltaX.(i);
   (!pMin).y <- p.y + deltaY.(i);
   if (*plusieurs vérifications:*) ((!pMin).x >= 0 && (!pMin).x < M) && ((!pMin).y >= 0 && (!pMin).y < N ) (*si la case est dans l'échiquier*)
    && (parcours.((!pMin).x).((!pMin).y) = 0) (*si la case n'a pas encore été atteinte par le cavalier*)
    && (poids.((!pMin).x).((!pMin).y) < !poidsMin) (*on compare le poids des cases*) then
    begin
     poidsMin := poids.((!pMin).x).((!pMin).y);
     iMin := i;
    end
   end
  done;
  if (!poidsMin) = 9 then failwith "Pas de parcours possible"; (*dans le cas où le cavalier est arriver dans une impasse*)
  {x=p.x + deltaX.(!iMin); y=p.y + deltaY.(!iMin)};;

(*Programme coeur qui synchronise les différentes briques de programmation:*)
let parcourir x y =
 let p = ref { x=x; y=y } and i = ref 2 in
 begin
 while (!i<=M*N) do
  p:=Warnsdorff(!p);
   if ((!p).x >= 0) then begin
    parcours.((!p).x).((!p).y) <- !i;
    i:=!i+1;
    end
   else i:=M*N+1;
  done;
  if ((!p).x >= 0) then
   afficher parcours
  else failwith "Pas de solution trouvee"
end;;

(*Programme final avec choix de la case de départ:*)
let principale x y =
 initialiserParcours parcours; initialiserPoids poids;
 parcours.(x).(y) <- 1; parcourir x y
;;

for i= 0 to M-1 do for j=0 to N-1 do principale i j done; done;;

let M = 6 and N = 6;;

(*Programme qui copie une matrice dans une autre:*)
let copie mat1 mat2 =
let n=vect_length mat1 and m=vect_length mat1.(0) in
 for i=0 to n-1 do
  for j=0 to m-1 do
   mat2.(i).(j) <- mat1.(i).(j);
  done;
 done;
;;

let rec parcourir_backtracking x y mat n =
 let deltaX = [|2;1;-1;-2;-2;-1;1;2|] and deltaY = [|1;2;2;1;-1;-2;-2;-1|] and pos = ref {x=0;y=0} and i = ref 0 and s = ref [] and parcours = ref (make_matrix M N 0) in
 while (!i < 8) do
   (!pos).x <- x + deltaX.(!i);
   (!pos).y <- y + deltaY.(!i);
   if ((!pos).x >= 0 && (!pos).x < M) && ((!pos).y >= 0 && (!pos).y < N )  then
    begin
     if (mat.((!pos).x).((!pos).y) = 0) then
     begin
      copie mat (!parcours);
      (!parcours).(x).(y) <- n;
      (!parcours).((!pos).x).((!pos).y) <- n+1;
      s := ( parcourir_backtracking ((!pos).x) ((!pos).y) (!parcours) (n+1) )@(!s);
     end
     else if (mat.((!pos).x).((!pos).y) = 1) && n>=(M*N) then
       s := mat::(!s);
    end;
    if (!s)<>[] then i:=9;
   i:=!i+1;
 done;
 !s
;;


let principale_backtracking x y =
 afficher ( hd (parcourir_backtracking x y (make_matrix M N 0) 1 ) )
;;

principale_backtracking 1 1;;

let rec afficherliste = function
|[]-> failwith "Pas de solution trouvee"
|a::q->begin
    afficher a;
    afficherliste q;
end
;;

principale_backtracking 0 0;;