Correction jeu rotation de tuiles

Modèle

Plusieurs modèles sont possible, en voici un.

Une variable par case. Une contrainte par couples de cases adjacentes.

Domaine d’une variable: toutes les formes qu’on peut obtenir par rotation et qui soient compatibles avec le bord.

Contrainte de compatibilité des faces adjacentes.

Variables

Les tuiles sont représentées par des entiers sur 4 bits. Des opérations de manipulation de bits permettent de détecter la présence d’un connecteur sur le bord. Dans un premier modèle, il y aura une variable par case, identifié les indices ligne et colonne.

def cell(i, j):
    return (i, j)

Le domaine de ces variables est donné par les rotations possible des tuiles.

    dom_cell = {cell(i, j): set(rotation[grid[i][j]]) for i in ROWS for j in COLS}

Contraintes unaires

D’abord il nous faut une fonction qui sélectionne des tuiles compatible avec un bord.

Nous pouvons restreindre le domaine des variables correspondant aux cases du bord. Notez l’utilisation de l’opérateur & qui fait l’intersection des ensembles.

    for j in COLS:
        dom_cell[ cell(0, j) ] &= border_tile(TOP)
    for i in ROWS:
        dom_cell[ cell(i, 0) ] &= border_tile(LEFT)
    for j in COLS:
        dom_cell[ cell(rows - 1, j) ] &= border_tile(BOTTOM)
    for i in ROWS:
        dom_cell[ cell(i, cols - 1) ] &= border_tile(RIGHT)

Contraintes binaires et affichage solution

Pour les contraintes binaires ont crée d’abord les couples de tuiles adjacentes compatibles, pour l’adjacence horizontale et puis pour l’adjacence verticale.

from itertools import product   # produit cartésien

    # ...

    # paires de rotations possibles par paires de cases adjacentes
    dom_hv = {}
    #  --- rotations possibles pour cases adjacentes horizontalement
    for i in ROWS:
        for j in range(cols - 1):
            Dx = dom_cell[ cell(i, j) ]
            Dy = dom_cell[ cell(i, j + 1) ]
            dom_hv[hpair(i, j)] = set(product(Dx, Dy)) & left_match_right
    #  --- rotations possibles pour cases adjacentes verticalement
    for i in range(rows - 1):
        for j in COLS:
            Dx = dom_cell[ cell(i, j) ]
            Dy = dom_cell[ cell(i + 1, j) ]
            dom_hv[vpair(i, j)] = set(product(Dx, Dy)) & top_match_bottom

On peut alors forcer les contraintes sur les cases adjacentes.

    P = constraint_program(dom_cell)
    #  --- tuiles adjacentes dans une même colonne
    for i in range(rows - 1):
        for j in COLS:
            P.add_constraint(cell(i, j), cell(i + 1, j), dom_hv[vpair(i, j)])
    #  --- tuiles adjacentes dans une même ligne
    for i in ROWS:
        for j in range(cols - 1):
            P.add_constraint(cell(i, j), cell(i, j + 1), dom_hv[hpair(i, j)])

L’affichage se fait de la manière suivante.

    sol = P.solve()
    for i in ROWS:                        # print solution
        for j in COLS:
            print(hex(sol[cell(i, j)])[-1], end='')
        print()

Résultat

L’exécution sur la grille donnée montre le résultat suivant. Notez que nous avons permit à notre programme de donner des arguments en ligne de commande, par exemple -p pour afficher une solution, ce qui est complètement optionel.

$ ./connect.py -s  < connect_sample.txt
c6000000000
d7ce6c644c2
11111939310
$ ./connect.py -s  < connect_sample.txt | ./connect.py -p
                                                       
  o----o    o    o    o    o    o    o    o    o    o  
  |    |                                               
  |    |                                               
  o----o    o----o----o    o----o    o    o    o----o  
  |    |    |    |    |    |    |    |    |    |       
  |    |    |    |    |    |    |    |    |    |       
  o    o    o    o    o    o----o    o----o    o    o  
                                                       

Le fichier Python complet est ici.

suite