(* 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;;