Programmation Avancée

TP5: autour du backtracking

Exercice 1: le problème des reines

Ce problème classique consiste à poser n reines sur un échiquier de taille n de façon à ce qu'aucune reine ne soit menacée par une autre: on doit donc avoir exactement une reine par ligne, une reine par colonne et une reine par diagonale montante ou descendante.

Il n'existe essentiellement pas de formule magique pour énumérer ou même compter les solutions, la seule solution est d'énumérer bêtement toutes les combinaisons possibles. Pas trop bêtement quand même: il est hors de question d'énumérer tous les échiquiers à n reines pour enlever ensuite ceux qui sont invalides. Plus généralement, on veut éviter de construire en mémoire la liste de toutes les solutions (partielles), ce qui permet par exemple de gagner du temps si on veut seulement afficher la première solution.

Question 1

Implémenter une solution sous la forme d'une fonction qui prend en argument la taille du problème et une fonction à appeler sur chaque solution trouvée. On évite ainsi de construire la liste de toutes les solutions, tout en restant abstrait par rapport à ce qu'on veut faire avec les solutions.

La fonction procèdera par construction progressive d'une solution, en posant des reines ligne par ligne sans avoir de conflit, et en "backtrackant" quand on se retrouve avec une ligne sans reine possible. Pour être efficace, on maintiendra en même temps que la solution en cours de construction l'ensemble des contraintes déja prises.

Question 2

Utiliser votre algorithme pour afficher la première solution et arrêter le calcul ensuite. Séparemment, l'utiliser pour compter le nombre de solutions. Vous pourrez comparer vos valeurs avec les résultats officiels.

Exercice 2: itérateurs persistants

On peut représenter une collection comme une fonction d'itération, par exemple List.iter ou la fonction d'énumération des solutions de l'exercice précédent. En utilisant des exceptions dans la fonction à itérer, on peut éviter de parcourir toute la collection. Par contre, on n'a aucun moyen de reprendre l'itération à partir d'une position arbitraire, ce qui est nécessaire si l'on veut faire des recherches avec backtracking. Pour ce faire, nous allons considérer un type d'itérateurs "de première classe". On considère la signature suivante:

module type ITER = sig
  type t
  type elt
  type init
  val init : init -> t
  val next : t -> (elt*t) option
end

La spécification est qu'on crée un itérateur à partir d'une donnée initiale (par exemple une liste, ou la taille du problème des reines à considérer) puis qu'on accède aux valeurs successives de l'itération via la fonction next, qui renvoie aussi une valeur de type t représentant la suite de l'itération. On demande que les itérateurs soient persistants dans le sens où itérateur doit pouvoir être réutilisé pour reprendre une énumération.

Question 1

Donner une implémentation de ITER qui énumère simplement les éléments d'une liste d'entiers, dans l'ordre.

Question 2

Coder une fonction qui prend en argument un itérateur sur elt = int et renvoie le nombre de sous-séquences dont la somme des éléments fasse 100. (On pourra supposer que tous les éléments rencontrés sont des entiers strictement positifs.)

Question 3

On se donne maintenant un type d'expressions arithmétiques:

type op = char * (int -> int -> int)
let plus = '+',(+)
let times = '*',( * )
let minus = '-',(-)
type expr =
  | I of int
  | Op of op * expr * expr
let rec eval = function
  | I i -> i
  | Op (o,a,b) -> (snd o) (eval a) (eval b)

Coder, d'abord de façon directe (en gros, comme cela vous plait) une fonction iter_subexpr : expr -> (expr -> unit) -> unit qui itère une fonction sur toutes les sous-expressions d'une expression donnée.

Question 4

Donner une implémentation de ITER correspondant à l'itération sur les sous-expressions. Adapter le code précédent pour chercher toutes les listes de sous-expressions d'une expression donnée, dont la somme des évaluations fasse 100.

Un peu de code utile pour tester; on doit trouver 6 solutions:

let t1 =
  Op (plus,
      Op (minus,
          Op (plus, Op (times, I 2, I 12), I 7),
          I 42),
      Op (plus, I 11, I 5))

let rec pp_expr ch = function
  | I i -> Format.fprintf ch "%d" i
  | Op (o,a,b) -> Format.fprintf ch "(%a%c%a)" pp_expr a (fst o) pp_expr b

let rec pp_list pp ch = function
  | [] -> ()
  | [a] -> pp ch a
  | a::b::more -> Format.printf "%a, %a" pp a (pp_list pp) (b::more)

let () = Format.printf "Exemple:\n %a\n" (pp_list pp_expr) [t1]
let () = assert (eval t1 = 5)

Pour la suite

On pourra se convaincre que faire la même chose avec des expressions qui se plongent dans l'expression initiale est nettement plus dur. Dans la suite du cours (et des TP) nous verrons comment faire cela de façon systématique.