Previous  Up  Next

Module Resolution (.ml)

module Resolution: sig .. end
Projet Puzzle
Author(s): Lilian Besson <lilian.besson[AT]ens-cachan.fr>
val ex : unit -> unit
val d_d : string -> int
val print_signature : unit -> int

D'abord la définition de notre réprésentation formelle des objets étudiés
type couleur = int
Pour les couleurs : simplement les entiers, entre 1 et c.
type piece = {
   b : couleur;
   g : couleur;
   h : couleur;
   d : couleur;
}
Pour les pièces du puzzle : quatre emplacements mémoire pour les couleurs.
type plateau = {
   mutable c : int; (*nombre de couleurs,*)
   mutable n : int; (*nombre de colonnes,*)
   mutable m : int; (*nombre de lignes,*)
   mutable p : piece option array array; (*matrice des pièces placées sur le plateau. Si pij = None, on a tout simplement pas encore posé de pièce,*)
   mutable v : bool; (*un booléen qui informe de savoir si plateau est valide, ie : si l'agencement de pièce satisfait les conditions de compatibilités horizontale (compatible_h) et verticale (compatible_v).*)
}
Pour le plateau du puzzle, : on utilise un type option pour gérer simplement le cas ou on a pas encore posé la pièce sur le plateau (a voir).
type instance = {
   mutable ci : int; (*nombre de couleurs,*)
   mutable ni : int; (*nombre de colonnes,*)
   mutable mi : int; (*nombre de lignes,*)
   mutable pi : piece list; (*liste des pièces donnée à l'entrée.*)
}
Pour une instance du problème.

CONVENTION : sur les 'array array' Si a = Array.create_matrix 2 7 '.';; on conviend que a est une matrice, de type char array array, de taille : dimX = 2, dimY = 7, ie : avec 2 colonnes, et 7 lignes a.0 est un array de taille 7, qui est une COLONNE de la matrice, et | a.[0].[j] ; ..; a.[n-1].[j] | est la jieme LIGNE de la matrice,

Quelques exceptions
exception Erreur_option
Si on a cherché a se débarasser d'un élément de type 'a option valant "None".
exception Solution_trouvee
Notre procédure de recherche sera exhaustive, et donc possiblement peu efficace. On stoppe la recherche dès qu'on trouve une possibilité qui va bien.
exception Solution_trouvee_arg of plateau
exception Aucune_solution
Si on a aucune solution au puzzle.
exception Mauvais_tableau
Si lors de la lecture d'un plateau dans un fichier extérieure (ie : une solution possible, ou partielle), on découvre une erreur.
exception Erreur_compatibilite_h of (int * int)
Si une paire de pièce ne satisfait pas h, la relation de satisfaisabilité horizontale.
exception Erreur_compatibilite_v of (int * int)
Si une paire de pièce ne satisfait pas v, la relation de satisfaisabilité verticale.
exception Ecriture_refusee
Si l'utilisateur demande l'interruption d'une des fonctions d'écritures.

Note : j'utilise des arguments nommés (déclarés par des '~<arg>') afin de faciliter l'utilisation des fonctions dans les autres programmes. Ainsi, la signature de nombreuses fonctions ici définies contiendra des '~arg:<type>'. J'espère être plus clair et compréhensible par cet outil. Et parfois des arguments optionnels, déclarés par des '?(<arg>:<valeur_par_defaut>). Tant qu'on n'utilise que les valeurs de tels arguments optionnels, et pas leur type (pas de match..with notamment), l'utilisation est la même que pour les arguments optionnels

Fonctions outils, macros

Pour faciliter l'accès au dimension d'un matrice :
val dimX : 'a array array -> int
Dimension selon x.
val nombreColonne : 'a array array -> int
Calcule le nombre de colonne d'une matrice (array array).
val dimY : 'a array array -> int
Dimension selon y.
val nombreLigne : 'a array array -> int
Calcule le nombre de ligne d'une matrice (array array).
val in_list : 'a -> 'a list -> bool
Test l'appartenance d'un élément a une liste
val monsub : string -> int -> int -> string
Pour extraire une sous-string.
val ecrire_sortie : Pervasives.out_channel -> string -> unit
Pour faciliter la gestion des 'out_channel'.
val decoupe : ?e:char list -> string -> string list
Pour découper une chaine de caractères en morceau, en commancant un nouveau morceau pour chaque 'e' trouvé. Par défaut, si le parametre 'e' (pour 'effacé') n'est pas spécifié, il vaut ' ' le caractère espace.
val list_of_matrix : 'a array array -> 'a list
Converti une matrice en une liste, selon les conventions d'indiçages universelles.
val matrix_of_list : l:'a list -> m:int -> n:int -> 'a array array
Converti une liste en une matrice, selon les conventions d'indicages universelles, en supposant qu'on connaisse la taille de destination. A propos des arguments nommés : ils peuvent être indiqués dans un ordre quelconque lors de l'appel. Exemples : $> matrix_of_list ~n:4 ~m:1 ~l:0;1;2;3 est un appel valide $> matrix_of_list ~l:0;1 ~n:1 ~m:2 et celui-là aussi.
val kill_option : 'a option -> 'a
Pour se débarasser simplement du type option.
val read_int : unit -> int
Pour améliorer la lecture d'un entier au clavier. (Attention : on modifie une fonction standard de Ocaml).

Fonctions de vérifications : compatibilités, validités
val compatible_h : pieceG:piece -> pieceD:piece -> bool
Relation de compatibilité horizontale.

en effet, G.d : couleur de droite de G, D.g : couleur de gauche de D.
val compatible_v : pieceB:piece -> pieceH:piece -> bool
Relation de compatibilité horizontale.

pour ces deux fonctions, attention à l'ordre des arguments, ils ne sont pas commutatifs.
val nest_pas_faux : plateau -> bool
Pour vérifier qu'un plateau ne contredit pas les compatibilités.
val compatible : plateau -> unit
Pour vérifier qu'un plateau ne contredit pas les compatibilités.
val est_valide_plateau : plateau -> unit
Pour vérifier qu'un plateau est valide.

Fonctions de création d'instances aléatoires

On charge ici le module standard 'Random' de Ocaml, et on l'initialise.
val couleur_random : c:int -> unit -> couleur
Pour créer une couleur alétoire entre 1 et c.
val piece_random : c:int -> unit -> piece
Pour créer une pièce aléatoire du puzzle. Nécessite de préciser le nombre de couleurs , par exemple '~c:4'.
val creer_liste_random : gen:(unit -> 'a) -> int -> 'a list
Fonction outil générale, Pour créer une liste d'élément générés aléatoires, créés par l'argument '~gen:<..>'. La signature imposée a 'gen' est faite pour être compatible avec les deux fonctions précédentes 'couleur_random' et 'piece_random'.
val creer_instance_random : ?m:int -> ?n:int -> ?c:int -> unit -> instance
Pour créer une instance aléatoire du problème. Nécessite de préciser le nombre de couleurs, et la taille du plateau. Par exemple '~c:4 ~m:1 ~n:2' pour une instance similaire à celle donnée dans l'énoncé.

Un exemple d'instance.

Fonctions de lectures et écritures dans un fichier
val demande_confirmation : string -> unit
val ecriture_instance : ?action_confirmation:(string -> unit) ->
       i:instance -> file:string -> unit
Pour écrire une instance.
val print_piece : piece -> unit
Pour n'afficher qu'une piece.

Exemple de la représentation par le type 'instance' de l'exemple présenta dans l'énoncé.
val test_ecriture : unit -> unit
On peut aussi afficher à l'écran, en utilisant le nom de fichier spécial 'stdout' (sortie écran)
val print_instance : instance -> unit
Raccourcis pour afficher une instance à l'écran directement (et pas dans un fichier extérieur). On affiche simplement sous la même forme que sous laquelle on écrit. Les fonctions d'affichage dans des fenètres, avec de la couleur, sont disponibles dans le module "interface".
exception Error_Parse_instance
val piece_of_listcouleur : couleur list -> piece
Convertit une liste de couleurs d; h; g; b en une piece équivalente.
val lecture_instance : file:string -> instance
Pour lire une instance écrite dans le fichier 'file'.

Testons la lecture de l'instance test qu'on a écrite plus haut :

Les memes fonctions de lecture et écriture, mais pour des plateaux
val kill_option2 : piece option -> piece
Pour se débarasser simplement du type option, mais en affichant quand meme si on tombe sur un None.
val instance_of_plateau : plateau -> instance
Jusque là, on lit et écrit des instances, pas des solutions (type plateau)
val plateau_of_instance : instance -> plateau
LA FONCTION SUIVANTE N'EST PAS LA FONCTION DE RESOLUTION. Il s'agit de la conversion naive.
val ecriture_plateau : p:plateau ->
       ?action_confirmation:(string -> unit) -> file:string -> unit
Pour ecrire une solution (de type 'plateau') dans un fichier externe. ~p correspond au plateau, ~file a l'emplacement du fichier de destination.
val print_plateau : plateau -> unit
Pour afficher une solution. On affiche simplement sous la même forme que sous laquelle on écrit. Les fonctions d'affichage dans des fenètres, avec de la couleur, sont disponibles dans le module "interface".
val lecture_plateau : file:string -> plateau
Pour lire une solution depuis un fichier externe. Il faut que l'instance enregistrée dans ce fichier soit une solution correcte, sinon le plateau produit ne sera pas valide.

Un test.
val test_complet : m:int -> n:int -> c:int -> unit
Une fonction de test de toutes les fonctions précédentes : génération aléatoire, lecture, écriture, conversion naïve plateau - instance, affichage dans le terminal. Si une des lignes ne termine pas par 'check !', une erreur s'est produite.

Résolution

On propose d'abord un genre d'interface qui propose trois niveaux de verbosité pendant la résolution. Que la résolution soit utilisée pour afficher une solution, en mode graphique avec des couleurs (via 'interface.ml'), ou en mode textuel pour sauvegarder le résultat, il est possible d'afficher des informations pendant la résolution. On distingue deux types d'informations :- les plateaux courant, Plus précisément, on propose 5 modes : 
type verbosity =
| Muet
| Verbeux_textuel
| Bavard_textuel
| Verbeux_graphique
| Bavard_graphique
Type utilisé pour différencier les modes.
val myprint : verbosity -> string -> unit
Pour afficher les informations textuelles.

De plus, on propose en fait a nos fonctions de prendre un argument optionnel qui est la méthode utilisée pour afficher un plateau. Elle peut donc etre 'print_plateau' définit ici, qui affiche la plateau à l'écran, tel qu'il est affiché dans un fichier externe; et dans la partie graphique cette méthode (ie : fonction : plateau -> unit;) pourra etre 'afficher_plateau'. L'argument optionnel s'appele '~printP'
val myverb : verbosity

On donne ici les premières fonctions de résolution du puzzle.

On supposera toujours que les pièces manipulées sont construites avec le bon nombre de couleurs, cohérent avec le champ d'enregistrement 'c' du plateau manipulé. Je précise quand j'y pense les autres points que l'on suppose avoir dans chaque fonction.
val creer_plateau_vide : printP:(plateau -> 'a) ->
       instance -> plateau
Pour créer le plateau vide avec lequel on commence à travailler.
exception Case_deja_occupee
Si on tente de rajouter une pièce sur une case qui n'est pas vide (ie qui ne contient pas un élément de type piece option, réduit à "None").
val compatible_h_option : piece option -> piece option -> bool
Relation de compatibilité horizontale adaptée avec le type option.
val compatible_v_option : piece option -> piece option -> bool
Relation de compatibilité horizontale adaptée avec le type option.
val est_rajoutable : piece:piece -> i:int -> j:int -> pl:plateau -> bool
Pour savoir si la piece '~pi' est rajoutable en case ('~i', '~j') du plateau courant '~pl'.
val suppri_liste : 'a -> 'a list -> 'a list
Pour supprimer un élément d'une liste.
val indices_suivants : i:int -> j:int -> n:int -> m:int -> int * int
Pour trouver l'indice (i,j) suivant dans notre numérotation courante.
val argument_suivant : printP:(plateau -> unit) ->
       liste_piece:piece list ->
       plateau:plateau ->
       icourant:int ->
       jcourant:int ->
       piece_choisie:piece ->
       piece list * plateau * int * int
Fonction macro pour simplifier la rédaction de la première fonction de résolution.
val resoud_naivement_aux : printP:(plateau -> unit) ->
       liste_piece:piece list ->
       plateau:plateau ->
       icourant:int -> jcourant:int -> plateau list
La fonction récursive naïve de résolution.
val resoud_naivement : ?printP:(plateau -> unit) ->
       instance -> plateau
Et enfin la fonction de résolution naive. A adapter après avec l'interface graphique. Pour le moment, on affiche dans la console la solution trouvée (la première de la liste des solutions). Et j'ai interfacé cette fonction avec une procédure plus générale, l'argument 'printP' correspond à la méthode choisie pour afficher le plateau (cela peut etre à l'écran dans la partie graphique avec des couleurs, ou dans la console ici.).
val instance1 : instance
Premier essai : une seule piece !
val instance2 : instance
Second essai : deux pieces !
val instance3 : instance
Troisieme essai : deux pieces !
exception Interuption_clavier
Pour permettre de stopper le test suivant.
val test_resolution : unit -> unit
Quatrieme test : autant de fois que l'utilisateurs le veut, avec les paramètres qu'il rentre.

On lance un test si on est dans le toplevel.
val lecture_et_resolution : string -> unit
val tioi : string
val ps : string -> unit

Pour générer une instance aléatoire qui admet une solution. On va en fait générer une solution, puis on la mélangera !
val suppri_liste_indice : int -> 'a list -> 'a list
Supprime une case d'une liste.
val auxi_melange_liste : lnm:'a list -> lm:'a list -> 'a list
Auxilliaire à la suivante.
val melange_liste : 'a list -> 'a list
Pour mélanger une liste.
val melanger_matrix_to_list : 'a array array -> unit -> 'a list
Comme son nom l'indique, pour transformer une matrice en liste, en mélangeant aléatoirement.
val actualise_couleur : couleur Pervasives.ref ->
       string -> piece option -> unit
Pour actualiser une couleur courante en fonction de la pièce considérée.
val generer_plateau_solution : n:int -> m:int -> c:int -> unit -> plateau
Pour générer un plateau aléatoire qui soit déjà solution (chaque pièce est bien placée).
val generer_instance_solution : n:int -> m:int -> c:int -> unit -> instance
Pour générer une instance aléatoire qui admette une solution.