Sudoku

L'objectif de l'exercice est d'implémenter un résolveur de Sudoku par backtracking en OCaml, en représentant la grille comme une liste plate de 81 entiers.

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

1. 1

   Indice

   Parcourir la liste avec List.iteri en insérant un saut de ligne quand l'indice est multiple de 9 et en affichant un point à la place des zéros.

   Écrire une fonction show : int list -> unit qui affiche une grille de Sudoku (liste de 81 entiers) sous forme de tableau 9×9, en remplaçant chaque 0 par un point . et en insérant un saut de ligne toutes les 9 cases. Par exemple show telegram affiche la grille telegram sur 9 lignes de 9 cases.

2. 2

   Indice

   Filtrer la grille en testant si l'indice divisé par 9 correspond à la ligne cible et si l'élément égale le nombre recherché.

   Écrire une fonction in_row : int -> int -> int list -> bool qui calcule si le number apparaît déjà dans la même ligne que la position i (la ligne étant i / 9) de la grille board. Par exemple in_row 0 8 telegram renvoie true et in_row 1 1 telegram renvoie false.

3. 3

   Indice

   Filtrer la grille en testant si l'indice modulo 9 correspond à la colonne cible et si l'élément égale le nombre recherché.

   Écrire une fonction in_col : int -> int -> int list -> bool qui calcule si le number apparaît déjà dans la même colonne que la position i (la colonne étant i mod 9) de la grille board. Par exemple in_col 0 8 telegram renvoie true et in_col 1 1 telegram renvoie false.

4. 4

   Indice

   Calculer les bornes du bloc 3×3 par division entière par 3 puis filtrer les éléments dont l'indice tombe dans ces bornes de ligne et de colonne.

   Écrire une fonction in_block : int -> int -> int list -> bool qui calcule si le number apparaît déjà dans le même bloc 3×3 que la position i de la grille board. Le bloc est déterminé par la ligne (i / 9 / 3) * 3 et la colonne (i mod 9 / 3) * 3. Par exemple in_block 0 8 telegram renvoie true et in_block 1 1 telegram renvoie false.

5. 5

   Indice

   Combiner les trois fonctions précédentes par une double négation et un ET logique pour rejeter toute collision.

   Écrire une fonction is_valid_number : int -> int -> int list -> bool qui calcule si le number peut être placé à la position i de la grille board, c'est-à-dire s'il n'apparaît ni dans la ligne, ni dans la colonne, ni dans le bloc de i. Par exemple is_valid_number 8 0 telegram renvoie false et is_valid_number 1 1 telegram renvoie true.

6. 6

   Indice

   Récursiver sur l'indice de 0 à 81, sauter les cases non nulles, essayer les chiffres 1 à 9 via is_valid_number pour les zéros, et incrémenter un compteur mutable à l'atteinte de l'indice 81.

   Écrire une fonction sudoku : int list -> unit qui résout la grille de Sudoku board par backtracking : pour chaque case vide (valeur 0), on essaie les chiffres de 1 à 9 en vérifiant is_valid_number, et on imprime chaque solution trouvée au format Solution #k suivi de la grille résolue. Par exemple sudoku telegram affiche Solution #1 puis la grille complète. Pour le sudoku multiple on attend 28 solutions !