Les huit reines par le hasard

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 25 — Algorithmes probabilistes, approximation, séparation et évaluation

Énoncé

La version Las Vegas tire une permutation au hasard et recommence tant qu'elle n'est pas valide.

Combien de permutations de ${0, \dots, 7}$ décrivent un placement valide ?
Combien d'essais faut-il en espérance ?
Comparer au retour sur trace.

Corrigé

1. Une permutation garantit déjà qu'aucune reine ne partage sa ligne ni sa colonne ; il reste à écarter les diagonales. L'énumération des $8! = 40320$ permutations en donne 92 valides — ce sont les $92$ solutions du problème des huit reines.

2. Chaque essai réussit avec probabilité $p = 92/40 320 \approx 0, 002282$ , indépendamment des précédents. Le nombre d'essais suit donc une loi géométrique, d'espérance

$E [essais] = \frac{1}{p} = \frac{40 320}{92} \approx 438, 26.$

Mesure sur $20000$ exécutions : $437, 37$ essais en moyenne. L'accord est excellent, et il confirme le raisonnement plutôt qu'il ne le remplace.

Pour d'autres tailles :

$n$	permutations valides	sur $n!$	$1/ p$	essais mesurés
$4$	$2$	$24$	$12, 00$	$12, 02$
$5$	$10$	$120$	$12, 00$	$12, 18$
$6$	$4$	$720$	$180, 00$	$179, 84$
$7$	$40$	$5040$	$126, 00$	$127, 08$
$8$	$92$	$40320$	$438, 26$	$437, 37$

Le coût n'est pas monotone en $n$ , et c'est instructif : $n = 6$ demande $180$ essais alors que $n = 7$ n'en demande que $126$ . La raison est que le problème n'a que quatre solutions à six reines contre quarante à sept. Le coût d'un Las Vegas ne dépend pas de la taille de l'instance mais de la densité des solutions dans l'espace où l'on tire.

3. Le retour sur trace, mesuré sur le même problème, explore $2057$ nœuds pour $n = 8$ et trouve les $92$ solutions ; $153$ nœuds pour $n = 6$ . Pour une solution il s'arrête bien plus tôt.

L'aléatoire n'est donc pas meilleur ici, et il faut le dire : sur les huit reines, le retour sur trace avec élagage est le bon algorithme. L'intérêt de la version Las Vegas est ailleurs, et le chapitre le nomme : elle sert quand on ne sait pas construire, seulement reconnaître. Ici on sait construire — le placement se fait colonne par colonne. Le problème « Fabriquer un nombre premier » traite le cas où l'on ne sait pas : la fabrication d'un nombre premier de taille cryptographique, où aucune construction directe n'existe.

Et le hasard reste supérieur sur un point : il n'a pas de pire cas exploitable. Un adversaire qui connaîtrait l'ordre de parcours du retour sur trace pourrait construire une entrée le mettant à genoux ; il ne peut rien contre des tirages qu'il ignore.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.