Grilles : présentation et objectifs

  Une grille est un tableau carré de cases noires ou blanches, comme une grille de mots croisés. Les cases noires sont interdites et les cases blanches autorisées. Dans ce sujet d'introduction, on propose:
    • la modélisation d'une grille
    • une liste de problèmes à résoudre
    • des outils de visualisation
    • des outils de sauvegarde et importation
    • la création de quelques grilles particulières

I) Modélisation  

  Un grille est donc un tableau carré de cases noires ou blanches, comme une grille de mots croisés. Les cases noires sont interdites et les cases blanches autorisées.

  Etant donné un entier non nul n, une grille A de dimension n sera un tableau à n lignes et n colonnes de 0 ou 1.
  Les cases c = (i, j) telles que A[i][j] = 0 sont les cases noires (les cases interdites) et les cases (i, j) telles que A[i][j] = 1 sont les cases blanches (les cases autorisées).  
  Les cases d'une grille de dimension n sont des couples d'entiers de {0, 1, ..., n - 1}. En Python, un couple est un t-uple à deux éléments.  Avec par exemple:

A = [[1, 1, 0, 1, 1], [0, 0, 1, 0, 1], [1, 1, 0, 1, 1], [1, 0, 1, 1, 1], [1, 1, 1, 0, 1]]

A est une grille de dimension 5 comportant 7 cases noires. La case c = (3, 1) est noire et la case c = (3, 3) est blanche.  

II) Des problèmes à résoudre

1) Quelques définitions dans une grille

(1) Un chemin joignant deux cases blanches distinctes  A et B est une suite S = [S[0], S[1], ..., S[p-1]] de cases blanches distinctes telles que:
    (1a) S[0] = A et S[p-1] = B
    (1b) ∀ k ∈ {1,..., p-1}, les cases S[k-1] et S[k] sont adjacentes par l'un de leurs quatre côtés.

(2) Un pays P est est un ensemble de cases blanches vérifiant les deux propriétés suivantes:
    (2a) Il existe un chemin joignant deux cases quelconques de P
    (2b) Il n'existe aucun chemin joignant une case blanche hors de P à une case de P
Notons qu'avec cette définition une case blanche isolée est un pays.

2) Une liste non exhaustive de problèmes dans un grille

(1) Calculer, s'il existe, un plus court chemin joignant deux cases blanches
(2) Calculer tous les pays d'une grille

(3) Calculer le(s) plus grand(s) carré(s) de cases blanches
(4) Calculer le(s) plus grand(s) rectangle(s) de cases blanches

III) Visualisation d'une grille

  On veut visualiser une grille A par le damier noir et blanc dont les lignes sont, de haut en bas, les lignes de A.  Comme on veut également voir les rectangles calculés dans la résolution des problèmes (3) et (4) ou des ensembles de cases calculés dans les problèmes (1) et (2), on se dote des trois fonctions suivantes:
    • une fonction affiche_grille(A, titre = "", ajout = []) qui affiche le grille A et éventuellement un ajout, des rectangles ou disques de couleurs
    • une fonction affiche_rectangles_grille(A, titre = "", rects = [], colors = []) qui affiche la grille A et les rectangles coloriés rects[k] = [(a,b), xL, yL] modélisant le rectangle [a, b] × [a + xL, b + yL]
    • une fonction affiche_zones_grille(A, titre = "", zones = [], colors = []) qui affiche la grille A et les disques coloriés des zones[k] qui contiennent une liste de cases
  Chaque rectangle rects[k] et chaque zone zones[k] est colorié avec la couleur colors[k % len(colors)].

import pylab as plt
import numpy as np
from matplotlib.collections import PatchCollection
from  matplotlib.patches import Circle, Rectangle

def affiche_grille(A, titre = "", ajout = []):
    """ Affichage de la grille de base et éventuellement d'un ajout, des
    rectangles ou disques de couleurs éventuels"""
# Divers préparatifs
    n = len(A)
    plt.rcParams['figure.figsize'] = 9.4, 10
    plt.subplots_adjust(bottom = 0.02, top = 0.92, left = 0.02, right = 0.98 )
    graphe = plt.subplot(1, 1, 1)
    graphe.get_xaxis().set_visible(False)
    graphe.get_yaxis().set_visible(False)
    plt.axis([0, n, n, 0])
    plt.suptitle(titre, fontsize = 24)
# Carrés noirs dans les cases interdites
    CN = []
    for i in range(n):
        for j in range(n):
            if A[i][j] == 0:
                CN.append(Rectangle((j, i), 1, 1, color = "black"))
    if CN != []:
        graphe.add_collection(PatchCollection(CN, match_original = True))
# Ajout (rectangles ou disques de couleurs éventuels)
    if ajout != []:
        graphe.add_collection(PatchCollection(ajout, match_original = True))
# Tracés des lignes
    for k in range(n + 1):
        plt.plot([0, n], [k, k], color = "0.75")
        plt.plot([k, k], [0, n], color = "0.75")
# Enregistrement éventuel et affichage
##    plt.savefig("grille.jpg",dpi=200)
    plt .show()

def affiche_rectangles_grille(A, titre = "", rects = [], colors = ["green"]):
    """ Affichage de la grille et des rectangles coloriés
    rects[k] = [ptHG = (a,b), xL, yL)] pour le rectangle [a,b]x[a+xL, b+yL]"""
# Calcul des rectangles coloriés
    R = []
    nR, nC = len(rects), len(colors)
    for k in range(nR):
        col = colors[k % nC]
        [(a, b), xL, yL] = rects[k]
        R.append(Rectangle((b, a), yL, xL, color = col, fill = False, lw = 9))
# Affichage
    affiche_grille(A, titre, R)

def affiche_zones_grille(A, titre = "", zones = [], colors = ["green"]):
    """ Affichage de la grille et éventuellement des disques coloriés des
    zones[k] qui contiennent une liste de cases"""
# Calcul des disques coloriés
    nZ, nC, D = len(zones), len(colors), []
    for k in range(nZ):
        col = colors[k % nC]
        for (i, j) in zones[k]:
            D.append(Circle((j + 0.5, i + 0.5), 0.25, color = col))
# Affichage
    affiche_grille(A, titre, D)

Q1)

  Par exemple, tester le code ci-dessous:   grille_presentation_1.png grille_presentation_2.png  grille_presentation_3.png

A = [[1, 1, 0, 1, 1], [0, 0, 1, 0, 1], [1, 1, 0, 1, 1], [1, 0, 1, 1, 1], [1, 1, 1, 0, 1]]
zones = [[(0,3)], [(2,0)], [(0,4), (1,4), (2,4), (3,4), (3,3), (3,2), (4,2),
        (4,1), (4,0), (3,0)]]
rectangles = [[(0, 3), 1, 2], [(2,3), 2, 2], [(2, 0), 3, 1]]
col = ["blue", "green", "red"]
affiche_grille(A, "Grille nue")
affiche_zones_grille(A, "Plus court chemin", zones, col)
affiche_rectangles_grille(A, "Trois rectangles", rectangles, col)

IV) Sauvegardc et importation d'une grille

  Tout d'abord, il peut être utile de modifier le répertoire courant da travail:

import os                    # Module contenant des fonctions utiles

##print(os.getcwd())        # Affiche le répertoire courant de travail
# Pour Changer (s'il le faut) le répertoire courant de travail, on utilise os.chdir()
# Par exemple:
os.chdir("C:/Users/Eric/Documents/Algorithmique/Grille")

  Les deux fonctions suivantes permettent d'enregistrer ou de récupérere un objet Python dans un fichier nommé nom_fichier. On les utilise pour sauvegarder ou importer une grille.

import pickle

def enregistrer(objet, nom_fichier):
    """ Enregistre objet dans le fichier nommé nom_fichier"""
    with open(nom_fichier,"wb") as fich: # ouverture en écriture du fichier
       pickle.dump(objet, fich)          # objet est enregistré dans fichier

def lire(nom_fichier):
    """ objet stocké dans le fichier nommé nom_fichier"""
    with open(nom_fichier,"rb") as fich: # ouverture en lecture du fichier
       return pickle.load(fich)     # lecture de l'objet enregistré dans fichier

Q2) Les fichiers de données (du type grille_xy.gri) sont stockés dans http://www.maths-algo.fr/algo/explorateur.php?dir=exercices/Grilles . Après les avoir recopiés dans le répertoire courant de travail, vérifier par exemple que le code suivant:

A = lire("grille_10.gri")
affiche_grille(A, "grille_10")

affiche bien la grille ci-contre : grille_presentation_4.png

V) Fabrication de quelques grilles

Q3) Ecrire les fonctions qui retournent les grilles n×n suivantes:
    • blanc_grille(n) → blanc
    • diag_grille(n) → blanc avec la diagonale SW - NE noire
    • double_diag_grille(n) → blanc avec les deux diagonales noires
    • damier_grille(n) → alternance de cases noires et blanches avec une case noire en haut et à gauche
    • special_grille(n) →blanc avec alternance de cases noires et blanches sur la première ligne seulement avec une case noire en haut et à gauche    
    • aleatoire_grille(n, prop_cases_blanches) qui retourne un grille aléatoire n×n ayant une proportion prop_cases_blanches ∈ [0,1] de cases blanches.
Contrôler les résultats avec la fonction affiche_grille(). Par exemple:    

def diag_grille(n):
    """ grille avec la diagonale SW-NE noire"""
    A = [[1]*n for i in range(n)]
    for i in range(n):
        A[i][n - 1 - i] = 0
    return A

affiche_grille(diag_grille(10)) → grille_presentation_5.png

Pour la fonction aleatoire_grille(n, prop_cases_blanches), on pourra utiliser la fonction shuffle dans le module random

© 2015 - Eric Obermeyer      Powered by      Corrigé