Navigation : << App-15 SportsScheduling | Index | App-17 VRP >>
Ce notebook explore la generation de grilles de mots croises comme un Problème de Satisfaction de Contraintes (CSP). A la fin de ce notebook, vous saurez :
Les mots croises sont un cas d’ecole du CSP : un probleme NP-complet avec une structure binaire (chaque case est contrainte par au plus deux mots : horizontal et vertical), un domaine enorme (dictionnaire de mots francais) et un espace de recherche qui explose tres vite. La reduction de l’espace par propagation de contraintes est ce qui rend ces puzzles solvables en pratique – sans elle, un backtracking pur s’essouffle sur une grille 7x7 avec ~1.7×10³¹ combinaisons possibles.
| Section | Sujet | Solveur | Technique cle |
|---|---|---|---|
| 1 | Modelisation | – | Variables, domaines, contraintes |
| 2 | Visualisation | matplotlib | Affichage de la grille |
| 3 | Solveur industriel | OR-Tools CP-SAT | CP-SAT + propagation booleenne |
| 4 | Backtracking pur | Python pur | Recherche sans inference |
| 5 | Forward checking | Python pur | Propagation locale paresseuse |
| 5b | AC-3 | Python pur | Arc-coherence globale preventive |
| 6 | Generation aleatoire | Python pur | Densite de cases noires |
| 7 | Statistiques | Python pur | Metriques de performance |
arc-consistency, MRV heuristic, forward checking, constraint propagationortools (Google OR-Tools), matplotlib, numpy, dataclasses45 a 60 minutes de lecture interactive (execution incluse). Les sections 3, 5b et 8 sont les plus denses – prenez le temps de lire les interpretations apres chaque cellule code.
# Imports
from ortools.sat.python import cp_model
from dataclasses import dataclass
from typing import Dict, List, Tuple, Optional, Set
import random
import numpy as np
import matplotlib.pyplot as plt
from collections import defaultdict
print("Imports OK")Imports OK| Élément | Description |
|---|---|
| Cases | Blanches (lettres) ou noires (blocantes) |
| Slots | Sequences de cases blanches consecutives |
| Contraintes | Intersections des slots horizontaux/verticaux |
Dans le formalisme CSP, le problème se decompose en trois composantes :
i et un slot vertical j, une egalite entre la lettre a la position p_i du mot choisi pour i et la lettre a la position p_j du mot choisi pour jLes mots croises ont une particularite : les contraintes sont toutes binaires (entre exactement 2 variables) et ponctuelles (portent sur une seule lettre). Cela les distingue d’autres CSP comme le Sudoku (contraintes d’inegalite sur 9 cases) ou les N-Reines (une seule contrainte unaire par variable).
Cette structure binaire rend les algorithmes d’arc-coherence comme AC-3 particulierement efficaces : chaque arc porte une seule contrainte, et la verification est O(d²) avec d la taille du domaine.
Les mots croises modernes ont ete popularises dans les annees 1920 (Arthur Wynne, New York World). La formalisation comme CSP date des annees 1970 avec les travaux de Aho-Hopcroft-Ullman et de Knuth. Le solveur “instantane” sur grille 7x7 est devenu un benchmark pedagogique classique pour les algorithmes de satisfaction de contraintes, au meme titre que les N-Reines pour le backtracking.
Cette modelisation est directement transposable a :
Le dictionnaire utilise (mots francais simplifies de 2 a 10 lettres, ~200 mots au total) est volontairement petit pour permettre des experimentations rapides. Un vrai dictionnaire francais comporte ~50 000 mots : la combinatoire passerait de ~10³¹ a ~10^120 – le backtracking serait intractable meme avec propagation.
La cellule suivante visualise la structure d’une grille 7x7 generee aleatoirement avec une densite de cases noires de ~17% (12 cases noires sur 49).
# Dictionnaire francais simplifie (mots de 2 a 10 lettres)
# Chaque cle = longueur du mot. Tous les mots sont verifies.
DICTIONARY = {
2: ['DE', 'LE', 'LA', 'UN', 'ET', 'EN', 'OU', 'NE', 'CE', 'SE', 'IL', 'AU', 'DU', 'SA', 'MA'],
3: ['LES', 'DES', 'UNE', 'PAS', 'SUR', 'PAR', 'EUR', 'ELS', 'MER', 'TER', 'AIR', 'EAU', 'FEU', 'NUI', 'OUI', 'ROI', 'LOI', 'VOI', 'FIN', 'BON'],
4: ['DANS', 'SOUS', 'PRES', 'LOIN', 'TOUS', 'DEUX', 'VRAI', 'FAUX', 'BIEN', 'AIME', 'DONC', 'VOTE', 'LIRE', 'NOIR', 'BLAN', 'VERT', 'ROUG', 'BLEU', 'GRIS', 'JAUN'],
5: ['TOUTE', 'AUTRE', 'VOTRE', 'NOIRE', 'GRAND', 'PETIT', 'FORTS', 'MAJOR', 'SAINT', 'VALOR', 'NOBLE', 'HONTE', 'NUAGE', 'ROUTE', 'FEUVE', 'ORAGE', 'LIMBE', 'ARBRE', 'ECRAN', 'BLANC'],
6: ['MOMENT', 'SYSTEM', 'FOREST', 'FONDER', 'NATURE', 'ANIMAL', 'OBJECT', 'SOIREE', 'VOYAGE', 'ETOILE', 'PORTER', 'SAVANT', 'DANGER', 'REGLER', 'COUPER', 'PLIANT', 'JARDIN', 'FLEURS', 'LIVRES', 'COULEU'],
7: ['SYSTEME', 'PROJETS', 'DOMAINE', 'LEURREZ', 'FAUCHER', 'LIAISON', 'PAROLES', 'SENTIER', 'ETOILER', 'DAUPHIN', 'HISTOIR', 'SAVANTE', 'JALOUSI', 'CREUSER', 'NATUREL', 'POURSUI', 'BROUILL', 'SOUFFLE', 'RUISSEA', 'CHANTER'],
8: ['PROGRAMM', 'VARIABLE', 'FONCTION', 'PROBLEME', 'SOLUTION', 'NATURELS', 'GRANDISS', 'CREATIFS', 'COMPLETE', 'PAROISIE', 'DEFINISS', 'CARACTER', 'LONGUEUR', 'OPPOSANT', 'SAVANTES', 'ELEVATIO', 'MONTAGNE', 'INFORMAT', 'REPERTOI', 'STRUCTUR'],
9: ['ALGORITHM', 'VARIABLES', 'SOLUTIONS', 'SQUELETTE', 'NATURELLE', 'COMPLETER', 'HARMONIES', 'PAROISSIE', 'REPERTOIR', 'EVOLUTION', 'LANGAGIER', 'COMPLEXES', 'DIFFICILE', 'SECONDAIR'],
10: ['PROGRAMMAT', 'SQUELETTES', 'NATURELLES', 'COMPLETION', 'EVOLUTIONS', 'HARMONIQUE', 'PAROISSIAL', 'REPERTOIRE', 'STRUCTURAL', 'OPPOSANTES', 'LANGAGIERS', 'DETERMINER', 'SECONDAIRE', 'RESOLUTION']
}
@dataclass
class Slot:
"""Un slot (emplacement de mot) dans la grille."""
id: int
row: int
col: int
length: int
direction: str # 'H' ou 'V'
cells: List[Tuple[int, int]] # coordonnees des cases
@dataclass
class CrosswordGrid:
"""Grille de mots croises."""
rows: int
cols: int
black_cells: Set[Tuple[int, int]] # Cases noires
slots: List[Slot]
def __post_init__(self):
self.grid = np.full((self.rows, self.cols), None, dtype=object)
for r, c in self.black_cells:
self.grid[r, c] = '#'
def is_white(self, r: int, c: int) -> bool:
"""Verifie si une case est blanche."""
return (r, c) not in self.black_cells
def get_intersections(self) -> List[Tuple[int, int, Tuple[int, int]]]:
"""
Trouve les intersections entre slots.
Retourne: [(slot_h_id, slot_v_id, (pos_h, pos_v))]
"""
intersections = []
horizontal = [s for s in self.slots if s.direction == 'H']
vertical = [s for s in self.slots if s.direction == 'V']
for h_slot in horizontal:
for v_slot in vertical:
# Trouver l'intersection
h_cells = set(h_slot.cells)
v_cells = set(v_slot.cells)
common = h_cells & v_cells
if common:
cell = common.pop()
# Position dans chaque slot
pos_h = h_slot.cells.index(cell)
pos_v = v_slot.cells.index(cell)
intersections.append((h_slot.id, v_slot.id, (pos_h, pos_v)))
return intersections
def create_sample_grid() -> CrosswordGrid:
"""Cree une grille exemple 7x7."""
black_cells = {
(0, 3), (1, 3), (2, 3),
(3, 0), (3, 1), (3, 2), (3, 4), (3, 5), (3, 6),
(4, 3), (5, 3), (6, 3)
}
# Identification des slots
slots = [
# Horizontaux
Slot(0, 0, 0, 3, 'H', [(0, 0), (0, 1), (0, 2)]),
Slot(1, 0, 4, 3, 'H', [(0, 4), (0, 5), (0, 6)]),
Slot(2, 1, 0, 3, 'H', [(1, 0), (1, 1), (1, 2)]),
Slot(3, 1, 4, 3, 'H', [(1, 4), (1, 5), (1, 6)]),
Slot(4, 2, 0, 3, 'H', [(2, 0), (2, 1), (2, 2)]),
Slot(5, 2, 4, 3, 'H', [(2, 4), (2, 5), (2, 6)]),
# Bas
Slot(6, 4, 0, 3, 'H', [(4, 0), (4, 1), (4, 2)]),
Slot(7, 4, 4, 3, 'H', [(4, 4), (4, 5), (4, 6)]),
Slot(8, 5, 0, 3, 'H', [(5, 0), (5, 1), (5, 2)]),
Slot(9, 5, 4, 3, 'H', [(5, 4), (5, 5), (5, 6)]),
Slot(10, 6, 0, 3, 'H', [(6, 0), (6, 1), (6, 2)]),
Slot(11, 6, 4, 3, 'H', [(6, 4), (6, 5), (6, 6)]),
# Verticaux
Slot(12, 0, 0, 3, 'V', [(0, 0), (1, 0), (2, 0)]),
Slot(13, 0, 1, 3, 'V', [(0, 1), (1, 1), (2, 1)]),
Slot(14, 0, 2, 3, 'V', [(0, 2), (1, 2), (2, 2)]),
Slot(15, 0, 4, 3, 'V', [(0, 4), (1, 4), (2, 4)]),
Slot(16, 0, 5, 3, 'V', [(0, 5), (1, 5), (2, 5)]),
Slot(17, 0, 6, 3, 'V', [(0, 6), (1, 6), (2, 6)]),
# Droite
Slot(18, 4, 0, 3, 'V', [(4, 0), (5, 0), (6, 0)]),
Slot(19, 4, 1, 3, 'V', [(4, 1), (5, 1), (6, 1)]),
Slot(20, 4, 2, 3, 'V', [(4, 2), (5, 2), (6, 2)]),
Slot(21, 4, 4, 3, 'V', [(4, 4), (5, 4), (6, 4)]),
Slot(22, 4, 5, 3, 'V', [(4, 5), (5, 5), (6, 5)]),
Slot(23, 4, 6, 3, 'V', [(4, 6), (5, 6), (6, 6)]),
]
return CrosswordGrid(rows=7, cols=7, black_cells=black_cells, slots=slots)
grid = create_sample_grid()
print(f"Grille creee: {grid.rows}x{grid.cols}")
print(f"Cases noires: {len(grid.black_cells)}")
print(f"Slots: {len(grid.slots)}")
# Verification du dictionnaire : chaque mot doit avoir la bonne longueur
errors = 0
for length, words in DICTIONARY.items():
for w in words:
if len(w) != length:
print(f"ERREUR: '{w}' dans cle {length} mais longueur reelle = {len(w)}")
errors += 1
if errors == 0:
print("Dictionnaire OK: toutes les longueurs sont correctes.")
else:
print(f"Dictionnaire: {errors} erreur(s) detectee(s).")Grille creee: 7x7
Cases noires: 12
Slots: 24
Dictionnaire OK: toutes les longueurs sont correctes.Une grille de mots croises est traditionnellement affichee avec :
La fonction display_grid utilise plt.Rectangle pour dessiner chaque case individuellement. L’astuce consiste a inverser l’axe Y (avec grid.rows - r - 1) pour que la ligne 0 soit en haut, comme dans la convention des mots croises.
Le rendu utilise un FigureCanvasAgg non interactif (kernel headless) – on ne peut pas zoomer ou survoler les cases. Pour un notebook interactif, on utiliserait plutot ipywidgets ou un affichage HTML avec une <table>.
La cellule code suivante affiche la grille avec : - 7 lignes x 7 colonnes - Cases noires en blocs noirs - Cases blanches vides (avant resolution) avec leur numero de slot
def display_grid(grid: CrosswordGrid, solution: Dict[Tuple[int, int], str] = None):
"""Affiche la grille avec matplotlib."""
fig, ax = plt.subplots(figsize=(8, 8))
# Dessiner les cases
for r in range(grid.rows):
for c in range(grid.cols):
if (r, c) in grid.black_cells:
# Case noire
rect = plt.Rectangle((c, grid.rows - r - 1), 1, 1,
facecolor='black', edgecolor='black')
ax.add_patch(rect)
else:
# Case blanche
rect = plt.Rectangle((c, grid.rows - r - 1), 1, 1,
facecolor='white', edgecolor='black')
ax.add_patch(rect)
# Afficher la lettre si solution
if solution and (r, c) in solution:
ax.text(c + 0.5, grid.rows - r - 0.5, solution[(r, c)],
fontsize=20, ha='center', va='center')
ax.set_xlim(0, grid.cols)
ax.set_ylim(0, grid.rows)
ax.set_aspect('equal')
ax.axis('off')
plt.title('Grille de mots croises')
plt.show()
display_grid(grid)
Le solveur CP-SAT (Constraint Programming - Satisfiability) de Google OR-Tools est l’un des solveurs de contraintes les plus performants au monde. Il combine :
C’est cette hybridation qui permet de resoudre en quelques millisecondes des problemes ou un backtracking pur echoue apres 50 000 noeuds.
slot_words[i] avec un domaine explicite (les indices de mots possibles)model.Add(words[slot_words[i]][p] == words[slot_words[j]][q]) exprime l’egalite de lettres aux intersectionsLa classe CrosswordCSP encapsule : - Le modele CP-SAT - Les variables (index de mot par slot) - Les contraintes (egalites de lettres aux intersections) - L’appel au solveur
L’API model.Add(element_var == array[index_var]) permet de relier une variable a un element d’un tableau de facon native, sans boucle explicite.
La cellule affiche “Solution trouvee avec 24 mots !” – le solveur a assigne un mot a chacun des 24 slots en un temps tres court (millisecondes). La performance est suffisante pour traiter des grilles beaucoup plus grandes (15x15, 21x21) sans modification du code.
class CrosswordCSP:
"""Solveur CSP pour mots croises avec OR-Tools."""
def __init__(self, grid: CrosswordGrid, dictionary: Dict[int, List[str]]):
self.grid = grid
self.dictionary = dictionary
self.model = cp_model.CpModel()
self.solver = cp_model.CpSolver()
# Variables
self.slot_words = {} # slot_id -> IntVar (index du mot)
self.cell_letters = {} # (r, c) -> IntVar (0-25 pour A-Z)
self._create_variables()
self._add_constraints()
def _create_variables(self):
"""Cree les variables de decision."""
# Variables pour les mots de chaque slot
for slot in self.grid.slots:
words_of_length = self.dictionary.get(slot.length, [])
if words_of_length:
self.slot_words[slot.id] = self.model.NewIntVar(
0, len(words_of_length) - 1, f'slot_{slot.id}'
)
# Variables pour les lettres de chaque case
for r in range(self.grid.rows):
for c in range(self.grid.cols):
if self.grid.is_white(r, c):
self.cell_letters[(r, c)] = self.model.NewIntVar(
0, 25, f'cell_{r}_{c}'
)
def _add_constraints(self):
"""Ajoute les contraintes."""
# Contrainte 1: Les lettres du mot doivent correspondre aux cases
for slot in self.grid.slots:
if slot.id not in self.slot_words:
continue
words_of_length = self.dictionary.get(slot.length, [])
for pos, (r, c) in enumerate(slot.cells):
# Pour chaque position du mot, la lettre doit correspondre
# On utilise un element de tableau
# Contrainte de table: pour chaque mot possible, extraire la lettre
letter_values = []
for word in words_of_length:
letter = word[pos].upper()
letter_values.append(ord(letter) - ord('A'))
# Contrainte: cell_letters[(r,c)] == slot_words[slot.id][pos]
self.model.AddElement(
self.slot_words[slot.id],
letter_values,
self.cell_letters[(r, c)]
)
def solve(self, time_limit: int = 30) -> bool:
"""Resout le probleme."""
self.solver.parameters.max_time_in_seconds = time_limit
self._status = self.solver.Solve(self.model)
return self._status == cp_model.OPTIMAL or self._status == cp_model.FEASIBLE
def get_solution(self) -> Dict[Tuple[int, int], str]:
"""Retourne la solution."""
# Utiliser StatusName(self._status) pour verifier le statut (correction API OR-Tools)
if self.solver.StatusName(self._status) == "UNKNOWN":
return {}
solution = {}
for (r, c), var in self.cell_letters.items():
letter_idx = self.solver.Value(var)
solution[(r, c)] = chr(ord('A') + letter_idx)
return solution
def get_words(self) -> Dict[int, str]:
"""Retourne les mots choisis pour chaque slot."""
# Utiliser StatusName(self._status) pour verifier le statut (correction API OR-Tools)
if self.solver.StatusName(self._status) == "UNKNOWN":
return {}
words = {}
for slot in self.grid.slots:
if slot.id in self.slot_words:
word_idx = self.solver.Value(self.slot_words[slot.id])
words[slot.id] = self.dictionary[slot.length][word_idx]
return words
# Resolution
csp = CrosswordCSP(grid, DICTIONARY)
print("Resolution CSP en cours...")
if csp.solve(time_limit=10):
solution = csp.get_solution()
words = csp.get_words()
print(f"Solution trouvee avec {len(words)} mots!")
display_grid(grid, solution)
else:
print("Pas de solution trouvee")Resolution CSP en cours...
Solution trouvee avec 24 mots!
Le solveur CP-SAT a trouve une solution complete en un temps tres court : “Solution trouvee avec 24 mots !” signifie que les 24 slots ont recu un mot du dictionnaire. La performance de CP-SAT tient a plusieurs facteurs :
model.AddElement(words_array, index_var, target_var) lie directement une variable a un element d’un tableauFigureCanvasAgg est benign (kernel headless, pas d’interaction)Cette performance exceptionnelle peut masquer la complexite du probleme. Pour apprecier la difficulte, il faut la comparer aux 50 001 noeuds du backtracking pur (section 4) et aux 33 noeuds du forward checking (section 5).
Après avoir resolu la grille avec le solveur CSP, il est important de pouvoir verifier qu’une solution est correcte. Implementez une fonction validate_solution qui verifie que :
Indices : - Utilisez csp.get_words() pour obtenir les mots choisis par le solveur - Pour chaque intersection (slot_h_id, slot_v_id, (pos_h, pos_v)), verifiez que la lettre a la position pos_h du mot horizontal correspond a la lettre a la position pos_v du mot vertical - Utilisez un Counter ou un set pour detecter les doublons
La validation est un garde-fou essentiel pour tout solveur : un solveur peut retourner une solution syntaxiquement valide mais semantiquement incorrecte si les contraintes sont mal formulees. C’est aussi un excellent exercice de prise en main de la structure de donnees : on parcourt les intersections, on accede aux mots par slot, on verifie les positions lettre par lettre.
La cellule affiche actuellement “Exercice a completer” – c’est normal, vous devez implementer la fonction avant l’execution.
def validate_solution(grid: CrosswordGrid, dictionary: Dict[int, List[str]],
words: Dict[int, str]) -> Tuple[bool, List[str]]:
"""
Valide qu'une solution de mots croises est correcte.
Parameters:
grid: La grille de mots croises
dictionary: Dictionnaire des mots par longueur
words: Dictionnaire {slot_id: mot} representant la solution
Returns:
Tuple (est_valide, liste_erreurs)
"""
# TODO etudiant : implementer la validation
# Etape 1 : verifier que chaque mot est dans le dictionnaire
# (pour chaque slot_id, le mot doit etre dans dictionary[slot.length])
# Etape 2 : verifier la coherence des intersections
# (grid.get_intersections() retourne les triplets)
# Etape 3 : verifier qu'aucun mot n'est utilise plus d'une fois
# Indice : utiliser un set ou Counter pour les doublons
return None, [] # TODO etudiant : remplacer par la vraie validation
# Test sur la solution CSP (si elle existe)
# if words:
# valid, errors = validate_solution(grid, DICTIONARY, words)
# print(f"Solution valide : {valid}")
# for err in errors:
# print(f" - {err}")
# else:
# print("Pas de solution CSP a valider")
print("Exercice a completer : validation d'une solution de mots croises")Exercice a completer : validation d'une solution de mots croisesCorrection complète (mêmes arguments que le squelette typé), déplacée après la cellule à compléter :
def validate_solution(grid, dictionary, words):
errors = []
# 1. Verifier que chaque mot est dans le dictionnaire de la bonne longueur
for slot_id, word in words.items():
if len(word) != grid.slots[slot_id].length:
errors.append(f"Slot {slot_id}: longueur {len(word)} != {grid.slots[slot_id].length}")
if word not in dictionary[grid.slots[slot_id].length]:
errors.append(f"Slot {slot_id}: mot '{word}' pas dans le dictionnaire")
# 2. Verifier les intersections
for h_id, v_id, (p_h, p_v) in grid.intersections:
if h_id in words and v_id in words:
if words[h_id][p_h] != words[v_id][p_v]:
errors.append(f"Intersection ({h_id}, {v_id}): '{words[h_id][p_h]}' != '{words[v_id][p_v]}'")
# 3. Verifier les doublons
seen = Counter(words.values())
for word, count in seen.items():
if count > 1:
errors.append(f"Mot '{word}' utilise {count} fois")
return (len(errors) == 0, errors)Comparaison avec un algorithme de backtracking classique.
Le backtracking est l’algorithme CSP le plus naif : il assigne les variables une par une, et “recule” (backtrack) des qu’une contrainte est violee. Sans aucune forme d’inference, il peut explorer un nombre exponentiel de branches.
backtrack(assignment):
si assignment complete: retourner assignment
choisir variable v non assignee
pour chaque valeur dans domain(v):
si v = valeur compatible avec assignment:
assigner v
resultat = backtrack(assignment)
si resultat: retourner resultat
desassigner v
retourner NoneSur notre probleme, le backtracking pur atteint les 50 000 noeuds en ~1 seconde et n’a toujours pas trouve de solution. C’est l’illustration classique de l’explosion combinatoire : l’espace de recherche est trop grand pour etre explore exhaustivement.
La cellule affiche “Recherche coupee apres 1.294s (50001 noeuds)” puis un message indiquant que l’espace de recherche est trop grand. C’est la demonstration par l’experience que le backtracking pur ne suffit pas pour ce probleme.
Ce resultat n’est pas un echec : c’est le point de depart pour comprendre pourquoi les techniques de propagation (sections 5 et 5b) sont essentielles. Sans avoir vu le backtracking s’essouffler, on ne mesurerait pas le gain apporte par l’inference.
Dans la cellule suivante, le forward checking (FC) reduit drastiquement le nombre de noeuds explores (33 au lieu de 50 001) en eliminant les valeurs incompatibles avant d’explorer chaque branche. Le gain est de 3 ordres de grandeur.
class CrosswordBacktracking:
"""Solveur par backtracking simple."""
def __init__(self, grid: CrosswordGrid, dictionary: Dict[int, List[str]]):
self.grid = grid
self.dictionary = dictionary
self.assignment = {} # slot_id -> word
self.letter_grid = {} # (r, c) -> letter
self.nodes_explored = 0
self._cutoff = False # Indique si la recherche a ete coupee
def solve(self, max_nodes: int = 100_000) -> bool:
"""Resout par backtracking avec limite de noeuds."""
self.nodes_explored = 0
self._max_nodes = max_nodes
self._cutoff = False
return self._backtrack(0)
def _backtrack(self, slot_idx: int) -> bool:
"""Backtracking recursif."""
self.nodes_explored += 1
if self.nodes_explored > self._max_nodes:
self._cutoff = True
return False
if slot_idx >= len(self.grid.slots):
return True # Tous les slots sont remplis
slot = self.grid.slots[slot_idx]
words = self.dictionary.get(slot.length, [])
# Filtrer les mots compatibles
compatible_words = []
for word in words:
if self._is_compatible(slot, word):
compatible_words.append(word)
# Essayer chaque mot compatible
for word in compatible_words:
# Assigner
self.assignment[slot.id] = word
self._assign_letters(slot, word)
# Recursion
if self._backtrack(slot_idx + 1):
return True
# Arreter si cutoff
if self._cutoff:
return False
# Backtrack
self._unassign_letters(slot)
del self.assignment[slot.id]
return False
def _is_compatible(self, slot: Slot, word: str) -> bool:
"""Verifie si le mot est compatible avec l'assignation actuelle."""
for pos, (r, c) in enumerate(slot.cells):
if (r, c) in self.letter_grid:
if self.letter_grid[(r, c)] != word[pos].upper():
return False
return True
def _assign_letters(self, slot: Slot, word: str):
"""Assigne les lettres du mot."""
for pos, (r, c) in enumerate(slot.cells):
self.letter_grid[(r, c)] = word[pos].upper()
def _unassign_letters(self, slot: Slot):
"""Desassigne les lettres du slot."""
for r, c in slot.cells:
# Ne supprimer que si pas utilise par un autre slot
used = False
for other_id, other_word in self.assignment.items():
if other_id == slot.id:
continue
other_slot = self.grid.slots[other_id]
if (r, c) in other_slot.cells:
used = True
break
if not used:
del self.letter_grid[(r, c)]
def get_solution(self) -> Dict[Tuple[int, int], str]:
"""Retourne la solution."""
return self.letter_grid.copy()
# Resolution avec limite de noeuds
bt = CrosswordBacktracking(grid, DICTIONARY)
print("Resolution Backtracking en cours...")
import time
start = time.time()
if bt.solve(max_nodes=50_000):
elapsed = time.time() - start
print(f"Solution trouvee en {elapsed:.3f}s ({bt.nodes_explored} noeuds)")
solution_bt = bt.get_solution()
display_grid(grid, solution_bt)
elif bt._cutoff:
elapsed = time.time() - start
print(f"Recherche coupee apres {elapsed:.3f}s ({bt.nodes_explored} noeuds)")
print("L'espace de recherche est trop grand pour le backtracking pur.")
print("Le solveur CSP (OR-Tools) est mieux adapte a ce probleme.")
else:
print("Pas de solution trouvee")Resolution Backtracking en cours...
Recherche coupee apres 0.657s (50001 noeuds)
L'espace de recherche est trop grand pour le backtracking pur.
Le solveur CSP (OR-Tools) est mieux adapte a ce probleme.La sortie du backtracking est tres instructive : “Recherche coupee apres 1.294s (50001 noeuds)”. Voici ce que cela signifie :
Les mots croises ont un espace de recherche doublement exponentiel :
Sans propagation, le backtracking essaie chaque combinaison une par une. Meme a 1 million de noeuds par seconde, il faudrait 10^25 secondes pour tout explorer – plus que l’age de l’univers (4.3×10^17 secondes).
Le backtracking est algorithmiquement correct mais pratiquement inutilisable sur ce probleme. C’est l’illustration classique de l’explosion combinatoire : un probleme de taille modeste (24 variables) devient intractable sans inference.
Dans la section suivante, le forward checking ajoute une couche d’inference : apres chaque assignation, on elimine des domaines des slots non encore assignes toutes les valeurs incompatibles. Cette simple astuce reduit l’espace de 50 001 a 33 noeuds, un gain de 3 ordres de grandeur.
L’ajout de propagation de contraintes (forward checking) reduit l’espace de recherche.
Le forward checking (FC) est une technique de propagation locale : apres chaque assignation d’une variable, on elimine des domaines des variables non encore assigneees toutes les valeurs incompatibles avec la nouvelle assignation.
Pour chaque slot voisin d’un slot assigne, on retire du domaine de ce voisin tous les mots qui ne partagent pas la lettre imposee a l’intersection. Si le domaine d’un voisin devient vide, on backtrack immediatement (fail-fast) sans explorer les autres valeurs du slot courant.
Le FC elimine les branches mortes des qu’elles apparaissent, au lieu d’attendre l’assignation d’une troisieme variable pour detecter un conflit. Sur les mots croises, cela suffit a passer de 50 000 noeuds a 33 noeuds.
L’implementation inclut aussi l’heuristique MRV (Minimum Remaining Values) : on choisit en priorite le slot dont le domaine est le plus petit. C’est une heuristique fail-first : si un slot n’a qu’un mot possible, mieux vaut l’assigner tout de suite pour eliminer rapidement les autres branches.
Le FC ne propage qu’aux voisins directs de la variable assigneee. Si une variable A est assigneee, que B est voisin de A, et que C est voisin de B mais pas de A, alors la reduction du domaine de B n’est pas reportee sur C. AC-3 (section 5b) generalise cette idee : il propage dans tout le reseau jusqu’a un point fixe.
La cellule affiche “ForwardChecking (termine): 0.0005s (moyenne 33 noeuds)”. Le gain est spectaculaire : 50 001 noeuds en 1.06s (backtracking) -> 33 noeuds en 0.5ms (FC + MRV), soit un facteur 1500 en temps et 1500 en noeuds explores.
class CrosswordForwardChecking(CrosswordBacktracking):
"""Solveur avec forward checking et heuristique MRV (Minimum Remaining Values).
Contrairement au backtracking pur, on maintient pour chaque slot non encore
assigne un *domaine* : l'ensemble des mots encore possibles. Des qu'on assigne
un mot a un slot, on *propage* la contrainte vers les slots voisins (ceux qui
le croisent) en retirant de leur domaine tout mot incompatible avec la lettre
imposee a l'intersection. Si la propagation vide le domaine d'un voisin, on
detecte immediatement le cul-de-sac (fail-fast) sans explorer toute la branche :
c'est tout l'interet du forward checking face a un backtracking qui s'essouffle.
"""
def __init__(self, grid: CrosswordGrid, dictionary: Dict[int, List[str]]):
super().__init__(grid, dictionary)
# Domaine courant de chaque slot (epure au fur et a mesure de la recherche)
self.domains = {
slot.id: set(dictionary.get(slot.length, []))
for slot in grid.slots
}
# Voisinages precalcules : slot_id -> [(slot_voisin, pos_dans_self, pos_dans_voisin)]
self._neighbors = self._build_neighbors()
def _build_neighbors(self) -> Dict[int, List[Tuple[int, int, int]]]:
"""Calcule, pour chaque slot, la liste des slots qui le croisent."""
neighbors = {slot.id: [] for slot in self.grid.slots}
for h_id, v_id, (pos_h, pos_v) in self.grid.get_intersections():
neighbors[h_id].append((v_id, pos_h, pos_v))
neighbors[v_id].append((h_id, pos_v, pos_h))
return neighbors
def _forward_check(self, slot_id: int, word: str):
"""
Propage l'assignation de ``word`` a ``slot_id`` : pour chaque voisin non
assigne, retire de son domaine les mots incompatibles avec la lettre
imposee a l'intersection.
Retourne la liste des (voisin, mots_retires) modifies, ou ``None`` si la
propagation vide le domaine d'un voisin (cul-de-sac).
"""
modified = []
for other_id, pos_self, pos_other in self._neighbors[slot_id]:
if other_id in self.assignment:
continue # deja assigne : contrainte deja verifiee
letter = word[pos_self].upper()
domain = self.domains[other_id]
incompatibles = {w for w in domain if w[pos_other].upper() != letter}
if incompatibles:
if len(domain) == len(incompatibles):
# Le domaine deviendrait vide : on restaure ce qui a deja ete
# retire dans CET appel, puis on signale l'echec (fail-fast).
for oid, removed in modified:
self.domains[oid] |= removed
return None
domain -= incompatibles
modified.append((other_id, incompatibles))
return modified
def _restore(self, modified):
"""Restaure les domaines apres un backtrack."""
for other_id, removed in modified:
self.domains[other_id] |= removed
def _get_mrv_slot(self) -> int:
"""
Heuristique MRV (Minimum Remaining Values) : choisir le slot non assigne
au plus petit domaine. On s'attaque d'abord aux variables les plus
contraintes, ce qui provoque une detection d'echec (et donc une coupe)
le plus tot possible dans l'arbre de recherche.
"""
unassigned = [
(slot.id, len(self.domains[slot.id]))
for slot in self.grid.slots
if slot.id not in self.assignment
]
if not unassigned:
return -1
return min(unassigned, key=lambda x: x[1])[0]
def solve(self, max_nodes: int = 100_000) -> bool:
"""Forward checking + MRV avec limite de noeuds."""
self.nodes_explored = 0
self._max_nodes = max_nodes
self._cutoff = False
self.assignment = {}
self.letter_grid = {}
# Reinitialiser les domaines (solve() peut etre rappele)
self.domains = {
slot.id: set(self.dictionary.get(slot.length, []))
for slot in self.grid.slots
}
return self._fc_backtrack()
def _fc_backtrack(self) -> bool:
"""Backtracking guidee par MRV avec propagation des domaines."""
self.nodes_explored += 1
if self.nodes_explored > self._max_nodes:
self._cutoff = True
return False
slot_id = self._get_mrv_slot()
if slot_id == -1:
return True # Tous les slots sont assignes
slot = self.grid.slots[slot_id]
# Le domaine ne contient PLUS QUE des mots coherents avec les assignations
# courantes (la propagation l'a deja epure) : inutile de re-verifier.
for word in sorted(self.domains[slot_id]):
self.assignment[slot_id] = word
self._assign_letters(slot, word)
modified = self._forward_check(slot_id, word)
if modified is not None:
if self._fc_backtrack():
return True
self._restore(modified)
# Backtrack
self._unassign_letters(slot)
del self.assignment[slot_id]
return False
# Comparaison des performances (avec limite de noeuds pour rester raisonnable)
def compare_solvers(grid, dictionary, n_trials=3):
"""Compare le backtracking pur et le forward checking sur la meme grille."""
import time
results = {
'Backtracking': {'times': [], 'nodes': []},
'ForwardChecking': {'times': [], 'nodes': []}
}
solvers = [
('Backtracking', CrosswordBacktracking),
('ForwardChecking', CrosswordForwardChecking),
]
for name, Solver in solvers:
for _ in range(n_trials):
solver = Solver(grid, dictionary)
start = time.time()
solver.solve(max_nodes=50_000)
elapsed = time.time() - start
results[name]['times'].append(elapsed)
results[name]['nodes'].append(solver.nodes_explored)
status = "coupe" if solver._cutoff else "termine"
print(f"{name:16} ({status}): {np.mean(results[name]['times']):.4f}s "
f"(moyenne {np.mean(results[name]['nodes']):.0f} noeuds)")
return results
print("Comparaison des solveurs...")
results = compare_solvers(grid, DICTIONARY, n_trials=3)Comparaison des solveurs...
Backtracking (coupe): 0.7279s (moyenne 50001 noeuds)
ForwardChecking (termine): 0.0004s (moyenne 33 noeuds)La sortie affiche les performances en parallele :
Backtracking (coupe): 1.0582s (moyenne 50001 noeuds)
ForwardChecking (termine): 0.0005s (moyenne 33 noeuds)Le forward checking elimine les valeurs incompatibles avant d’explorer chaque branche. Sur ce probleme :
Les temps mesures dependent du materiel et de la charge systeme. La variabilite est d’environ 10% d’une execution a l’autre – suffisante pour observer l’ordre de grandeur du gain mais pas pour comparer finement deux heuristiques proches.
Le forward checking ne propage qu’aux voisins directs. Si la reduction d’un voisin affecte un autre slot (non voisin), cette information est perdue. AC-3 (section 5b) remedie a cela en propageant dans tout le reseau.
Le forward checking (section 5) propage la contrainte vers les voisins directs d’une assignation, et seulement les slots non encore assignés. AC-3 généralise cette idée : il propage les contraintes dans tout le réseau, dans les deux sens, jusqu’à un point fixe, avant de lancer la recherche.
Le mécanisme. AC-3 maintient une file d’arcs (i, j) — paires de slots qui se croisent. Pour chaque arc, il révise le domaine de i : retire tout mot qui n’a aucun support dans le domaine de j (aucun mot de j dont la lettre à l’intersection coïncide). Si le domaine de i change, on remet en file tous les arcs entrants (k, i) : la réduction peut rendre (k, i) incohérent à son tour. L’algorithme s’arrête quand la file est vide (point fixe) ou qu’un domaine est vidé (insatisfiabilité détectée sans explorer la recherche).
Pourquoi cela compte. Un backtracking pur (section 4) aborde chaque slot avec le domaine complet du dictionnaire ; le forward checking ne réduit les domaines qu’au fil de la recherche. AC-3, lui, épure tous les domaines une bonne fois au départ : la recherche qui suit démarre d’un espace drastiquement plus petit, et peut même découvrir sans chercher que le problème est insatisfiable (un domaine vide pendant la propagation).
AC-3 est en O(E × d³) ou E est le nombre d’arcs et d la taille max des domaines. Sur notre probleme : - 24 slots, 36 intersections (arcs), ~20 mots par domaine initial - Complexite : 36 × 20³ = 288 000 operations au pire cas - En pratique : beaucoup moins car la reduction est rapide
La cellule code teste si AC-3 laisse un domaine vide (insatisfiable). Sur cette grille, tous les domaines restent non vides apres AC-3, donc le probleme est potentiellement satisfiable. La sortie confirme “Réseau cohérent après AC-3”.
La cellule affiche un tableau (une ligne par slot), montrant pour chaque slot la longueur, le nombre de mots dans le domaine avant et apres AC-3, et le nombre de mots retires. La derniere ligne resume l’espace combinatoire avant et apres (1.7×10³¹ -> 2.56×10²).
from collections import deque
def _revise(i_id, j_id, neighbors, domains):
"""Revise l'arc (i, j) : retire de domain_i tout mot sans support dans domain_j.
Retourne True si le domaine de i a ete réduit (il faut alors réexaminer les
arcs entrants de i). Un mot de i est sans support si aucun mot de j ne
partage sa lettre a la position d'intersection.
"""
pos_i = pos_j = None
for nb_id, p_self, p_other in neighbors[i_id]:
if nb_id == j_id:
pos_i, pos_j = p_self, p_other
break
if pos_i is None:
return False # i et j ne se croisent pas
removed = set()
domain_i = domains[i_id]
domain_j = domains[j_id]
for word_i in domain_i:
letter = word_i[pos_i].upper()
if not any(word_j[pos_j].upper() == letter for word_j in domain_j):
removed.add(word_i)
if removed:
domain_i -= removed
return True
return False
def ac3_reduce_domains(grid: CrosswordGrid, dictionary: Dict[int, List[str]]):
"""Cohérence d'arc (AC-3) sur le réseau de contraintes des mots croisés.
Propage les contraintes d'intersection jusqu'au point fixe. Retourne
(domains, consistent) : domains est le dictionnaire slot_id -> ensemble de
mots encore possibles après propagation ; consistent vaut False si un
domaine a ete vide (le probleme est alors prouve insatisfiable sans recherche).
"""
# Domaines initiaux : un mot par slot, indexés par slot id
domains = {slot.id: set(dictionary.get(slot.length, [])) for slot in grid.slots}
# Voisinages : slot_id -> liste de (voisin_id, pos_dans_self, pos_dans_voisin)
neighbors = {slot.id: [] for slot in grid.slots}
for h_id, v_id, (pos_h, pos_v) in grid.get_intersections():
neighbors[h_id].append((v_id, pos_h, pos_v))
neighbors[v_id].append((h_id, pos_v, pos_h))
# File initiale : tous les arcs (i, j) du réseau
queue = deque()
for i_id in neighbors:
for j_id, _, _ in neighbors[i_id]:
queue.append((i_id, j_id))
while queue:
i_id, j_id = queue.popleft()
if _revise(i_id, j_id, neighbors, domains):
if not domains[i_id]:
return domains, False # domaine vide -> insatisfiable
# Le domaine de i a change : remettre en file les arcs (k, i), k != j
for k_id, _, _ in neighbors[i_id]:
if k_id != j_id:
queue.append((k_id, i_id))
return domains, True
# Mesure firsthand de la réduction operee par AC-3 sur cette grille
sizes_before = {s.id: len(DICTIONARY.get(s.length, [])) for s in grid.slots}
domains_ac3, consistent = ac3_reduce_domains(grid, DICTIONARY)
sizes_after = {s.id: len(domains_ac3[s.id]) for s in grid.slots}
comb_before = int(np.prod(list(sizes_before.values()), dtype=object))
comb_after = int(np.prod(list(sizes_after.values()), dtype=object))
print(f"Réseau {'cohérent' if consistent else 'INCOHÉRENT (insatisfiable)'} après AC-3")
print(f"{len(grid.slots)} slots, {len(grid.get_intersections())} intersections\n")
print(f"{'slot':>5} {'longueur':>8} {'avant':>7} {'après':>6} {'coupé':>6}")
for s in grid.slots:
b, a = sizes_before[s.id], sizes_after[s.id]
print(f"{s.id:>5} {s.length:>8} {b:>7} {a:>6} {b - a:>6}")
print(f"\nEspace combinatoire avant AC-3 : {comb_before:.2e}")
print(f"Espace combinatoire après AC-3 : {comb_after:.2e}")
print(f"Facteur de réduction : {comb_before / max(comb_after, 1):.3g}")Réseau cohérent après AC-3
24 slots, 36 intersections
slot longueur avant après coupé
0 3 20 2 18
1 3 20 2 18
2 3 20 1 19
3 3 20 1 19
4 3 20 1 19
5 3 20 1 19
6 3 20 2 18
7 3 20 2 18
8 3 20 1 19
9 3 20 1 19
10 3 20 1 19
11 3 20 1 19
12 3 20 2 18
13 3 20 1 19
14 3 20 1 19
15 3 20 2 18
16 3 20 1 19
17 3 20 1 19
18 3 20 2 18
19 3 20 1 19
20 3 20 1 19
21 3 20 2 18
22 3 20 1 19
23 3 20 1 19
Espace combinatoire avant AC-3 : 1.68e+31
Espace combinatoire après AC-3 : 2.56e+02
Facteur de réduction : 6.55e+28La cellule AC-3 affiche, pour les 24 slots (36 intersections, toutes de longueur 3 — le dictionnaire français simplifié de cette expérience n’a que des mots de 3 lettres), un tableau à lire ainsi :
| Colonne | Signification |
|---|---|
slot |
Identifiant du slot (0 à 23) |
longueur |
Nombre de lettres du slot |
avant |
Taille du domaine avant AC-3 (20 pour chacun des 24 slots) |
après |
Taille du domaine après AC-3 (1 ou 2) |
coupé |
Nombre de mots éliminés (avant - après) |
L’effondrement mesuré. Les 24 domaines passent de 20 mots à 1 ou 2 candidats — 16 slots à 1 seul, 8 slots à 2 — et l’espace combinatoire s’écroule de 1.68×10³¹ à 2.56×10² combinaisons (soit exactement 2⁸ × 1¹⁶ = 256), un facteur de réduction de 6.55×10²⁸ (~10²⁹), avant d’avoir posé la moindre assignation. C’est précisément la marge que le backtracking pur (section 4) ne pouvait pas exploiter et qui le faisait s’essouffler : lui abordait chaque slot avec 20 candidats, quand AC-3 n’en laisse qu’un ou deux. Pour donner un ordre de grandeur : réduire l’espace de recherche de 10²⁹, c’est passer d’une recherche dans tout l’univers observable (10⁸⁰ atomes) à une recherche dans une salle de classe (10³ atomes) — et AC-3 fait cela gratuitement, avant même que la recherche commence.
Pourquoi un rendement si élevé ici. Les contraintes d’intersection sont extrêmement discriminantes : un mot de 3 lettres posé dans un slot élimine presque tous les mots des slots qui le croisent sans partager ses lettres aux positions d’intersection. C’est le signe d’un réseau bien connecté, avec un dictionnaire adapté à la taille des slots. La réciproque est instructive : si la grille était mal conçue (slots isolés, peu d’intersections), AC-3 éliminerait beaucoup moins de mots et la recherche qui suivrait serait plus difficile. Les grilles de mots croisés classiques ont une symétrie de rotation 180° qui garantit un équilibre entre mots longs et courts ; notre grille générée aléatoirement n’a pas cette symétrie, ce qui peut produire des zones sur-contraintes et des zones sous-contraintes — elle s’en tire bien ici, mais c’est une chance de la géométrie, pas une garantie.
Le pont avec le forward checking. FC est une propagation locale et paresseuse : elle ne touche qu’au voisinage d’une assignation, au moment où l’on assigne. AC-3 est une propagation globale et préventive : il établit d’emblée la cohérence de tout le réseau. Un solveur qui combine les deux — AC-3 en prétraitement, puis FC pendant la recherche — cumule les deux régimes : un espace de départ déjà épuré, et une coupe locale à chaque nœud. C’est d’ailleurs ce que fait OR-Tools en interne (section 3) : le solveur CP-SAT applique ses propres techniques de propagation bien plus puissantes qu’AC-3, ce qui explique qu’il résolve le problème quasi instantanément là où notre backtracking pur peinait.
Créer une grille de mots croises a partir de rien.
La generation suit trois etapes :
La densite classique pour les mots croises francais est entre 15% et 25% de cases noires :
L’implementation actuelle utilise un placement uniforme aleatoire, ce qui produit souvent des grilles avec des “trous” (regions entierement noires ou entierement blanches). Un meilleur algorithme utiliserait un motif symetrique (les mots croises francais ont une symetrie de rotation 180°) pour garantir une distribution esthetique.
La cellule affiche la nouvelle grille generee avec ses statistiques (nombre de cases noires, nombre de slots, longueur min/max des slots).
def generate_random_grid(rows: int, cols: int, density: float = 0.2) -> CrosswordGrid:
"""
Genere une grille aleatoire avec des cases noires.
Args:
density: proportion de cases noires (~0.2 pour mots croises classiques)
"""
black_cells = set()
for r in range(rows):
for c in range(cols):
if random.random() < density:
black_cells.add((r, c))
# Identifier les slots
slots = []
slot_id = 0
# Slots horizontaux
for r in range(rows):
start = 0
for c in range(cols + 1):
is_end = (c == cols) or (r, c) in black_cells
if is_end:
if c - start >= 2: # Minimum 2 lettres
cells = [(r, cc) for cc in range(start, c)]
slots.append(Slot(slot_id, r, start, c - start, 'H', cells))
slot_id += 1
start = c + 1
# Slots verticaux
for c in range(cols):
start = 0
for r in range(rows + 1):
is_end = (r == rows) or (r, c) in black_cells
if is_end:
if r - start >= 2:
cells = [(rr, c) for rr in range(start, r)]
slots.append(Slot(slot_id, start, c, r - start, 'V', cells))
slot_id += 1
start = r + 1
return CrosswordGrid(rows=rows, cols=cols, black_cells=black_cells, slots=slots)
# Generation
random_grid = generate_random_grid(5, 5, density=0.2)
print(f"Grille aleatoire: {random_grid.rows}x{random_grid.cols}")
print(f"Cases noires: {len(random_grid.black_cells)}")
print(f"Slots: {len(random_grid.slots)}")
display_grid(random_grid)Grille aleatoire: 5x5
Cases noires: 7
Slots: 10
La generation produit une nouvelle grille avec les parametres suivants :
| Aspect | Generation aleatoire | Generation optimisee |
|---|---|---|
| Rapidite | Tres rapide (quelques ms) | Plus lente (avec verification) |
| Qualite | Variable (slots isoles possibles) | Garantie (intersections maximales) |
| Symetrie | Aucune | Symetrie 180° classique |
| Repetabilite | Seed aleatoire | Seed deterministe |
Pour des grilles de qualite publication, on utilise plutot :
Le notebook compare trois solveurs sur la meme grille 7x7 :
| Solveur | Noeuds explores | Temps | Verdict |
|---|---|---|---|
| Backtracking pur | 50 001 (coupe) | ~1.0s | Pas de solution trouvee |
| Forward Checking + MRV | 33 | ~0.5ms | Solution trouvee |
| OR-Tools CP-SAT | ~0 (interne) | ~10ms | Solution trouvee |
Le passage du backtracking pur au forward checking represente un gain de 3 ordres de grandeur (50 001 -> 33 noeuds). Ce gain vient uniquement de la propagation locale appliquee apres chaque assignation. AC-3 ajouterait un facteur supplementaire en reduisant l’espace de recherche avant meme de commencer.
Pour un prototype ou un enseignement, FC + MRV est preferable : implementation simple, resultats immediats.
Pour un solveur de production sur des grilles 15x15 ou 21x21, CP-SAT est indispensable : son hybridation CP/SAT et ses techniques de no-good learning permettent de resoudre en quelques secondes des problemes ou les autres solveurs prendraient des heures.
def analyze_crossword_complexity(grid: CrosswordGrid, dictionary: Dict[int, List[str]]):
"""
Analyse la complexite du probleme.
"""
# Nombre de variables
n_slots = len(grid.slots)
n_cells = sum(1 for r in range(grid.rows) for c in range(grid.cols)
if grid.is_white(r, c))
# Taille des domaines
domain_sizes = [len(dictionary.get(slot.length, [])) for slot in grid.slots]
# Intersections
intersections = grid.get_intersections()
print("=== Analyse de complexite ===")
print(f"Slots: {n_slots}")
print(f"Cases blanches: {n_cells}")
print(f"Intersections: {len(intersections)}")
print(f"Taille moyenne des domaines: {np.mean(domain_sizes):.1f}")
print(f"Domaine total: {np.prod(domain_sizes, dtype=object):.2e} combinaisons")
analyze_crossword_complexity(grid, DICTIONARY)=== Analyse de complexite ===
Slots: 24
Cases blanches: 37
Intersections: 36
Taille moyenne des domaines: 20.0
Domaine total: 1.68e+31 combinaisonsModelisation CSP : Les mots croises sont un excellent exemple de CSP avec des variables interdependantes
Contraintes d’intersection : Les croisements horizontal/vertical contraignent fortement les solutions
Propagation : Le forward checking reduit drastiquement l’espace de recherche
Heuristiques : MRV (Minimum Remaining Values) choisit les slots les plus contraints en premier
Trois exercices pour approfondir la comprehension :
L’heuristique LCV consiste a choisir en priorite les mots qui eliminent le moins de choix pour les autres slots. Implementez cette heuristique dans le solveur backtracking.
Indices : - Pour chaque mot candidat, comptez combien de mots deviennent incompatibles dans les slots adjacents - Triez les candidats par ordre croissant de contraintes imposees - Comparez les performances avec et sans LCV
LCV peut reduire de 20 a 50% le nombre de noeuds explores par rapport a un ordre arbitraire, en combinaison avec MRV. C’est l’une des heuristiques les plus efficaces en pratique.
def count_eliminated_words(grid: CrosswordGrid, dictionary: Dict[int, List[str]],
slot: Slot, word: str, current_assignment: Dict[int, str]) -> int:
"""
Compte le nombre de mots elimines dans les slots adjacents si on assigne 'word' a 'slot'.
Args:
grid: La grille de mots croises
dictionary: Dictionnaire des mots par longueur
slot: Le slot auquel on veut assigner le mot
word: Le mot candidat
current_assignment: Assignation actuelle (slot_id -> word)
Returns:
Nombre total de mots elimines dans les slots adjacents
"""
# Exercice: Identifier les slots qui partagent des cases avec 'slot'
pass
# Exercice: Pour chaque slot adjacent, compter les mots incompatibles
pass
# Exercice: Retourner la somme des mots elimines
pass
return 0 # TODO etudiant : remplacer
def solve_with_lcv(grid: CrosswordGrid, dictionary: Dict[int, List[str]]) -> Tuple[bool, int]:
"""
Solveur backtracking avec heuristique LCV.
Returns:
Tuple (succes, noeuds_explores)
"""
# Exercice: Adapter le solveur CrosswordBacktracking pour utiliser LCV
# Indice: Trier les mots candidats avec count_eliminated_words
return False, 0 # TODO etudiant : remplacer
print("Exercice a completer : heuristique LCV pour mots croises")Exercice a completer : heuristique LCV pour mots croisesLa fonction generate_random_grid créé des grilles aleatoires qui peuvent etre trop simples ou trop difficiles. Implementez une generation qui maximise le nombre d’intersections.
Indices : - Une bonne grille de mots croises a beaucoup d’intersections - Evitez les slots isoles (sans intersection) - Une densite de cases noires entre 15% et 25% est optimale
Au lieu d’un placement uniforme, utiliser un algorithme de croissance :
Une grille 7x7 bien concue doit avoir : - 20 a 30 intersections - Aucun slot isole (sans intersection) - Ratio cases noires / total entre 0.15 et 0.25
La cellule affiche la grille generee avec ses statistiques (nombre de cases noires, nombre de slots, nombre d’intersections, ratio mots/dictionnaire). Comparez aux valeurs d’une generation purement aleatoire (densite 0.2) : vous devriez observer une amelioration du nombre d’intersections de 20 a 50%.
def generate_optimized_grid(rows: int, cols: int, target_intersections: int = None) -> CrosswordGrid:
"""
Genere une grille optimisee pour maximiser les intersections.
Args:
rows: Nombre de lignes
cols: Nombre de colonnes
target_intersections: Nombre cible d'intersections (optionnel)
Returns:
CrosswordGrid avec un maximum d'intersections
"""
# Exercice: Implementer une strategie de generation
# Indice: Commencer par placer des cases noires strategiquement
pass
# Exercice: Calculer le nombre d'intersections
pass
# Exercice: Ajuster les cases noires pour maximiser les intersections
pass
return None # TODO etudiant : remplacer
def evaluate_grid_quality(grid: CrosswordGrid) -> float:
"""
Evalue la qualite d'une grille de mots croises.
Returns:
Score de qualite entre 0 et 1 (1 = excellent)
"""
# Exercice: Calculer un score base sur:
# - Nombre d'intersections / nombre maximum possible
# - Distribution equilibree des longueurs de slots
# - Absence de slots isoles
return 0.0 # TODO etudiant : remplacer
print("Exercice a completer : generation de grille optimisee")Exercice a completer : generation de grille optimiseeComment modifieriez-vous le solveur pour generer des grilles sur un thème donne (ex: informatique, nature, sport) ?
Questions a considerer : - Comment structurer un dictionnaire thematique ? - Faut-il penaliser les mots hors-thème ou les interdire totalement ? - Quel impact sur la difficulte de resolution ?
Reponse attendue : Une description textuelle de votre approche (pas de code requis).
Un dictionnaire thematique peut etre structure de plusieurs facons :
| Strategie | Avantage | Inconvenient |
|---|---|---|
| Interdire hors-theme | Grille purement thematique | Plus dur a resoudre |
| Penaliser hors-theme | Flexibilite | Risque de dilution |
| Bonus thematique | Encourage les mots cles | Biais algorithmique |
Un dictionnaire thematique est plus petit qu’un dictionnaire general (50 000 -> 5 000 mots), donc : - Domaines plus petits - Moins d’ambiguite - Resolution plus rapide… mais aussi moins de mots disponibles pour les intersections
La cle est de trouver le bon equilibre entre thematique stricte et jouabilite.
Ce notebook a modelise la generation de mots croises comme un problème de satisfaction de contraintes (CSP).
| Solveur | Grille 7x7 | Performance |
|---|---|---|
| OR-Tools CP-SAT | 24 mots places | Resolution instantanee |
| Backtracking naif | Aucune solution | 50 001 noeuds, 0.714s, echec |
Le contraste est saisissant : le même problème est trivial pour CP-SAT et intraitable pour le backtracking naif. La propagation de contraintes de CP-SAT (arc-consistance, bound tightening) elague massivement l’espace de recherche, tandis que le backtracking sans inference explore aveuglement des branches sans issue.
La modelisation est elegante : les variables sont les emplacements (slots), les domaines sont les mots du dictionnaire, et les contraintes sont les intersections de lettres entre mots horizontaux et verticaux.
Les memes principes s’appliquent a :
Suite : App-15 - Planification sportive | Retour au sommaire