4.2- TP - Retour sur trace

On applique la méthode du retour sur trace (voir le cours) à deux problèmes classiques : le placement de huit reines sur un échiquier, et la résolution d'un sudoku.

I. Le problème des huit reines

On veut placer 8 reines sur un échiquier de cases, de sorte qu'aucune reine n'en attaque une autre : pas deux reines sur la même ligne, la même colonne, ou la même diagonale.

Comme il y a exactement une reine par ligne, on représente un placement par un tableau sol de taille 8 : sol.(i) est la colonne de la reine de la ligne i. On place les reines ligne par ligne, en commençant par la ligne 0.

Question 1

Deux reines en et sont sur une même diagonale si et seulement si . Pourquoi ?

Les cases d'une diagonale "descendante" vérifient $é$ lignes revient à se déplacer de colonnes.

Question 2

Écrire une fonction compatible (sol : int array) (i : int) (c : int) : bool qui indique si une reine placée en ligne i, colonne c, est compatible avec les reines déjà placées dans les lignes 0 à i - 1.

OCaml

Loading editor...

Question 3

Écrire une fonction récursive placer (sol : int array) (i : int) : bool qui place des reines dans les lignes i à n - 1 (où n est la taille de sol), en respectant les reines déjà placées, et renvoie true si c'est possible. Pour la ligne i, on essaie chaque colonne compatible, et on appelle placer pour la ligne suivante ; si cet appel échoue, on essaie la colonne suivante.

OCaml

Loading editor...

On vous donne une fonction d'affichage :

OCaml

Loading editor...

let affiche (sol : int array) : unit =
  Array.iter (fun c ->
    print_endline (String.concat " " (List.init (Array.length sol) (fun j -> if j = c then "♛" else "·")))) sol;;

let sol = Array.make 8 0;;
if placer sol 0 then affiche sol;;

Question 4

Écrire une fonction compter (sol : int array) (i : int) : int qui compte le nombre de façons de compléter le placement à partir de la ligne i. Combien y a-t-il de solutions au problème des huit reines ? Comparer avec le nombre de façons de placer une reine par ligne, .

OCaml

Loading editor...

Question 5

Pour quelles valeurs de le problème des reines n'a-t-il pas de solution ?

OCaml

Loading editor...

II. Le sudoku

Une grille de sudoku est représentée par une matrice int array array de taille , où les cases vides contiennent 0. Il faut remplir les cases vides avec des chiffres de 1 à 9, de sorte que chaque ligne, chaque colonne, et chacun des neuf carrés de contienne une seule fois chaque chiffre.

OCaml

Loading editor...

let grille = [|
  [|5; 3; 0; 0; 7; 0; 0; 0; 0|];
  [|6; 0; 0; 1; 9; 5; 0; 0; 0|];
  [|0; 9; 8; 0; 0; 0; 0; 6; 0|];
  [|8; 0; 0; 0; 6; 0; 0; 0; 3|];
  [|4; 0; 0; 8; 0; 3; 0; 0; 1|];
  [|7; 0; 0; 0; 2; 0; 0; 0; 6|];
  [|0; 6; 0; 0; 0; 0; 2; 8; 0|];
  [|0; 0; 0; 4; 1; 9; 0; 0; 5|];
  [|0; 0; 0; 0; 8; 0; 0; 7; 9|]
|];;

let affiche_grille (g : int array array) : unit =
  Array.iter (fun ligne -> print_endline (String.concat " " (Array.to_list (Array.map string_of_int ligne)))) g;;

affiche_grille grille;;

Question 6

Écrire une fonction possible (g : int array array) (i : int) (j : int) (v : int) : bool qui indique si on peut écrire v dans la case (i, j) : v n'est pas déjà dans la ligne i, la colonne j, ni le carré qui contient la case.

Indication

Le coin en haut à gauche du carré qui contient la case est la case (avec des divisions entières).

OCaml

Loading editor...

Question 7

On numérote les cases de 0 à 80, ligne par ligne : la case numéro est en ligne et en colonne . Écrire une fonction récursive resoudre (g : int array array) (k : int) : bool qui remplit la grille à partir de la case numéro k, et renvoie true si c'est possible. Si la case est déjà remplie, on passe à la suivante ; sinon, on essaie chaque chiffre possible.

Attention : si aucun chiffre ne convient, il faut vider la case avant de revenir en arrière !

OCaml

Loading editor...

Question 8

Pourquoi faut-il vider la case lors du retour en arrière ? Que se passerait-il sinon ?

Si on laisse le dernier chiffre essayé dans la case, les appels suivants à possible (pour d'autres cases de la même ligne, colonne ou carré) le prendraient en compte, alors qu'il ne fait partie d'aucune solution : on éliminerait à tort des chiffres, et on pourrait conclure qu'une grille n'a pas de solution alors qu'elle en a une.

Entrez le code donné en cours pour accéder à la solution :

Code d'accès