(* Le problème des N-reines.

   Variante du programme 16 page 112 pour renvoyer la première solution
   trouvée plutôt que compter le nombre total de solutions. *)

module S = Set.Make(struct type t = int let compare = compare end)

let map f s = S.fold (fun x s -> S.add (f x) s) s S.empty

let rec upto n = if n < 0 then S.empty else S.add n (upto (n-1))

(* la taille de l'échiquier *)
let n =
  try int_of_string Sys.argv.(1)
  with  _ -> Printf.printf "%s <entier>\n" Sys.argv.(0); exit 1

(* la solution en cours de construction *)
let solution = Array.make n 0

(* i     = la prochaine ligne considérée
   cols  = l'ensemble des colonnes non encore remplies
   d1,d2 = les colonnes de la ligne i en prise avec des lignes inférieures *)
let rec solve i cols d1 d2 =
  if S.is_empty cols then
    raise Exit (* on a trouvé une solution *)
  else
    S.iter
      (fun c ->
        solution.(i) <- c; (* on enregistre le choix qui est fait *)
        let d1 = map succ (S.add c d1) in
        let d2 = map pred (S.add c d2) in
        solve (i + 1) (S.remove c cols) d1 d2 (* on passe à la ligne suivante *)
      )
      (S.diff (S.diff cols d1) d2)

let () =
  try
    solve 0 (upto (n - 1)) S.empty S.empty;
    Printf.printf "pas de solution\n"
  with Exit ->
    Printf.printf "voici une solution:\n";
    for i = 0 to n - 1 do
      for j = 0 to n - 1 do
        Printf.printf (if solution.(i) = j then "X" else ".")
      done;
      Printf.printf "\n"
    done

(*

en lançant le programme avec 8 sur la ligne de commande on obtient

voici une solution:
X.......
....X...
.......X
.....X..
..X.....
......X.
.X......
...X....

(c'est la même solution qu'à la page 110, mais tournée de 90 degrés)
*)

This document was generated using caml2html