(* Tentative de Résolution du Taquin avec A* *)

type taquin = { vide : int * int ; cases : int array array }

type deplacement = H | B | G | D

let taqWin = { vide = (0,0); cases = [| 
            [| 0; 1; 2; 3 |];
            [| 4; 5; 6; 7 |]; 
            [| 8; 9; 10; 11 |];
            [| 12; 13; 14; 15 |]; |]};;

(* taquins exemples *)

let taq1 = { vide = (0,1); cases = [|
          [| 1; 0; 2; 7 |];
          [| 4; 5; 3; 6 |];
          [| 8; 9; 10; 11 |];
          [| 12; 13; 14; 15 |]; |]};;

let taq2 = { vide = (1,1) ; cases = [|
          [| 4; 6; 1; 3 |];
          [| 8; 0; 2; 7 |];
          [| 10; 12; 14; 11 |];
          [| 9; 13; 5; 15 |]; |]};;

(* Fonctions utilitaires *)

let affiche_taquin taq =
  Printf.printf "-------------\n";
  for i = 0 to 3 do
    for j = 0 to 3 do
      let v = taq.cases.(i).(j) in
      if v = 0 then 
        Printf.printf "|  "
      else if  v < 10 then
        Printf.printf "| %d" v
      else
        Printf.printf "|%d" v
    done;
    Printf.printf "|\n"
  done;
  Printf.printf "-------------\n"
;;

affiche_taquin taqWin;;
affiche_taquin taq1;;
affiche_taquin taq2;;


(** Le jeu **)

let coups_possibles taq = match taq.vide with
(* les coins, les bords, le milieu *)
| (0, 0) -> [B; D]
| (3, 0) -> [H; D]
| (0, 3) -> [B; G]
| (3, 3) -> [H; G]
| (0, _) -> [B; G; D]
| (3, _) -> [H; G; D]
| (_, 0) -> [H; B; D]
| (_, 3) -> [H; B; G]
| (_, _) -> [H; B; G; D]
;;

let joue taq depl = 
  let cases = Array.make_matrix 4 4 0 in
  for i = 0 to 3 do
    for j = 0 to 3 do
      cases.(i).(j) <- taq.cases.(i).(j)
    done
  done;
  let iv, jv = taq.vide in (* ancienne case vide *)
  let inv, jnv = match depl with (* nouvelle case vide *)
    | B -> (iv+1, jv)
    | H -> (iv-1, jv)
    | G -> (iv, jv-1)
    | D -> (iv, jv+1)
  in
  cases.(iv).(jv) <- cases.(inv).(jnv);
  cases.(inv).(jnv) <- 0;
  { vide = (inv, jnv) ; cases = cases }
;;

let rec joue_partie taq coups = match coups with
| [] -> taq
| depl::ccoups -> let taq2 = joue taq depl in joue_partie taq2 ccoups
;;

(* Affiche *)
let affiche_voisins taq =
  let cp = coups_possibles taq in
  let voisins = List.map (fun c -> joue taq c) cp in
  List.iter affiche_taquin voisins;;

Printf.printf "Voisins de taq1\n";
affiche_voisins taq1;
Printf.printf "Voisins de taq2\n"; 
affiche_voisins taq2;;

(** L' Heuristique **)

(* les coordonnées cibles pour chaque valeur *)
let coord_cible = 
  let tab = Array.make 16 (0,0) in
  for i = 0 to 3 do
    for j = 0 to 3 do
      tab.(taqWin.cases.(i).(j)) <- (i,j)
    done
  done;
  tab;;

let h taq = 
  let s = ref 0 in
  for i = 0 to 3 do
    for j = 0 to 3 do
      let v = taq.cases.(i).(j) in
      let (i_c, j_c) = coord_cible.(v) in
      s := !s + abs (i - i_c) + abs (j - j_c)
    done
  done; !s
;;

Printf.printf "h(taq1)=%d h(taq2)=%d\n" (h taq1) (h taq2);;

(** La File de priorité : liste (element, prio) trié par priorité croissante **)

type 'a fileprio = { mutable liste : ('a * int) list };;


(* let testFP () =
  let fp = creeFP() in
  ajouterFP fp "test" 3;
  ajouterFP fp "ceci" 1;
  ajouterFP fp "est un" 2;
  while not (estVideFP fp) do
    let s = extraireMinFP fp in print_endline s
  done;; *)



(** Les associations : taquin ->  distance, deplacement **)





(** Algo A* **)

exception Success;;



(* Resolution *)