La ligne qu'on oublie : combien de solutions produit-elle ?

void explorer(int k) {
    if (k == n) { compte = compte + 1; return; }
    for (int c = 0; c < n; c = c + 1) {
        if (!utilise[c]) {
            utilise[c] = true;  perm[k] = c;
            explorer(k + 1);
            utilise[c] = false;      /* <-- LA LIGNE */
        }
    }
}

Avec la ligne, le programme trouve $n!$ permutations. Sans elle, il en trouve exactement une, quel que soit $n$ :

Pour $n=3$, la sortie complète passe de 012 021 102 120 201 210 à 012.

Pourquoi une seule. Sans le defaire, la première descente marque $0$, $1$ puis $2$ comme utilisés et compte la permutation 012. Au retour, aucun de ces trois marquages n'est annulé : tous les tests if (!utilise[c]) des tours suivants échouent, et la remontée traverse toutes les boucles sans jamais redescendre.

Ce qu'il faut en retenir, et le cours l'annonce autrement. L'oubli de defaire produit un résultat faux — mais le sens de l'erreur dépend de ce que defaire annulait. Ici, l'état non annulé est une interdiction : elle survit à la remontée, et l'on trouve trop peu. Si l'état non annulé était au contraire un élément ajouté à une solution partielle, on trouverait des solutions trop longues, et trop nombreuses. Dans les deux cas, ni erreur ni plantage.

Comment on l'attrape. Par un test sur un cas dont on connaît la réponse d'avance : $n!$ pour les permutations, $92$ pour les huit reines. C'est la discipline du chapitre chap:discipline : un retour sur trace se teste toujours sur un comptage connu, jamais sur l'inspection de sa sortie.