Devoir maison 1

Mots croisés

Vous pouvez utiliser ces fichiers pour votre devoir.

0. Introduction

Un mot croisé consiste en une grille, dont certaines cases sont vides et certaines sont bloquées, ce qui est représenté respectivement par un point (.) et par un dièse (#.) Une séquence d’au moins deux cases vides consécutifs dans une même ligne ou même colonne est un segment si elle ne peut pas être étendue, donc si elle est encadré par des cases bloquées.

Le but du jeu est d’affecter des lettres à chacune des cases vides, afin que chaque segment soit un mot du dictionnaire. Le devoir consiste à écrire un programme qui résout cette tâche en se servant de la programmation par contraintes.

Exemple

Une instance au problème consiste en deux fichiers, décrivant un dictionnaire

to
at
tea
eat

et une grille.

#####
##.##
#...#
##.##
#####

Une solution possible est par exemple la grille suivante.

# # # # #
# # t # #
# t e a #
# # a # #
# # # # #

1. Spécification

Votre tache est d’écrire un programme python qui lit ces deux fichiers, dont les noms seraient spécifiés en argument de ligne de commande idéalement, puis construit un modèle de programmation par contraintes, appelle notre solveur, et affiche la solution produite dans le cas où la grille admet une solution.

2. Expérimentez

Plusieurs choix de posent à vous. Vous pouvez utiliser une résolution du programme par contraintes avec ou sans la maintenance de l’arc consistance. Déterminez expérimentalement quel choix donne de meilleurs performances. Pour les performances ne comptez pas le nombre de nœuds de l’arbre de recherche, mais le temps découlé, de préférence le temps utilisateur (comme affiché par la commande unix time).

Vérifiez expérimentalement lequel des deux choix est préférable.

3. Déposez

Déposez votre code et un document décrivant votre approche et les résultats des expériences. Déposez le tout dans fichier zip ici avant le 1 février 2017. Le 2 un corrigé sera communiqué pendant le cours. Je vous conseille de rendre le devoir maison le plus tôt possible pour ne pas tout faire à la dernière minute. J’estime le travail nécessaire à une soirée.