Devoir maison 1 des années passées

Connect

Ce devoir maison est inspiré de ce jeu. Vous pouvez utiliser ce code pour votre devoir.

0. Introduction

Dans ce jeu on vous donne une grille composée de n fois n cases carrés. Chaque case est recouverte d’une tuile. Le but est d’appliquer des rotations aux tuiles afin de mettre des connecteurs en face les uns des autres.

Concrètement une tuile a 4 bords, et chacun de ces bords peut être vide ou contenir un connecteur. Il existe 6 tuiles de base.

En appliquant des rotations sur ces tuiles de base on peut obtenir d’autres tuiles pour arriver à la collection de 16 tuiles représentés ci-dessous.

Ces tuiles sont numérotés de la manière suivante. La présence ou l’absence d’un connecteur est représenté par le bit 1 ou le bit 0. Ainsi une tuile est décrite par 4 bits, qui forment un entier entre 0 et 15, en associant le poids \(2^0\) au bord du haut, le poids \(2^1\) au bord de gauche, le poids \(2^2\) au bord du bas et le poids \(2^3\) au bord de droite. Ces numéros sont indiqués en bleu et en hexadécimal sur l’illustration ci-haut.

On vous donne une grille carrée composée de n fois n tuiles de base, c’est-à-dire la grille de l’entrée ne contient que les chiffres 0, 1, 3, 5, 7 ou F. Votre but est d’appliquer des rotations sur certaines des tuiles afin que tout connecteur soit en face d’un autre connecteur. Donc les faces opposées de deux tuiles adjacentes (verticalement ou horizontalement) doivent soit tous les deux être vide soit tous les deux contenir un connecteur. Les faces du bord de la grille doivent être vide.

1. Programmez

Écrivez un programme python qui résout ce problème par programmation par contraintes. Votre programme une fois lancé avec l’argument “-s” en ligne de commande devrait lire de l’entrée standard une grille et afficher en sortie une solution. Puis une dernière ligne devrait contenir soit

# la solution est unique

soit

# la solution n'est pas unique

Par exemple sur l’entrée

11
11

votre programme devra afficher

82
82
# la solution n'est pas unique

ou

44
11
# la solution n'est pas unique

Autre exemple : sur l’entrée

13
13

votre programme devra afficher

86
83
# la solution est unique

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).

Puis vous pouvez modéliser le problème

  1. en introduisant des variables qui codent les orientation des tuiles,
  2. en introduisant des variables qui codent la présence de connecteurs sur le contact entre deux tuiles adjacentes,
  3. en introduisant toutes ces variables.

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 15 janvier 2017. Le 16 un corrigé sera communiqué. Je vous conseille de rendre le devoir maison déjà le 9 janvier pour ne pas tout faire à la dernière minute.

Aide