Les $n$ reines

let n_reines n =
  let rec compatible ligne reines distance =
    match reines with
    | [] -> true
    | l :: reste ->
        l <> ligne && l - ligne <> distance && ligne - l <> distance
        && compatible ligne reste (distance + 1)
  in
  let rec place col reines =
    if col = n then 1
    else begin
      let total = ref 0 in
      for ligne = 0 to n - 1 do
        if compatible ligne reines 1 then
          total := !total + place (col + 1) (ligne :: reines)
      done;
      !total
    end
  in
  place 0 []

n_reines 4 $=2$, n_reines 8 $=92$. La fonction compatible vérifie, en remontant les colonnes (distance croissante), qu'aucune reine n'est sur la même ligne ni sur l'une des deux diagonales. L'élagage (on ne descend que si compatible) rend l'exploration praticable.