Le même élagage, dix fois plus vite

Le nombre de nœuds ne change pas d'un seul : les deux versions coupent aux mêmes endroits, elles ne diffèrent que par le prix du test.

(* Une reine en (c, l) occupe la ligne l, la diagonale montante c + l et la
   diagonale descendante c - l ; on décale cette dernière de n-1 pour indexer. *)
let reines n =
  let ligne = Array.make n false in
  let montante = Array.make (2*n) false and descendante = Array.make (2*n) false in
  let total = ref 0 in
  let rec explorer c =
    if c = n then incr total
    else
      for l = 0 to n - 1 do
        if not ligne.(l) && not montante.(c + l) && not descendante.(c - l + n - 1)
        then begin
          ligne.(l) <- true; montante.(c + l) <- true; descendante.(c - l + n - 1) <- true;
          explorer (c + 1);
          ligne.(l) <- false; montante.(c + l) <- false; descendante.(c - l + n - 1) <- false
        end
      done
  in explorer 0; !total

Temps mesurés, les deux versions rendant les mêmes comptes de solutions :

Trois observations, et la troisième est celle qui compte.

D'abord, le rapport croît avec $n$ : le test coûteux est $O(c)$, donc son surcoût moyen grandit avec la profondeur de l'arbre.

Ensuite, le prix payé est trois lignes à défaire au lieu de zéro. La version du cours n'avait rien à défaire, car $\mathtt{pos}(c)$ était réécrite au tour suivant ; ici, trois tableaux sont modifiés et doivent être restaurés. On a échangé de la vitesse contre le risque de l'exercice 14.3.

Enfin — et c'est la leçon — un facteur $13$ ne change rien à la nature du problème. Cette version calcule $n=13$ en deux secondes ; à $n=17$ elle mettra des heures. L'optimisation constante recule le mur ; seul un changement de méthode le supprime, et pour les $n$ reines il n'y en a pas.