Ce que chaque test d'élagage rapporte

Les trois programmes trouvent le même nombre de solutions, ce qui a été vérifié à chaque ligne. Les nœuds visités, eux, mesurés en instrumentant les trois versions :

Trois lectures de ce tableau.

Le nombre de nœuds de (a) vaut $1+n+n^2+\cdots +n^n$ — c'est l'arbre complet des placements. Pour $n=6$ : $55987$, et l'on vérifie ${\sum }_{k=0}^6{6}^k=55987$.

Le test des lignes seul fait passer de $n^n$ à ${\sum }_{k=0}^n\frac{n!}{(n-k)!}$ — les arrangements. À $n=8$, c'est déjà un facteur $175$.

Le test des diagonales apporte encore un facteur $53$ à $n=8$, et $278$ à $n=10$. Il rapporte donc plus que le test des lignes, alors qu'il tient sur la même ligne de code. C'est la leçon : ce n'est pas le nombre de conditions qui compte, c'est leur pouvoir de coupe — et celui-ci croît avec la profondeur à laquelle la condition mord.

Et l'élagage ne change pas la classe : de $6$ à $10$, la colonne (c) passe de $153$ à $35539$, soit un facteur $232$ pendant que $n$ augmente de $4$. C'est toujours exponentiel — plus lentement, voilà tout.