Il existe des casse-têtes qui traversent les siècles et fascinent autant les mathématiciens que les amateurs de jeux de réflexion. Le problème des N-reines en fait partie. Derrière sa simplicité apparente se cache un défi algorithmique redoutable, qui met à l’épreuve la logique, la patience et la créativité.
Le défi : placer sans prise
Le principe est simple à énoncer, mais redoutable à résoudre pour de grandes valeurs de N :
Placer N reines sur un échiquier de taille N×N de sorte qu’aucune reine ne puisse en attaquer une autre.
Rappelons-le : une reine attaque toutes les cases de sa ligne, de sa colonne, et de ses deux diagonales. Il faut donc veiller à ce qu’aucune ne partage la même ligne, la même colonne, ou la même diagonale qu’une autre.
Une approche intelligente : le backtracking
Pour relever ce défi, les informaticiens utilisent le backtracking (ou retour arrière), une méthode qui consiste à explorer toutes les possibilités, mais en revenant en arrière dès qu’une configuration mène à une impasse.
On place une reine sur la première ligne, puis on essaie d’en placer une sur la deuxième ligne, et ainsi de suite. Si l’on se retrouve bloqué, on revient en arrière pour essayer une autre position.
Astuce : une reine par ligne et par colonne
On remarque vite qu’il suffit de placer une seule reine par ligne et par colonne. On peut donc représenter une solution comme une permutation des colonnes, ce qui réduit considérablement le nombre de cas à tester.
Implémentation en OCaml
Voici une version simple du backtracking pour résoudre le problème des N-reines en OCaml :
let is_safe pos solution =
let rec aux i = function
| [] -> true
| col :: rest ->
if col = pos || abs (col - pos) = i then false
else aux (i + 1) rest
in aux 1 solution
let rec n_queens n solution =
if List.length solution = n then [List.rev solution]
else
let rec try_cols col acc =
if col > n then acc
else
if is_safe col solution then
let new_solutions = n_queens n (col :: solution) in
try_cols (col + 1) (new_solutions @ acc)
else
try_cols (col + 1) acc
in
try_cols 1 []
Signature du programme :
val n_queens : int -> int list -> int list list = <fun>
n_queens n []renvoie la liste de toutes les solutions pour un échiquier de taille n×n.- Chaque solution est une liste d’entiers représentant les colonnes où sont placées les reines pour chaque ligne.
Exemple d’utilisation
n_queens 4 [];;
: int list list = [[2; 4; 1; 3]; [3; 1; 4; 2]]
Ici, chaque liste représente une solution possible pour 4 reines sur un échiquier 4×4.
Visualiser une solution
Pour mieux comprendre, voici une fonction qui affiche joliment une solution :
let print_solution sol =
List.iter (fun col ->
for i = 1 to List.length sol do
if i = col then print_string "Q " else print_string ". "
done;
print_newline ()
) sol;
print_newline ()
Essayez par vous-même !
Vous pouvez tester ce code dans votre compilateur ou interpréteur OCaml (ocamlc, ocamlopt) ou en ligne sur :
https://try.ocamlpro.com/
Astuce : Essayez d’augmenter la taille de l’échiquier. Pour N=8, il existe 92 solutions différentes ! Le backtracking vous montrera toute la puissance de la programmation récursive et de la logique combinatoire.
Le problème des N-reines, c’est la beauté de la simplicité alliée à la profondeur de la logique. À vous de jouer !