module Sig_resolution: sig .. end
Projet Puzzle
Author(s): Lilian Besson <lilian.besson[AT]ens-cachan.fr>
type int
Représente une couleur entre 1 et c.
type
}
Réprésente une pièce. 4 positions contenant toutes une couleur.
type
|
mutable c : int; |
|
mutable n : int; |
|
mutable m : int; |
|
mutable p : piece option array array; |
|
mutable v : bool; |
}
Une solution du problème sera de ce type là. Chaque case contient une pièce, ou un indicateur disant qu'on peut encore en mettre une.
type
|
mutable ci : int; |
|
mutable ni : int; |
|
mutable mi : int; |
|
mutable pi : piece list; |
}
Une instance du problème est un ensemble de pièces, qu'il faut placer sur un plateau, et trois entiers c, n, m.
exception Erreur_option
Si pendant la résolution on tente de replacer une pièce là ou en avait déja fixé une.
exception Solution_trouvee
Dès qu'on a un plateau satisfaisant pendant la recherche (exhaustive), cette exception est renvoyée.
exception Solution_trouvee_arg of plateau
Idem, mais en donnant le dit-plateau en plus.
exception Aucune_solution
Si la recherche exhaustive n'aboutit pas.
exception Mauvais_tableau
Si on a construit par erreur un mauvais tableau. Normalement, n'arrive jamais.
exception Erreur_compatibilite_h of (int * int)
Pendant la vérification de la validité d'un plateau, signale une erreur entre deux pièces, horizontalement, entre la case (i,j) et (i+1,j).
exception Erreur_compatibilite_v of (int * int)
Pendant la vérification de la validité d'un plateau, signale une erreur entre deux pièces, verticalement, entre la case (i,j) et (i,j+1).
exception Ecriture_refusee
Si lors de l'écriture dans un fichier externe, l'utilisateur refuse de l'écraser.
val compatible_h : pieceG:piece -> pieceD:piece -> bool
Relation de compatibilité horizontale.
val compatible_v : pieceB:piece -> pieceH:piece -> bool
Relation de compatibilité verticale.
val est_valide_plateau : plateau -> unit
Test de validité d'un plateau. Une exception parmi celle décrite plus haut est toujours renvoyée.
val couleur_random : c:int -> unit -> couleur
Pour générer une couleur entre 1 et c aléatoirement.
val piece_random : c:int -> unit -> piece
Pour générer une pièce colorée par des couleurs entre 1 et c aléatoirement.
val creer_instance_random : ?m:int -> ?n:int -> ?c:int -> unit -> instance
Pour générer une instance du problème aléatoirement.
val ecriture_instance : ?action_confirmation:(string -> unit) ->
i:instance -> file:string -> unit
Pour écrire une instance 'i' dans un fichier externe 'file', contenant une adresse relative OU absolue. 'action_confirmation' est l'action faite si le fichier destination existe déja. Selon les cas, il peut s'agir d'une demande de confirmation d'écrasement, textuel si on est en console, ou graphique si on est en mode graphique.
val print_piece : piece -> unit
Pour écrire une pièce en mode textuel (selon le format décrit en annexe).
val print_instance : instance -> unit
Idem mais pour une instance.
exception Error_Parse_instance
Lors de la lecture d'une instance déja écrite dans un fichier, si le contenu du dit-fichier n'est pas valide avec la "syntaxe" du format, cette exception est levée.
val lecture_instance : file:string -> instance
Pour lire une instance contenue dans le fichier "file".
val instance_of_plateau : plateau -> instance
Cette fonction est la suivante ne sont pas des fonctions de résolutions, seulement de conversions naïves d'un type vers l'autre.
val plateau_of_instance : instance -> plateau
En particulier, celle-ci place seulement les pièces de l'instance sur le plateau, une par une, ligne par ligne. Aucune vérification n'est faite, il s'agit simplement d'une conversion de type, et non d'une résolution.
val ecriture_plateau : p:plateau ->
?action_confirmation:(string -> unit) -> file:string -> unit
Pour écrire un plateau "p" dans un fichier externe "file".
val print_plateau : plateau -> unit
Pour écrire un plateau en mode textuel (selon le format décrit en annexe).
val lecture_plateau : file:string -> plateau
Pour charger un plateau depuis le fichier externe "file".
val creer_plateau_vide : printP:(plateau -> 'a) ->
instance -> plateau
Pour créer un plateau vide à partir d'une instance. Un plateau vide signifie un plateau avec les bonnes dimensions, mais sans aucune pièces fixées.
val compatible_h_option : piece option -> piece option -> bool
De même que "compatible_h", mais est toujours vrai dès qu'on l'utilise avec des cases sans pièces déja fixées.
val compatible_v_option : piece option -> piece option -> bool
De même que "compatible_v", mais est toujours vrai dès qu'on l'utilise avec des cases sans pièces déja fixées.
val est_rajoutable : piece:piece ->
i:int -> j:int -> pl:plateau -> bool
Pour vérifier que la pièce "piece" est rajoutable en position "i" et "j" du plateau "pl".
val indices_suivants : i:int -> j:int -> n:int -> m:int -> int * int
Pendant la résolution naïve, on parcours les indices ligne par ligne, dans l'ordre des i croissants, puis des j croissants (selon la convention d'indicages universelles pour les matrices, comme en C ou en Fortran par exemple). Cette fonction permet de savoir quel est le couple d'indices suivant.
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 interne à la procédure de résolution.
val resoud_naivement_aux : printP:(plateau -> unit) ->
liste_piece:piece list ->
plateau:plateau ->
icourant:int -> jcourant:int -> plateau list
Pour résoudre naïvement le plateau "plateau", en commençant aux indices "icourant" et "jcourant", avec un ensemble de pièces à placer "liste_piece", et une méthode pour afficher les plateaux courant "printP".
Note : ne vérifie pas les bonnes concordances des tailles de tous les éléments mis en jeu.
Note : peut renvoyer une liste de candidats, et pas un toujours seul candidat unique.
val resoud_naivement : ?printP:(plateau -> unit) ->
instance -> plateau
Pour résoudre naïvement une instance, avec une méthode pour afficher les plateaux courant "printP". Cette fois, la première solution valide trouvée est renvoyée.
exception Interuption_clavier
Pendant le test suivant, une interuption du test lève cette exception.
val test_resolution : unit -> unit
Un test intéractif EN TOPLEVEL uniquement.
val lecture_et_resolution : string -> unit
Condense les étapes de lecture dans un fichier externe, et de résolution, en une seule étape.
