N-reines

On considère un échiquier carré de taille n×n (par exemple 4×4) sur lequel on souhaite placer des reines.

• L'objectif est de placer n reines sur l'échiquier de façon à ce qu'aucune d'entre elles ne puisse en attaquer une autre.
• Deux reines s'attaquent si elles sont situées sur la même ligne, la même colonne, ou la même diagonale.
• En OCaml, on représente la position des reines sur l'échiquier par une liste de coordonnées (int * int) list, où chaque tuple (ligne, colonne) indique l'emplacement d'une reine. La ligne supérieure correspond à l'indice 0.

Le but est d'écrire une fonction qui renvoie toutes les configurations possibles pour placer n reines en toute sécurité sur l'échiquier.

1. 1

   Indice

   Comparer les coordonnées des lignes et des colonnes, puis détecter les lignes ou colonnes identiques. Les diagonales se compare en prenant le différence des coordonnées en valeur absolue.
   Écrire une fonction attacks : int * int -> int * int -> bool qui renvoie true si deux reines s'attaquent et false sinon. Par exemple attacks (0, 0) (0, 1) renvoie true.
2. 2

   Indice

   Appliquer la fonction attacks à chaque élément de la liste à l'aide de List.exists pour vérifier la sécurité.
   Écrire une fonction is_safe : (int * int) list -> int * int -> bool qui renvoie true si une case est sûre par rapport à une liste de reines déjà placées. Par exemple is_safe [(1, 1)] (0, 0) renvoie false.
3. 3

   Indice

   Vérifier la taille de la liste puis utiliser une récursion pour garantir la sécurité mutuelle et les limites du plateau.
   Écrire une fonction validate_solution : int -> (int * int) list -> bool qui renvoie true si une liste de reines constitue une solution valide sur un plateau de taille n x n. Par exemple validate_solution 4 [(0, 0); (1, 2); (2, 0); (3, 2)] renvoie false.
4. 4

   Indice

   Implémenter une récursion par backtracking sur les lignes et les colonnes pour accumuler progressivement toutes les solutions.
   Écrire une fonction solve_n_queens : int -> (int * int) list list qui renvoie toutes les solutions possibles du problème des N reines. Par exemple solve_n_queens 4 renvoie [[(0, 1); (1, 3); (2, 0); (3, 2)]; [(0, 2); (1, 0); (2, 3); (3, 1)]].