(* Correction TP 02 - Exercice 1 - N Reines en OCaml *)

(* affiche un plateau nxn, et les reines positionnées *)
let affiche n lpos =
  (* n : la taille de l'échiquier  -  lpos : la liste des positions des reines *)
  let echiquier = Array.make_matrix n n false in
  let num_col = ref 0 in
  let marque i = 
    echiquier.(i).(!num_col) <- true;
    incr num_col
  in
  List.iter marque (List.rev lpos);
  print_endline "-PLATEAU-";
  for i = 0 to n-1 do
    for j = 0 to n-1 do
      print_string (if echiquier.(i).(j) then "X" else "O")
    done;
    print_newline ()
  done;
  print_endline "--------"
;;

affiche 8 [4;2;0];;


(* affiche les solutions au problème des n-reines, et renvoie le nombre de solutions *)
let pb_reines n =
  (* deux positions sont-elles compatibles (ne se menacent pas) ?*)
  let compatible (i1,j1) (i2,j2) =
    (i1 <> i2) && (j1 <> j2) && (abs (i2-i1) <> abs (j2-j1))
  in

  (* construit la liste des postions occupées par les reines *)
  let rec positions lpos k =
    match lpos with
    | [] -> []
    | i::llpos -> (i,k-1)::(positions llpos (k-1))
  in
  
  let nbsol = ref 0 in (* compteur *)

  (* le plateau etant partiellement rempli de gauche à droite (indiqué par lpos),
       on essaie de placer une reine à la colonne k *)
  let rec construit lpos k =
    if (k = n) then begin
      (* affiche n lpos; *)
      nbsol := !nbsol + 1
    end else
      let pos = positions lpos k in
      for i = 0 to n - 1 do
        (* on essaie de placer la reine à la ligne i *)
        if List.for_all (compatible (i,k)) pos then (* NB : application partielle ! *)
          construit (i::lpos) (k+1)
      done
  in
  construit [] 0; 
  Printf.printf "n=%d : %d solutions\n" n !nbsol;;


for n = 0 to 11 do 
  pb_reines n
done;;