Jeu de rotation de tuiles

Cet exercice est inspiré de ce jeu.

Dans ce jeu on vous donne une grille. 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.

• la tuile sans connecteur
• la tuile avec un unique connecteur
• la tuile avec 2 connecteurs sur des faces successifs
• la tuile avec 2 connecteurs sur des faces opposés
• la tuile avec 3 connecteurs
• la tuile avec 4 connecteurs.

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. Ce codage en python donnera les instructions suivantes (pardon pour le franglais).

# toutes les tuiles possibles
T = range(16)

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

# formes possible d'une tuile pour les différentes rotations
rotation = { 0: [0],
             1: [1, 2, 4, 8],
             3: [3, 6, 12, 9],
             5: [5, 10],
             7: [7, 14, 13, 11],
             15:[15]}

def tile_side(tile, side):
    """test the presence of a connnector on a side of the tile"""
    return tile & (1 << side) > 0          

On vous donne la suivante grille en entrée.

33000000000
77373331131
11111333310

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.

Écrivez un programme python qui résout ce problème par programmation par contraintes.

Indices

On vous suggère de numéroter les variables dans l’ordre des lignes, et d’associer un numéro de variable à chaque case de la manière suivante.

# global variables

n=0  # rows
m=0  # columns


def cell(i, j):
    return i * m + j

Perdu ?

• aide (attention, spoiler)