Info_MPSI/MP/JALLAT_backtracking.ml

let rec creer_nuage_aux x l = match x with
| 0 -> []
| _ -> (Random.float 10., Random.float 10.)::(creer_nuage_aux (x-1) l);;

let creer_nuage x = creer_nuage_aux x [];;
let nuage1_list = creer_nuage 10;;
let nuage1_array = Array.of_list nuage1_list;;
type nuage = float*float array;;


let point_extremal nuage = let n = Array.length nuage and  aux = ref (snd nuage.(0)) in
  for i = 1 to n-1 do
    for j = 0 to 1 do
      if snd (nuage.(i)) < !aux then aux := snd (nuage.(i))
  done;
done;
;;

let virage_a_gauche point1 point2 point3 = let (x1,y1) = point1 and (x2,y2) = point2 and (x3,y3) = point3 in

;;

type element = Vide | Fixe of int | Variable of int;;
let grille = element array array;;
let taille = 9;;

let int_of_element (elt:element):int =
  match elt with
  | Vide -> failwith "case vide"
  | Fixe x -> x
  | Variable x -> x
;;

let case_suivante ((a,b):int*int): int*int =
  if b < taille - 1 then (a,b+1) else (a+1,0)
;;

let case_precedente ((a,b):int*int):int*int =
  if b>0 then (a,b-1) else (a-1,taille-1)
;;

let valeurs_interdites_ligne (g:grille) ((i,j):int*int) : int list =
  let l = ref [] in
    for y = 0 to taille - 1 do
      if (y<>j) && (g.(i)(y)<> Vide) then
        then l := (int_of_element g.(i).(y)) :: l
    done;
    !l
;;

let valeurs_interdites_colonne (g:grille) ((i,j):int*int) : int list =
  let l = ref [] in
    for x = 0 to taille - 1 do
      if (x<>i) && (g.(x)(j)<> Vide) then
        then l := (int_of_element g.(x).(j)) :: l
    done;
    !l
;;

let valeurs_interdites_blocs (g:grille) ((i,j):int*int) : int list =
  let l = ref [] and ib = 3 *(i/3) and jb = 3*(j/3) in
    for x = ib to ib+2 do
      for y = jb to jb+2 do
      if ((x,y)<>(i,j)) && (g.(x)(y)<> Vide) then
        then l := (int_of_element g.(x).(j)) :: l
    done;
  done;
    !l
;;

let valeur_test (g:grille) ((i,j):int*int) : int list =
  let vil = valeurs_interdites_ligne g (i,j) and
      vib = valeurs_interdites_blocs g (i,j) and
      vic = valeurs_interdites_colonne g (i,j) and
      l = ref [] in
    for a = 1 to taille -1 do
      if not ((List.mem a vil) || (List.mem a vic) || (List.mem a vib)) then
        l:= a::!l
    done;
    !l
;;

let est_fixe (g:grille) ((i,j):int*int):bool =
  match g.(i).(j) with
  | Fixe _ -> true
  | _ -> false
;;

let sudoku g =
  let i = ref 0 and j = ref 0 and
  g_test = Array.make_matrix taille taille [] in
  if not (est_fixe g (0,0)) then
    g_test.(0).(0)<- valeur_test g (0,0);
  while (!i>-1) && (!i<taille) do
    if (est_fixe g (!i,!j))
      then
        begin
          let (x,y) = case_suivante (!i,!j) in
            if (x<taille) && (not(est_fixe g (x,y)))
              then g_test(!i).(!j)<- valeur_test g (x,y);
            i := x;
            j := y
        end
      else
        begin
          if (g_test.(!i).(!j) = [])
            then
              begin
                while (!i > -1) && (((est_fixe g (!i,!j))) || (g_test.(!i).(!j) = [])) do
                  if not(est_fixe g (!i,!j)) then g.(!i).(!j)<- Vide
                  let (x,y) = case_precedente (!i,!j) in
                  i:=x;
                  j:=y;
                done;
              end;
          else
            begin
              g.(!i).(!j) <- Variable(List.hd g_test.(!i).(!j));
              g_test.(!i).(!j) <- List.tl g_test.(!i).(!j);
              let (x,y) = case_suivante (!i,!j) in
                if (x<taille) && (not (est_fixe g (x,y)))
                  then g_test.(x).(y) <- valeur_test g (x,y)
              i:=x;
              j:=y;
            end
          end
        done;
        g
;;