TP 17 : Le problème des 5 reines (CS 2025) ou CCINP sujets zéros

Solution

(** Le champ `m` est une matrice représentant l'échiquier indiquant
   pour chaque case `(i, j)` le nombre de reines qui couvrent cette
   case. Le champ `z` sera utilisé plus tard. *)
type couverture = {m : int array array; mutable z : int}

let creer_couverture n = {m = Array.make_matrix n n 0; z = n * n}

let taille (c : couverture) = Array.length c.m

let modifie_case (c : couverture) (i : int) (j : int) (v : int) : unit =
  let avant = c.m.(i).(j) in
  let apres = avant + v in
  assert (apres >= 0);
  if avant = 0 && apres > 0 then c.z <- c.z - 1
  else if avant > 0 && apres = 0 then c.z <- c.z + 1;
  c.m.(i).(j) <- apres


(** Vérifie si une couverture est terminée, c'est-à-dire si toute case
   est couverte par au moins une reine. **)
let finale (c : couverture) : bool =
  c.z = 0


(** Mise à jour de la couverture `c` suite au placement/suppression
   d'une reine en position `(i, j)`. Si `v = 1` une nouvelle reine y
   est placée ; si `v = -1` la reine qui s'y trouve est enlevée *)
let mise_a_jour (c : couverture) (i : int) (j : int) (v : int) : unit =
  assert (c.m.(i).(j) = 0 && v = 1 || c.m.(i).(j) = 1 && v = -1);
  let n = taille c in
  for colonne = 0 to n - 1 do
    modifie_case c i colonne v
  done;
  for ligne = 0 to n - 1 do
    if ligne <> i then modifie_case c ligne j v
  done;
  let ligne = ref (i - 1) in
  let colonne = ref (j - 1) in
  while !ligne >= 0 && !colonne >= 0 do
    modifie_case c !ligne !colonne v;
    decr ligne;
    decr colonne
  done;
  let ligne = ref (i + 1) in
  let colonne = ref (j + 1) in
  while !ligne < n && !colonne < n do
    modifie_case c !ligne !colonne v;
    incr ligne;
    incr colonne
  done;
  let ligne = ref (i - 1) in
  let colonne = ref (j + 1) in
  while !ligne >= 0 && !colonne < n do
    modifie_case c !ligne !colonne v;
    decr ligne;
    incr colonne
  done;
  let ligne = ref (i + 1) in
  let colonne = ref (j - 1) in
  while !ligne < n && !colonne >= 0 do
    modifie_case c !ligne !colonne v;
    incr ligne;
    decr colonne
  done

(** Calcul du nombre minimal de reines sans prises nécessaires pour
   couvrir un échiquier $n \times n$. *)
let couverture_par_reines n =
  (* Nombre minimal de reines trouvées jusqu'ici *)
  let r_min = ref n in
  (* La couverture est une variable globale, dont les champs sont
     mutables, pour la fonction auxiliaire qui recherche la solution.
     Elle doit être à jour en tout temps. *)
  let c = creer_couverture n in
  (* Placement des reines à partir de la ligne `i` incluse, sachant
     que l'on a déjà placé `r` reines et que la couverture `c` est
     dans un état cohérent avec les placements effectués. *)
  let rec place i r =
    if r >= !r_min then ()
    (* Si on a tout couvert on met à jour suivant ce que l'on a trouvé *)
    else if finale c then begin
      r_min := r
    end
    (* Sinon, et à condition d'avoir encore des lignes à considérer *)
    else if i < n then begin
      (* On essaie sans reine sur cette ligne *)
      place (i + 1) r;
      (* On essaie tous les placements envisageables d'une reine sur cette ligne *)
      for j = 0 to n - 1 do
        if c.m.(i).(j) = 0 then begin
          (* On essaie avec une reine en position `(i, j)` *)
          mise_a_jour c i j 1;
          place (i + 1) (r + 1);
          (* Retour à l'état précédent pour tester la suite *)
          mise_a_jour c i j (-1)
        end
      done
    end
  in
  place 0 0;
  !r_min

let couverture_par_reines_positions n =
  let r_min = ref n in
  let meilleure_solution = ref [] in
  let c = creer_couverture n in
  let rec place i r positions =
    if r >= !r_min then ()
    else if finale c then begin
      r_min := r;
      meilleure_solution := List.rev positions
    end
    else if i < n then begin
      place (i + 1) r positions;
      for j = 0 to n - 1 do
        if c.m.(i).(j) = 0 then begin
          mise_a_jour c i j 1;
          place (i + 1) (r + 1) ((i, j) :: positions);
          mise_a_jour c i j (-1)
        end
      done
    end
  in
  place 0 0 [];
  (!r_min, !meilleure_solution)

let couverture_par_reines_nombre_solutions n =
  let r_min = ref n in
  let nb_solutions = ref 0 in
  let c = creer_couverture n in
  let rec place i r =
    if r > !r_min then ()
    else if finale c then begin
      if r < !r_min then begin
        r_min := r;
        nb_solutions := 1
      end
      else incr nb_solutions
    end
    else if i < n then begin
      place (i + 1) r;
      for j = 0 to n - 1 do
        if c.m.(i).(j) = 0 then begin
          mise_a_jour c i j 1;
          place (i + 1) (r + 1);
          mise_a_jour c i j (-1)
        end
      done
    end
  in
  place 0 0;
  (!r_min, !nb_solutions)

(** Affichage d'un échiquier `n` x `n` avec des reines placéees aux
    cordonnées de la liste `pos` *)
let affiche_reines n pos =
  let m = Array.make_matrix n n '.' in
  List.iter (fun (i, j) -> m.(i).(j) <- 'x') pos;
  print_newline ();
  for i = 0 to n - 1 do
    for j = 0 to n - 1 do
      print_char m.(i).(j);
      if j <> n - 1 then print_char ' '
    done;
    print_newline ();
  done;
  print_newline ()

(** Choix aléatoire uniforme d'un indice dans un tableau `a` parmi les
    indices donnant une valeur nulle pour `a`. La valeur `-1` est
    renvoyée si aucune valeur du tableau `a` n'est nulle. *)
let choix_position (a : int array) : int =
  let resultat = ref (-1) in
  let nb_zeros = ref 0 in
  Array.iteri
    (fun i valeur ->
      if valeur = 0 then begin
        incr nb_zeros;
        if Random.int !nb_zeros = 0 then resultat := i
      end)
    a;
  !resultat

(** Borne supérieure du nombre minimal de reines sans prises
    nécessaires pour couvrir un échiquier $n \times n$ en effectuant
    `nb_essais` d'une couverture aléatoire. *)
let couverture_par_reines_aleatoire n nb_essais =
  Random.self_init ();
  let meilleur = ref n in
  for _ = 1 to nb_essais do
    let c = creer_couverture n in
    let nb_reines = ref 0 in
    let abandon = ref false in
    for i = 0 to n - 1 do
      if not !abandon then begin
        if !nb_reines >= !meilleur then abandon := true
        else if Random.int n < n - 1 then begin
          let j = choix_position c.m.(i) in
          if j <> -1 then begin
            mise_a_jour c i j 1;
            incr nb_reines
          end
        end
      end
    done;
    if not !abandon && finale c && !nb_reines < !meilleur then
      meilleur := !nb_reines
  done;
  !meilleur

Dans ce TP, on étudie une recherche exhaustive avec élagage, puis une heuristique aléatoire, pour minimiser le nombre de reines sans prises couvrant un échiquier.

Pour lancer les tests automatiquement :

cd docs/tp/17_tp_reines
ocaml test_reines.ml

Centrale :

• Énoncé.
• Fichier OCaml.
• Script de tests.

CCINP Sujets zéros :

• Énoncé (Sujets B)
• Fichiers compagnons

Premières questions

1. Donner une solution avec une reine pour $n = 3$ et avec trois reines pour $n = 4$.

Correction

Pour $n = 3$, la reine au centre couvre tout l'échiquier.

Pour $n = 4$, une solution à trois reines est donnée par les positions

(1, 1), (2, 3), (3, 0)

soit

. . . .
. x . .
. . . x
x . . .

2. Montrer que le problème admet toujours une solution optimale et majorer simplement sa valeur.

Correction

Pour $n \ge 4$, on sait qu'il existe un placement de $n$ reines sans prises. Comme chaque ligne contient alors une reine, toute case est couverte par la reine de sa ligne. On obtient donc une solution de taille $n$.

Pour $n \in \{1,2,3\}$, on vérifie directement qu'une solution existe. Comme l'ensemble des placements possibles est fini, une solution optimale existe toujours.

On a donc simplement

$$1 \le r_n \le n.$$

3. Proposer un minorant de la valeur optimale.

Correction

Une reine couvre au plus sa ligne, sa colonne et ses deux diagonales, soit au plus $4n - 3$ cases distinctes. Si $r_n$ désigne le nombre minimal de reines, il faut donc au moins couvrir $n^2$ cases avec $r_n$ reines, d'où

$$r_n \ge \left\lceil \frac{n^2}{4n - 3} \right\rceil.$$

Ce minorant est simple mais déjà utile pour cadrer l'ordre de grandeur.

Recherche exhaustive

4. Implémenter finale : couverture -> bool.

Correction

Dans la version finale du fichier, on maintient l'invariant z = nombre de cases non couvertes. On peut donc tester la complétude en temps constant.

let finale (c : couverture) : bool =
	c.z = 0

5. Implémenter mise_a_jour.

Correction

On incrémente ou décrémente toutes les cases de la ligne, de la colonne et des deux diagonales de la reine. La fonction auxiliaire modifie_case maintient aussi z quand une case passe de 0 à une valeur positive, ou réciproquement.

let modifie_case (c : couverture) (i : int) (j : int) (v : int) : unit =
	let avant = c.m.(i).(j) in
	let apres = avant + v in
	assert (apres >= 0);
	if avant = 0 && apres > 0 then c.z <- c.z - 1
	else if avant > 0 && apres = 0 then c.z <- c.z + 1;
	c.m.(i).(j) <- apres

let mise_a_jour (c : couverture) (i : int) (j : int) (v : int) : unit =
	assert (c.m.(i).(j) = 0 && v = 1 || c.m.(i).(j) = 1 && v = -1);
	let n = Array.length c.m in
	for colonne = 0 to n - 1 do
		modifie_case c i colonne v
	done;
	for ligne = 0 to n - 1 do
		if ligne <> i then modifie_case c ligne j v
	done;
	(* puis les quatre demi-diagonales *)
	...

L'idée clé est qu'une case contenant une reine vaut nécessairement 1, car le placement est sans prises.

6. Rappeler le principe du branch and bound.

Correction

On explore récursivement un arbre de décisions. À chaque nœud, on compare la meilleure solution déjà connue avec ce qu'il est encore possible d'obtenir dans la branche courante. Si cette branche ne peut plus battre le meilleur optimum courant, on l'élague immédiatement.

7. Décommenter couverture_par_reines et corriger ses erreurs.

Correction

Les principales corrections sont :

• utiliser des références pour r_min ;
• créer correctement la couverture initiale ;
• ajouter les do, then et ; manquants ;
• conserver l'invariant de cohérence de c après chaque retour récursif.

let couverture_par_reines n =
	let r_min = ref n in
	let c = creer_couverture n in
	let rec place i r =
		if r >= !r_min then ()
		else if finale c then r_min := r
		else if i < n then begin
			place (i + 1) r;
			for j = 0 to n - 1 do
				if c.m.(i).(j) = 0 then begin
					mise_a_jour c i j 1;
					place (i + 1) (r + 1);
					mise_a_jour c i j (-1)
				end
			done
		end
	in
	place 0 0;
	!r_min

8. Donner pour $n \in \{5,6,7,8,9\}$ le nombre minimal de reines.

Correction

Avec le programme, on obtient :

$n$	5	6	7	8	9
minimum	3	4	4	5	5

9. Proposer un élagage simple.

Correction

Le plus simple consiste à arrêter immédiatement l'exploration dès que l'on a déjà placé au moins autant de reines que la meilleure solution connue :

if r >= !r_min then ()

Cet élagage est très rentable car il coupe toutes les branches qui ne peuvent plus améliorer l'optimum courant.

10. Modifier la fonction pour renvoyer aussi une solution optimale.

Correction

Il suffit de mémoriser la liste courante des placements et de la copier quand on améliore l'optimum.

let couverture_par_reines_positions n =
	let r_min = ref n in
	let meilleure_solution = ref [] in
	let c = creer_couverture n in
	let rec place i r positions =
		if r >= !r_min then ()
		else if finale c then begin
			r_min := r;
			meilleure_solution := List.rev positions
		end
		else if i < n then begin
			place (i + 1) r positions;
			for j = 0 to n - 1 do
				if c.m.(i).(j) = 0 then begin
					mise_a_jour c i j 1;
					place (i + 1) (r + 1) ((i, j) :: positions);
					mise_a_jour c i j (-1)
				end
			done
		end
	in
	place 0 0 [];
	(!r_min, !meilleure_solution)

11. Afficher une solution optimale pour $n = 9$.

Correction

Une solution optimale trouvée par le programme est

(2, 2), (3, 6), (6, 1), (7, 5), (8, 0)

ce qui donne

. . . . . . . . .
. . . . . . . . .
. . x . . . . . .
. . . . . . x . .
. . . . . . . . .
. . . . . . . . .
. x . . . . . . .
. . . . . x . . .
x . . . . . . . .

12. Maintenir l'invariant z et obtenir finale en $O(1)$.

Correction

On initialise z à n * n. Ensuite, chaque appel à modifie_case met z à jour :

• z := z - 1 quand une case passe de 0 à une valeur positive ;
• z := z + 1 quand une case repasse de positive à 0.

On obtient alors finale c = (c.z = 0), donc en temps constant.

13. Compter le nombre de solutions optimales.

Correction

On garde un compteur séparé.

• quand on trouve une solution strictement meilleure, on remplace r_min et on remet le compteur à 1 ;
• quand on retrouve une solution de même taille optimale, on incrémente ce compteur.

let couverture_par_reines_nombre_solutions n =
	let r_min = ref n in
	let nb_solutions = ref 0 in
	let c = creer_couverture n in
	let rec place i r =
		if r > !r_min then ()
		else if finale c then begin
			if r < !r_min then begin
				r_min := r;
				nb_solutions := 1
			end
			else incr nb_solutions
		end
		else if i < n then begin
			place (i + 1) r;
			for j = 0 to n - 1 do
				if c.m.(i).(j) = 0 then begin
					mise_a_jour c i j 1;
					place (i + 1) (r + 1);
					mise_a_jour c i j (-1)
				end
			done
		end
	in
	place 0 0;
	(!r_min, !nb_solutions)

14. Donner, pour $n \in \llbracket 1, 10 \rrbracket$, le minimum et le nombre de solutions optimales.

Correction

La fonction précédente donne le tableau suivant.

$n$	1	2	3	4	5	6	7	8	9	10
minimum	1	1	1	3	3	4	4	5	5	5
nombre de solutions optimales	1	4	1	16	16	120	8	728	92	8

Approche probabiliste

15. Différence entre Monte-Carlo et Las Vegas.

Correction

Un algorithme de Monte-Carlo a un temps d'exécution borné, mais peut produire un résultat faux avec une certaine probabilité. Un algorithme de Las Vegas produit toujours un résultat correct, mais sa durée d'exécution est aléatoire.

16. Déterminer la probabilité p_i du procédé de tirage uniforme en une passe.

Correction

Il faut prendre

$$p_i = \frac{1}{i + 1}.$$

En effet, la probabilité qu'un élément déjà vu reste mémorisé après l'étape $i$ vaut

$$\left(\frac{1}{i}\right)\left(1 - \frac{1}{i + 1}\right) = \frac{1}{i + 1},$$

ce qui conserve l'uniformité par récurrence.

17. Adapter ce procédé à un prédicat P.

Correction

On ne compte que les éléments qui vérifient P. Si le $k$-ième élément admissible apparaît, on le retient avec probabilité $1/k$. C'est exactement le principe du reservoir sampling sur la sous-suite filtrée.

18. Implémenter choix_position.

Correction

let choix_position (a : int array) : int =
	let resultat = ref (-1) in
	let nb_zeros = ref 0 in
	Array.iteri
		(fun i valeur ->
			if valeur = 0 then begin
				incr nb_zeros;
				if Random.int !nb_zeros = 0 then resultat := i
			end)
		a;
	!resultat

Chaque indice nul est bien choisi avec la même probabilité, et le tableau n'est parcouru qu'une seule fois.

19. Implémenter couverture_par_reines_aleatoire.

Correction

On répète nb_essais tentatives indépendantes. À chaque ligne, avec probabilité $(n-1)/n$, on place éventuellement une reine sur une case encore nulle choisie uniformément.

let couverture_par_reines_aleatoire n nb_essais =
	Random.self_init ();
	let meilleur = ref n in
	for _ = 1 to nb_essais do
		let c = creer_couverture n in
		let nb_reines = ref 0 in
		let abandon = ref false in
		for i = 0 to n - 1 do
			if not !abandon then begin
				if !nb_reines >= !meilleur then abandon := true
				else if Random.int n < n - 1 then begin
					let j = choix_position c.m.(i) in
					if j <> -1 then begin
						mise_a_jour c i j 1;
						incr nb_reines
					end
				end
			end
		done;
		if not !abandon && finale c && !nb_reines < !meilleur then
			meilleur := !nb_reines
	done;
	!meilleur

20. Donner un majorant expérimental pour $n \in \{20,30,100\}$ avec $10^6$ essais.

Correction

Il n'y a pas ici de réponse unique : toute exécution correcte fournit un majorant valable. En pratique, il faut compiler en natif avec ocamlopt pour que $10^6$ essais soient réalistes, et les valeurs obtenues dépendent de la graine aléatoire.

21. Complexité de cette approche.

Correction

Un essai parcourt les $n$ lignes. À chaque ligne, le choix et la mise à jour coûtent au plus $O(n)$. On obtient donc une complexité totale en

$$O(nb\_essais \times n^2).$$

22. Proposer un autre choix de p.

Correction

Une heuristique naturelle consiste à adapter p à la marge encore disponible avant de dépasser la meilleure solution connue. Par exemple, à la ligne i, si l'on a déjà placé r reines et que le meilleur majorant vaut m, on peut prendre une probabilité croissante avec

$$\frac{m - r}{n - i}.$$

Cela pousse l'algorithme à poser davantage de reines quand il en manque encore beaucoup, et à devenir plus parcimonieux lorsqu'il approche du meilleur score courant.

23. Commenter les proportions d'échecs, d'élagages et d'améliorations.

Correction

En général :

• les échecs restent majoritaires ;
• les élagages deviennent de plus en plus fréquents dès qu'un bon majorant a été trouvé ;
• les améliorations deviennent rapidement rares.

C'est exactement le comportement attendu d'une heuristique aléatoire avec branch and bound.

Parallélisation

24. Proposer une version parallélisée.

Correction

Le plus simple est de répartir les essais aléatoires entre plusieurs fils, chacun effectuant un bloc d'essais indépendant, puis de protéger la meilleure valeur globale par un mutex.

let couverture_par_reines_aleatoire_parallel n nb_essais nb_threads =
	let meilleur = ref n in
	let verrou = Mutex.create () in
	let essais_par_thread = nb_essais / nb_threads in
	let travail () =
		let local = couverture_par_reines_aleatoire n essais_par_thread in
		Mutex.lock verrou;
		if local < !meilleur then meilleur := local;
		Mutex.unlock verrou
	in
	let fils = Array.init nb_threads (fun _ -> Thread.create travail ()) in
	Array.iter Thread.join fils;
	!meilleur

25. Ressources partagées.

Correction

Les ressources partagées sont surtout le meilleur majorant global, éventuellement un compteur de statistiques, et les affichages. L'état local d'une tentative doit rester privé à chaque fil. Le mutex protège les écritures concurrentes sur les ressources globales.

26. Illustrer le déroulement.

Correction

Des affichages utiles sont par exemple : début d'un lot d'essais par fil, découverte d'un nouveau meilleur majorant, et synthèse finale. Il faut en revanche éviter d'afficher à chaque tentative, sinon l'I/O domine rapidement le calcul.

Variante

27. Déterminer le minimum pour $n = 4$ sans imposer le placement sans prises.

Correction

On peut couvrir l'échiquier $4 \times 4$ avec deux reines, par exemple en $(0, 0)$ et $(2, 2)$. Une seule reine ne suffit pas sur $4 \times 4$, donc le minimum vaut 2.

28. Déterminer le minimum pour des valeurs de n aussi grandes que possible.

Correction

On adapte la recherche exacte en autorisant désormais toutes les positions, sans test de non-prise. Pour de petites tailles, on obtient par programme :

$n$	1	2	3	4	5	6	7	8
minimum sans contrainte de non-prise	1	1	1	2	3	3	4	5