Aide pour le jeu de rotation de tuiles

Décisions

On vous donne une grille carrée avec des tuiles de base et il faut les tourner pour que les connecteurs sur les tuiles soient en face. La première modélisation qui nous vient à l’esprit alors est de coder dans des variables de décision les rotations des tuiles. Pour cela il nous pourrions représenter les rotations des tuiles par des entiers comme suit. 0 veut dire que la tuile de base reste comme elle est, 1 qu’elle subit une rotation à 90 degrés dans le sens normal, etc.

Exemple

Considérons la grille

13
13

Nous avons alors 4 variables de décision pour chacune des tuiles, que nous numérotons de x0 à x3, de gauche à droite, ligne par ligne. Quelles sont les contraintes sur ces tuiles ? Il y a d’abord des contraintes unaires imposées par le bord de la grille, visualisées en bleu dans la figure suivante. Par exemple le bord bleu marqué en rouge force x0 à être différent de 0, car le bord haut de la première cellule ne doit pas contenir de connecteur.

Puis il y a des contraintes binaires imposées par les bords de contact entre tuiles adjacentes, visualisées en orange dans la figure. Par exemple le bord orange marqué en rouge impose que soit \(x_0=3\) et $x_1\in\{0,1\}$ correspondant à la présence de connecteur sur ce bord commun soit $x_0\in\{0,1,2\}$ et $x_1\in\{2,3\}$ correspondant à l’absence de connecteur sur ce bord commun.

Finalement dans cet exemple toutes les contraintes n’autorisent qu’une seule solution, à savoir x0=3, x1=1, x2=3, x3=0, correspondant à la grille

Votre programme devrait alors afficher sur cet exemple

86
83

Contraintes binaires

Le domaine des contraintes binaires, peut se calculer de la manière suivante.

# toutes les tuiles possibles
T = range(16)

# les faces d'une tuile
TOP = 0
LEFT = 1
BOTTOM = 2
RIGHT = 3

# pour une tuile et une face donnée, y a-t-il un connecteur ?
def tile_side(tile, side):
    "presence of a connnector on a side of the tile"
    return (tile >> side) & 1

# couples de tuiles adjacents qui sont compatibles
left_match_right = {(a,b) for a in T for b in T if tile_side(a, RIGHT) == tile_side(b, LEFT)}
top_match_bottom = {(a,b) for a in T for b in T if tile_side(a, BOTTOM) == tile_side(b, TOP)}

# tuiles sans connecteur vers le bord
def border_tile(border):
    return {a for a in T if not tile_side(a, border)}