Sudoku-10-ORTools-Python : OR-Tools CP-SAT (Python)

Navigation : << Python Backtracking | Index | Z3 Python >>

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Modeliser le Sudoku avec un solveur de programmation par contraintes (OR-Tools CP-SAT) 2. Comprendre la différence entre approche imperative et declarative 3. Comparer les performances d’un solveur industriel avec le backtracking 4. Utiliser la contrainte AllDifferent pour modéliser des problèmes combinatoires

Duree estimee : ~10 min | Prerequis : Sudoku-00 Environment | Lien : Voir CSP-3-Avance

Ce notebook implemente un solveur de Sudoku utilisant une approche declarative (par opposition a l’approche imperative du backtracking) :

  • Google OR-Tools CP-SAT : Solveur de Programmation par Contraintes avec techniques SAT

Cette approche est equivalente au notebook C# Sudoku-10-ORTools-CSharp.ipynb.

Paradigme declaratif vs imperatif

Aspect Backtracking (imperatif) CP-SAT (declaratif)
Comment resoudre On programme l’algorithme On decrit les contraintes
Optimisations Manuelles (MRV, etc.) Automatiques par le solveur
Expressivite Code spécifique au problème Modèle generique reutilisable
Maintenance Algorithme a maintenir Seulement les contraintes

Avantages de CP-SAT

  1. Annees d’optimisation : CP-SAT integre des decennies de recherche en optimisation
  2. Propagation de contraintes : Reduction automatique des domaines
  3. Apprentissage de conflits : Evite de repeter les mêmes erreurs (CDCL)
  4. Parallelisation : Exploitation automatique du multi-core

Installation

pip install ortools
# Installation silencieuse d'OR-Tools (uniquement si absent de l'environnement)
import subprocess, sys
try:
    import ortools  # noqa: F401
except ImportError:
    subprocess.check_call([sys.executable, '-m', 'pip', 'install', 'ortools'])

Importation et verification de la bibliotheque

OR-Tools est maintenant installe. La cellule suivante importe le module cp_model depuis le package ortools.sat.python et verifie que l’installation est fonctionnelle. Le sous-module SAT (Boolean Satisfiability) fournit le solveur CP-SAT qui combine programmation par contraintes et techniques de resolution SAT.

# Imports
import time
from typing import List, Optional, Tuple

# Verifier l'installation
try:
    from ortools.sat.python import cp_model
    print(f"OR-Tools importe avec succes")
except ImportError:
    print("OR-Tools non installe. Executez: pip install ortools")
OR-Tools importe avec succes

1. Classe SudokuGrid (réutilisée)

Même représentation que dans le notebook Backtracking. La classe est indépendante du solveur utilisé, ce qui permet de comparer facilement différentes approches sur les mêmes puzzles.

1. Configuration du chemin vers les puzzles

# Configuration du chemin vers les puzzles
import os
from pathlib import Path

# Définir le chemin absolu vers le dossier Puzzles
NOTEBOOK_DIR = Path.cwd()
PUZZLES_DIR = NOTEBOOK_DIR / "Puzzles"

# Vérifier que le dossier existe
if PUZZLES_DIR.exists():
    print(f"Dossier Puzzles: {PUZZLES_DIR.name}")
    puzzle_files = list(PUZZLES_DIR.glob('*.txt'))
    print(f"Fichiers disponibles: {[f.name for f in puzzle_files]}")
else:
    print("ATTENTION: Dossier Puzzles non trouvé")
    PUZZLES_DIR = Path(os.getcwd()) / "Puzzles"
Dossier Puzzles: Puzzles
Fichiers disponibles: ['Sudoku_Easy51.txt', 'Sudoku_hardest.txt', 'Sudoku_top95.txt']

Definition de la classe de representation de grille Sudoku et du solveur OR-Tools.

class SudokuGrid:
    """Représentation d'une grille de Sudoku 9x9."""
    
    def __init__(self, grid: Optional[List[List[int]]] = None):
        if grid is None:
            self.cells = [[0] * 9 for _ in range(9)]
        else:
            self.cells = [row[:] for row in grid]
    
    @classmethod
    def from_string(cls, s: str) -> 'SudokuGrid':
        s = s.replace('.', '0').replace(' ', '').replace('\n', '')
        if len(s) != 81:
            raise ValueError(f"La chaîne doit avoir 81 caractères")
        grid = cls()
        for i in range(81):
            grid.cells[i // 9][i % 9] = int(s[i])
        return grid
    
    def clone(self) -> 'SudokuGrid':
        return SudokuGrid(self.cells)
    
    def __str__(self) -> str:
        lines = []
        for r in range(9):
            if r > 0 and r % 3 == 0:
                lines.append('-' * 21)
            row_str = ''
            for c in range(9):
                if c > 0 and c % 3 == 0:
                    row_str += '| '
                val = self.cells[r][c]
                row_str += (str(val) if val != 0 else '.') + ' '
            lines.append(row_str)
        return '\n'.join(lines)

def load_puzzles(filepath: str, max_puzzles: int = None) -> List[str]:
    puzzles = []
    with open(filepath, 'r') as f:
        for line in f:
            line = line.strip()
            if len(line) >= 81:
                puzzles.append(line[:81])
                if max_puzzles and len(puzzles) >= max_puzzles:
                    break
    return puzzles

# Charger puzzles
easy_puzzles = load_puzzles(str(PUZZLES_DIR / 'Sudoku_Easy51.txt'), max_puzzles=10)
hard_puzzles = load_puzzles(str(PUZZLES_DIR / 'Sudoku_hardest.txt'))
print(f"Puzzles chargés: {len(easy_puzzles)} faciles, {len(hard_puzzles)} difficiles")
Puzzles chargés: 10 faciles, 11 difficiles

Exercice 1 : Compter les contraintes initiales

Objectif : Ecrire une fonction qui analyse une grille de Sudoku et compte les contraintes déjà imposees par les valeurs initiales.

Contexte : Avant de lancer un solveur, il est utile de savoir combien de contraintes sont déjà fixees. Chaque cellule non vide impose une exclusion sur ses 20 voisins dans le graphe de contraintes (ligne + colonne + bloc). Le nombre de cellules fixees et le nombre total de contraintes d’exclusion donnent une idee de la difficulte du puzzle.

Étapes : 1. Parcourir les 81 cellules de la grille 2. Compter le nombre de cellules non nulles (valeurs fixees) 3. Pour chaque cellule fixee, compter ses voisins non nuls (contraintes binaires imposées) 4. Retourner un dictionnaire avec fixed_cells, total_constraints et empty_cells

Indice : Deux cellules sont en contrainte binaire si elles sont dans la même ligne, colonne ou bloc. Attention a ne pas compter les doublons (pair A-B = pair B-A).

def count_initial_constraints(grid: SudokuGrid) -> dict:
    """
    Analyse les contraintes initiales d'une grille de Sudoku.
    
    Args:
        grid: grille de Sudoku partiellement remplie
    
    Returns:
        dict avec 'fixed_cells', 'empty_cells', 'total_constraints'
        total_constraints = nombre de paires (i,j) ou les deux cellules sont non nulles
        et en contrainte (meme ligne, colonne ou bloc)
    """
    # TODO etudiant : implementer le comptage des contraintes
    # Etape 1 : compter les cellules non nulles
    # Etape 2 : identifier les paires de cellules en contrainte (ligne/colonne/bloc)
    # Etape 3 : compter les paires ou les deux cellules sont non nulles
    # Etape 4 : retourner le dictionnaire
    return {"fixed_cells": 0, "empty_cells": 0, "total_constraints": 0}  # TODO etudiant : remplacer

# Test sur un puzzle facile
test_constraints = SudokuGrid.from_string(easy_puzzles[0])
result = count_initial_constraints(test_constraints)
print(f"Cellules fixees: {result['fixed_cells']}/81")
print(f"Cellules vides: {result['empty_cells']}")
print(f"Paires contraintes actives: {result['total_constraints']}")
print("Exercice a completer")
Cellules fixees: 0/81
Cellules vides: 0
Paires contraintes actives: 0
Exercice a completer

2. Solveur OR-Tools CP-SAT

Google OR-Tools est une suite d’optimisation open-source. Le solveur CP-SAT (Constraint Programming with SAT) combine:

  • Programmation par contraintes (CP): Modélisation naturelle avec domaines et contraintes
  • Techniques SAT: Apprentissage de clauses, propagation unitaire, backjumping

Modélisation du Sudoku en CP

Le modèle se construit en 3 étapes:

  1. Variables: 81 variables entières, domaine {1..9}

    cells[(i, j)] = model.NewIntVar(1, 9, f'cell_{i}_{j}')

  2. Contraintes de valeurs initiales: Fixer les cases connues

    cells[(i, j)] = model.NewConstant(valeur_initiale)

  3. Contraintes AllDifferent: La contrainte clé du Sudoku

    model.AddAllDifferent([cells[(i, j)] for j in range(9)])  # Ligne
model.AddAllDifferent([cells[(i, j)] for i in range(9)])  # Colonne
model.AddAllDifferent([...])  # Bloc 3x3

Pourquoi CP-SAT est si rapide?

  • Propagation AllDifferent: Algorithme spécialisé O(n sqrt(n)) qui détecte les inconsistances
  • Arc Consistency: Réduit les domaines avant même de commencer la recherche
  • CDCL: Apprend des conflits pour éviter de les répéter
  • Restarts: Stratégie de redémarrage pour éviter les chemins sans issue
class ORToolsSolver:
    """Solveur Sudoku utilisant OR-Tools CP-SAT."""
    
    def solve(self, grid: SudokuGrid) -> bool:
        """Résout le Sudoku avec OR-Tools CP-SAT."""
        model = cp_model.CpModel()
        
        # Créer les variables: cells[i][j] in {1..9}
        cells = {}
        for i in range(9):
            for j in range(9):
                if grid.cells[i][j] != 0:
                    # Valeur fixée
                    cells[(i, j)] = model.NewConstant(grid.cells[i][j])
                else:
                    # Variable libre
                    cells[(i, j)] = model.NewIntVar(1, 9, f'cell_{i}_{j}')
        
        # Contraintes: toutes différentes par ligne
        for i in range(9):
            model.AddAllDifferent([cells[(i, j)] for j in range(9)])
        
        # Contraintes: toutes différentes par colonne
        for j in range(9):
            model.AddAllDifferent([cells[(i, j)] for i in range(9)])
        
        # Contraintes: toutes différentes par bloc 3x3
        for box_row in range(3):
            for box_col in range(3):
                box_cells = []
                for i in range(3):
                    for j in range(3):
                        box_cells.append(cells[(box_row * 3 + i, box_col * 3 + j)])
                model.AddAllDifferent(box_cells)
        
        # Résoudre
        solver = cp_model.CpSolver()
        status = solver.Solve(model)
        
        if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
            # Extraire la solution
            for i in range(9):
                for j in range(9):
                    grid.cells[i][j] = solver.Value(cells[(i, j)])
            return True
        
        return False

# Test
ortools_solver = ORToolsSolver()
test_grid = SudokuGrid.from_string(hard_puzzles[0])
print("Puzzle difficile:")
print(test_grid)

start = time.time()
solved = ortools_solver.solve(test_grid)
elapsed = (time.time() - start) * 1000

print(f"\nRésolu: {solved} en {elapsed:.2f} ms")
print("\nSolution:")
print(test_grid)
Puzzle difficile:
8 5 . | . . 2 | 4 . . 
7 2 . | . . . | . . 9 
. . 4 | . . . | . . . 
---------------------
. . . | 1 . 7 | . . 2 
3 . 5 | . . . | 9 . . 
. 4 . | . . . | . . . 
---------------------
. . . | . 8 . | . 7 . 
. 1 7 | . . . | . . . 
. . . | . 3 6 | . 4 . 

Résolu: True en 25.91 ms

Solution:
8 5 9 | 6 1 2 | 4 3 7 
7 2 3 | 8 5 4 | 1 6 9 
1 6 4 | 3 7 9 | 5 2 8 
---------------------
9 8 6 | 1 4 7 | 3 5 2 
3 7 5 | 2 6 8 | 9 1 4 
2 4 1 | 5 9 3 | 7 8 6 
---------------------
4 3 2 | 9 8 1 | 6 7 5 
6 1 7 | 4 2 5 | 8 9 3 
5 9 8 | 7 3 6 | 2 4 1

Exercice 2 : Verifier la validite d’une solution avec OR-Tools

Objectif : Ecrire une fonction qui utilise OR-Tools CP-SAT pour verifier qu’une grille Sudoku completée est valide.

Contexte : Après avoir resolu un puzzle, il est important de verifier que la solution respecte toutes les contraintes. Avec OR-Tools, on peut construire un modèle qui encode la solution proposee et verifier si elle satisfait toutes les contraintes AllDifferent.

Étapes : 1. Construire le modèle CP-SAT avec les 81 variables 2. Fixer chaque variable a la valeur de la grille proposee (utiliser NewConstant) 3. Ajouter les 27 contraintes AllDifferent (9 lignes + 9 colonnes + 9 blocs) 4. Resolver : si le modèle est faisable, la solution est valide

Indice : Si la grille est valide, le solveur trouvera une solution immediatement. Si une contrainte est violee, le solveur retournerai INFEASIBLE. Cette méthode est plus robuste qu’une verification manuelle car elle teste toutes les contraintes en un seul appel.

def verify_solution_with_ortools(grid: SudokuGrid) -> bool:
    """
    Verifie qu'une grille Sudoku completee est valide en utilisant OR-Tools CP-SAT.
    
    Args:
        grid: grille de Sudoku completee (toutes les cellules non nulles)
    
    Returns:
        True si la solution respecte toutes les contraintes, False sinon
    """
    # TODO etudiant : implementer la verification avec OR-Tools
    # Etape 1 : verifier que toutes les cellules sont non nulles
    # Etape 2 : creer le modele CP-SAT
    # Etape 3 : creer 81 constantes fixees aux valeurs de la grille
    # Etape 4 : ajouter les 27 contraintes AllDifferent (lignes, colonnes, blocs)
    # Etape 5 : resolver et retourner True si FEASIBLE
    return False  # TODO etudiant : remplacer par la verification reelle

# Test sur la solution valide obtenue precedemment
test_verify = SudokuGrid.from_string(hard_puzzles[0])
ortools_solver.solve(test_verify)  # Resoudre d'abord
is_valid = verify_solution_with_ortools(test_verify)
print(f"Solution valide : {is_valid}")
print("Exercice a completer")
Solution valide : False
Exercice a completer

Interpretation : Résultat OR-Tools CP-SAT

Le solveur OR-Tools a resolu un puzzle difficile en quelques dizaines de millisecondes (temps exact affiche par la cellule de resolution ci-dessus ; CP-SAT etant non-deterministe, la valeur varie d’une execution a l’autre et selon la machine).

Aspect Valeur Signification
Temps de resolution (cellule ci-dessus) Performance excellente
Statut FEASIBLE Solution trouvee
Approche Declarative Modèle de contraintes, pas d’algorithme a ecrire

Points cles : 1. Simplicite du code : Seuls 30 lignes pour définir le modèle complet 2. Contrainte AllDifferent : OR-Tools l’implemente de maniere très efficace 3. Pas de parametrage : L’heuristique par defaut fonctionne très bien

Note technique : CP-SAT utilise la propagation de contraintes et l’apprentissage de conflits (CDCL) pour reduire rapidement l’espace de recherche.

3. Benchmark OR-Tools CP-SAT

Le benchmark evalue les performances du solveur OR-Tools CP-SAT sur des puzzles faciles et difficiles.

Metriques importantes

  • Temps total : Performance brute de bout en bout
  • Temps moyen par puzzle : Indicateur de la complexite moyenne
  • Taux de resolution : Devrait etre 100% (le solveur est complet)

Ce qu’on observe généralement

Aspect Performance
Puzzles faciles ~10-20 ms par puzzle
Puzzles difficiles ~15-30 ms par puzzle
Temps d’initialisation Negligeable
Overhead par puzzle Minimal

Le solveur OR-Tools est considerablement plus rapide que le backtracking simple. Son avantage principal est la simplicite du code et la garantie de performance même sur des problemes plus complexes que le Sudoku standard.

Exercice : Ajouter une contrainte d’anti-symetrie

Objectif Ajoutez au modèle OR-Tools une contrainte qui force la première ligne a etre strictement croissante (1,2,3,4,5,6,7,8,9), eliminant ainsi les solutions symetriques par rotation/reflection.

Indice Utilisez model.Add(cells[0][i] == i+1) pour chaque colonne i de la ligne 0.

# EXERCICE : Ajouter une contrainte d'anti-symetrie
def solve_with_anti_symmetry(grid: SudokuGrid) -> dict:
    # TODO: Construisez le modele CP-SAT avec la contrainte supplementaire
    # que la premiere ligne doit etre (1,2,3,...,9)
    result = {}  # TODO etudiant
    return result
print("Exercice a completer")
Exercice a completer
def benchmark_ortools(puzzles: List[str], name: str):
    """Evalue les performances du solveur OR-Tools CP-SAT."""
    print(f"\n{'='*60}")
    print(f"Benchmark: {name} ({len(puzzles)} puzzles)")
    print('='*60)
    
    solver = ORToolsSolver()
    total_time = 0
    solved = 0
    
    for puzzle_str in puzzles:
        grid = SudokuGrid.from_string(puzzle_str)
        
        start = time.time()
        success = solver.solve(grid)
        elapsed = time.time() - start
        
        total_time += elapsed
        if success:
            solved += 1
    
    # Afficher resultats
    avg_time = (total_time / len(puzzles)) * 1000
    total_time_ms = total_time * 1000
    
    print(f"\n{'Solveur':<20} {'Résolus':<10} {'Temps total':<15} {'Temps moyen':<15}")
    print('-'*60)
    print(f"{'OR-Tools CP-SAT':<20} {solved}/{len(puzzles):<8} {total_time_ms:>10.2f} ms   {avg_time:>10.2f} ms")
    
    return {'solved': solved, 'total_time': total_time}

# Benchmark
benchmark_ortools(easy_puzzles, "Puzzles Faciles")
benchmark_ortools(hard_puzzles, "Puzzles Difficiles (Top 11)")

============================================================
Benchmark: Puzzles Faciles (10 puzzles)
============================================================

Solveur              Résolus    Temps total     Temps moyen    
------------------------------------------------------------
OR-Tools CP-SAT      10/10           163.81 ms        16.38 ms

============================================================
Benchmark: Puzzles Difficiles (Top 11) (11 puzzles)
============================================================

Solveur              Résolus    Temps total     Temps moyen    
------------------------------------------------------------
OR-Tools CP-SAT      11/11           201.94 ms        18.36 ms
{'solved': 11, 'total_time': 0.20194029808044434}

Interpretation : ce que revele le benchmark OR-Tools CP-SAT

Le benchmark oppose deux niveaux de difficulté et affiche deux résultats frappants :

Difficulté Puzzles résolus Temps moyen par puzzle
Faciles (10) 10/10 (benchmark ci-dessus)
Difficiles — Top 11 (11) 11/11 (benchmark ci-dessus)

  • Un taux de résolution de 100 % (21/21). OR-Tools CP-SAT résout intégralement les deux séries, y compris les 11 puzzles les plus ardents. C’est la signature d’un solveur complet (exact) : s’il existe une solution, il la trouve — sans time-out ni recours à une recherche aléatoire qui pourrait échouer.

  • Un facteur de difficulté modéré (typiquement sous 2x — voir le rapport exact dans le benchmark ci-dessus). C’est le point pédagogique essentiel. Là où un backtracking naïf subit une explosion combinatoire sur les puzzles difficiles (le nombre d’essais grimpe en flèche dès que les déductions simples s’épuisent), CP-SAT maintient une croissance quasi linéaire grâce à deux mécanismes : la propagation de contraintes (chaque déduction réduit l’espace de recherche avant tout retour-arrière) et la génération paresseuse de clauses (le solveur apprend des conflits rencontrés et coupe les branches stériles à la volée).

  • De l’ordre de quelques dizaines de ms par grille (benchmark ci-dessus). Pour un problème formellement NP-complet, ces temps sont remarquables et expliquent pourquoi la programmation par contraintes est la méthode industrielle de référence pour l’ordonnancement, l’affectation de ressources et les casse-têtes combinatoires — bien avant une recherche arborescente écrite « à la main ».

A retenir : la puissance de CP-SAT ne se lit pas dans le temps absolu, mais dans la faiblesse du facteur de difficulté. Un backtracking naïf verrait ce ratio exploser (souvent au-delà de 10x sur les mêmes puzzles) ; CP-SAT le maintient sous 2x. La section suivante (N-Reines) va confirmer cette efficacité en énumérant des dizaines de solutions d’un seul coup.

Exemple : Solveur OR-Tools CP-SAT pour le problème des N-Reines

Cet exemple montre comment adapter la modelisation OR-Tools CP-SAT du Sudoku pour resoudre un problème combinatoire classique : les N-Reines. L’objectif est de placer N reines sur un echiquier NxN sans qu’aucune ne puisse en capturer une autre, puis de compter toutes les solutions.

Technique utilisee

  1. N variables queen[i] representant la colonne de la reine de la ligne i
  2. Contrainte AddAllDifferent pour les colonnes (une seule reine par colonne)
  3. Contraintes de diagonales via des variables auxiliaires : les diagonales montantes (queen[i] - i) et descendantes (queen[i] + i) doivent aussi etre toutes différentes
  4. Un CpSolverSolutionCallback pour compter et stocker toutes les solutions
  5. Verification : le solveur trouve bien 92 solutions pour N=8
from ortools.sat.python import cp_model

class NQueensSolutionCounter(cp_model.CpSolverSolutionCallback):
    """Callback pour compter et stocker toutes les solutions N-Reines."""
    
    def __init__(self, queens):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self._queens = queens
        self._solutions = []
    
    def on_solution_callback(self):
        self._solutions.append([self.Value(q) for q in self._queens])
    
    @property
    def solution_count(self):
        return len(self._solutions)


def solve_n_queens(n: int) -> int:
    """Compte le nombre de solutions du probleme des N-Reines.
    
    Args:
        n: Taille du plateau (N x N)
    
    Returns:
        Nombre de solutions
    """
    model = cp_model.CpModel()
    
    queens = [model.NewIntVar(0, n - 1, f'queen_{i}') for i in range(n)]
    
    model.AddAllDifferent(queens)
    
    diag1 = [model.NewIntVar(-(n - 1), n - 1, f'diag1_{i}') for i in range(n)]
    for i in range(n):
        model.Add(diag1[i] == queens[i] - i)
    model.AddAllDifferent(diag1)
    
    diag2 = [model.NewIntVar(0, 2 * (n - 1), f'diag2_{i}') for i in range(n)]
    for i in range(n):
        model.Add(diag2[i] == queens[i] + i)
    model.AddAllDifferent(diag2)
    
    solver = cp_model.CpSolver()
    solver.parameters.enumerate_all_solutions = True
    callback = NQueensSolutionCounter(queens)
    solver.Solve(model, callback)
    
    return callback.solution_count


# Test
print("Test du solveur N-Reines avec OR-Tools CP-SAT")
for n in [4, 5, 6, 7, 8]:
    count = solve_n_queens(n)
    print(f"  N={n}: {count} solutions")
print(f"\nAttendus: N=4->2, N=5->10, N=6->4, N=7->40, N=8->92")
Test du solveur N-Reines avec OR-Tools CP-SAT
  N=4: 2 solutions
  N=5: 10 solutions
  N=6: 4 solutions
  N=7: 40 solutions
  N=8: 92 solutions

Attendus: N=4->2, N=5->10, N=6->4, N=7->40, N=8->92

Exercice : Carre latin avec OR-Tools CP-SAT

Enonce

En vous inspirant de l’exemple des N-Reines ci-dessus, implementez un solveur de carre latin avec OR-Tools CP-SAT.

Un carre latin de taille N est une grille NxN remplie avec les nombres de 1 a N, ou chaque nombre apparait exactement une fois dans chaque ligne et chaque colonne. C’est un problème plus simple que le Sudoku (pas de contraintes de sous-blocs).

Étapes a suivre :

  1. Créez un modèle CP-SAT avec N x N variables entieres dans le domaine {1, …, N}
  2. Ajoutez la contrainte AddAllDifferent pour chaque ligne
  3. Ajoutez la contrainte AddAllDifferent pour chaque colonne
  4. Resolver le modèle et extraire la solution

Indices :

  • La modelisation est similaire au Sudoku, mais sans les contraintes de blocs 3x3
  • Utilisez model.NewIntVar(1, n, ...) pour les variables de la grille
  • Pour verifier : un carre latin 3x3 existe toujours (par exemple, une permutation cyclique des lignes)
  • Le nombre de carres latins croit très rapidement avec N : 1, 1, 12, 576, 161280…
def solve_latin_square(n: int) -> Optional[List[List[int]]]:
    """Resout le probleme du carre latin de taille NxN avec OR-Tools CP-SAT.
    
    Un carre latin est une grille NxN remplie de nombres de 1 a N telle que
    chaque nombre apparaisse exactement une fois dans chaque ligne et chaque colonne.
    
    Args:
        n: Taille de la grille (N x N)
    
    Returns:
        La grille solution sous forme de liste de listes, ou None si pas de solution
    """
    # Exercice: Creez le modele CP-SAT
    # model = ...
    
    # Exercice: Creez les variables cells[i][j] dans {1, ..., n}
    # cells = ...
    
    # Exercice: Ajoutez la contrainte AllDifferent pour chaque ligne
    
    # Exercice: Ajoutez la contrainte AllDifferent pour chaque colonne
    
    # Exercice: Resolver et retourner la solution
    # solver = ...
    # status = ...
    
    pass


# Test
print("Test du solveur de carre latin avec OR-Tools CP-SAT")
for n in [3, 4, 5, 6, 7]:
    solution = solve_latin_square(n)
    if solution is not None:
        print(f"  N={n}: Solution trouvee")
        if n <= 5:
            for row in solution:
                print(f"    {row}")
    else:
        print(f"  N={n}: Aucune solution trouvee")
Test du solveur de carre latin avec OR-Tools CP-SAT
  N=3: Aucune solution trouvee
  N=4: Aucune solution trouvee
  N=5: Aucune solution trouvee
  N=6: Aucune solution trouvee
  N=7: Aucune solution trouvee

Exemple : Optimisation avec CP-SAT (au-dela de la satisfaction)

Jusqu’ici, CP-SAT a resolu des problemes de satisfaction : trouver UNE solution realisable (une grille de Sudoku valide, N-Reines non-conflictuelles).

La puissance distinctive de CP-SAT est l’optimisation : parmi toutes les solutions realisables, trouver celle qui maximise (ou minimise) un objectif – model.Maximize(...) / model.Minimize(...). C’est ce qui fait de CP-SAT le moteur d’optimisation combinatoire de reference (ordonnancement, tournees, packing, allocation de ressources).

Demonstration : un « carre latin a bonus » – chaque cellule (i, j) offre un reward dependant de la valeur placee (tableau reward[i][j][v]). Parmi tous les carres latins 5x5 valides, CP-SAT trouve celui qui maximise le reward total. Le solveur renvoie le statut OPTIMAL (preuve qu’aucune meilleure solution n’existe), pas seulement FEASIBLE.

from ortools.sat.python import cp_model


def solve_max_reward_latin_square(n: int = 5, reward=None, seed: int = 42):
    """Carre latin NxN maximisant le reward total (demontre model.Maximize).

    CP-SAT ne se contente pas de trouver une solution realisable : il sait
    OPTIMISER un objectif. Chaque cellule (i, j) offre un reward dependant de
    la valeur placee ; parmi toutes les grilles valides, on cherche celle qui
    MAXIMISE le reward total.
    """
    import random
    rng = random.Random(seed)
    if reward is None:
        reward = [[[rng.randint(0, 10) for _ in range(n + 1)] for _ in range(n)] for _ in range(n)]

    model = cp_model.CpModel()
    x = {}
    for i in range(n):
        for j in range(n):
            for v in range(1, n + 1):
                x[i, j, v] = model.NewBoolVar(f"x_{i}_{j}_{v}")
            model.AddExactlyOne([x[i, j, v] for v in range(1, n + 1)])
        for v in range(1, n + 1):
            model.AddExactlyOne([x[i, j, v] for j in range(n)])
    for j in range(n):
        for v in range(1, n + 1):
            model.AddExactlyOne([x[i, j, v] for i in range(n)])

    model.Maximize(
        sum(reward[i][j][v] * x[i, j, v]
            for i in range(n) for j in range(n) for v in range(1, n + 1))
    )

    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None, None, status
    grid = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for v in range(1, n + 1):
                if solver.Value(x[i, j, v]):
                    grid[i][j] = v
    return grid, solver.ObjectiveValue(), status


grid, obj, status = solve_max_reward_latin_square(n=5)
status_name = {cp_model.OPTIMAL: "OPTIMAL", cp_model.FEASIBLE: "FEASIBLE",
               cp_model.INFEASIBLE: "INFEASIBLE", cp_model.UNKNOWN: "UNKNOWN"}.get(status, str(status))
print(f"Statut: {status_name} (status={status})")
print(f"Reward optimal maximise: {obj}")
print("Grille optimale (carre latin 5x5 max-reward):")
for row in grid:
    print("  ", row)
Statut: OPTIMAL (status=CpSolverStatus.OPTIMAL)
Reward optimal maximise: 178.0
Grille optimale (carre latin 5x5 max-reward):
   [3, 2, 1, 5, 4]
   [2, 1, 5, 4, 3]
   [1, 4, 2, 3, 5]
   [5, 3, 4, 1, 2]
   [4, 5, 3, 2, 1]

Exemple miroir : Minimiser un cout pondere avec CP-SAT

Miroir de l’exemple precedent (solve_max_reward_latin_square) : meme espace de carres latins realisables, meme variables booleennes x[i,j,v], mais on minimise un cout dependant de (i, j, v) au lieu de maximiser un reward. Cela demontre model.Minimize(...) – le pendant exact de model.Maximize(...).

Piege de degenerescence (Prong-B, EPIC #3801). Une version anterieure de cet exemple minimisait la somme des valeurs sur la diagonale. C’etait un objectif degenere : chaque cellule diagonale val[i][i] appartient a 1..n, donc le minorant trivial est n (somme de n fois la valeur 1), atteignable en plaçant 1 sur chaque case diagonale – ce qu’aucune contrainte du carre latin n’interdit. Le solveur renvoyait bien OPTIMAL, mais ce statut ne prouvait rien : l’optimum etait le minorant evident, trouvable de tete sans aucune recherche. La capacite d’optimisation distinctive de CP-SAT (branch-and-bound, relaxation lineaire) y etait invisible – exactement le symptome d’un cas trop trivial pour mettre le moteur en valeur.

Avec un cout pondere aleatoire cost[i][j][v], l’optimum n’est plus devinable : la solution bon-marche cellule par cellule (prendre la valeur de cout minimal dans chaque case) viole les contraintes de carre latin. CP-SAT doit alors chercher parmi tous les carres latins realisables celui de cout total minimal. On rend cette recherche visible dans la sortie en comparant l’optimum au minorant naif (somme des couts minima par cellule, en ignorant les contraintes) : l’ecart OPTIMAL - minorant_naif > 0 prouve que les contraintes mordent et que l’optimisation est non-triviale.

Question : pourquoi le meme piege (optimum = borne triviale) guetterait-il aussi un objectif « maximiser la somme des valeurs sur la diagonale » ? (Indice : le majorant trivial serait n^2, atteint en plaçant n sur chaque case diagonale – la encore completable en carre latin.)

from ortools.sat.python import cp_model


def solve_min_cost_latin_square(n: int = 5, cost=None, seed: int = 42):
    """Carre latin NxN MINIMISANT un cout pondere (vrai miroir de Maximize).

    Miroir honnete de solve_max_reward_latin_square : meme espace de carres
    latins, meme variables booleennes x[i,j,v], mais on MINIMISE un cout
    dependant de (i,j,v) au lieu de maximiser un reward. Demontre
    model.Minimize(...), le pendant exact de model.Maximize(...).

    Pourquoi un cout PONDERE (et non la somme des valeurs sur la diagonale) :
    minimiser sum(diagonale) est un objectif DEGENERE -- chaque cellule >= 1,
    donc le minorant trivial est n, atteint en placant 1 sur chaque case
    diagonale (ce qu'aucune contrainte du carre latin n'interdit). CP-SAT
    n'y fait alors AUCUN travail d'optimisation : le statut OPTIMAL confirme
    un minorant evident. Avec un cout pondere aleatoire, l'optimum n'est plus
    devinable et CP-SAT doit chercher reellement parmi les carres latins.
    """
    import random
    rng = random.Random(seed)
    if cost is None:
        # cost[i][j][v] : cout de placer la valeur v dans la cellule (i, j)
        cost = [[[rng.randint(0, 10) for _ in range(n + 1)] for _ in range(n)] for _ in range(n)]

    model = cp_model.CpModel()
    x = {}
    for i in range(n):
        for j in range(n):
            for v in range(1, n + 1):
                x[i, j, v] = model.NewBoolVar(f"x_{i}_{j}_{v}")
            model.AddExactlyOne([x[i, j, v] for v in range(1, n + 1)])
        for v in range(1, n + 1):
            model.AddExactlyOne([x[i, j, v] for j in range(n)])
    for j in range(n):
        for v in range(1, n + 1):
            model.AddExactlyOne([x[i, j, v] for i in range(n)])

    model.Minimize(
        sum(cost[i][j][v] * x[i, j, v]
            for i in range(n) for j in range(n) for v in range(1, n + 1))
    )

    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None, None, status, None
    grid = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for v in range(1, n + 1):
                if solver.Value(x[i, j, v]):
                    grid[i][j] = v
    # Minorant naif : somme des couts minima par cellule (ignore les contraintes).
    # Si OPTIMAL > minorant naif, les contraintes de carre latin "mordent" :
    # l'optimisation est non-triviale (CP-SAT a vraiment cherche).
    naive_lower_bound = sum(min(cost[i][j][v] for v in range(1, n + 1))
                            for i in range(n) for j in range(n))
    return grid, solver.ObjectiveValue(), status, naive_lower_bound


grid, obj, status, naive_lb = solve_min_cost_latin_square(n=5)
status_name = {cp_model.OPTIMAL: "OPTIMAL", cp_model.FEASIBLE: "FEASIBLE",
               cp_model.INFEASIBLE: "INFEASIBLE", cp_model.UNKNOWN: "UNKNOWN"}.get(status, str(status))
print(f"Statut: {status_name} (status={status})")
print(f"Cout optimal minimise: {obj}")
print(f"Minorant naif (somme des couts minima par cellule, sans contraintes): {naive_lb}")
print(f"Separation : OPTIMAL ({obj}) > minorant naif ({naive_lb}) -> ecart {obj - naive_lb}")
print(f"  => les contraintes de carre latin interdisent la solution triviale ;")
print(f"     CP-SAT a reellement cherche parmi les carres latins realisables.")
print("Grille optimale (carre latin 5x5 min-cost):")
for row in grid:
    print("  ", row)
Statut: OPTIMAL (status=CpSolverStatus.OPTIMAL)
Cout optimal minimise: 73.0
Minorant naif (somme des couts minima par cellule, sans contraintes): 37
Separation : OPTIMAL (73.0) > minorant naif (37) -> ecart 36.0
  => les contraintes de carre latin interdisent la solution triviale ;
     CP-SAT a reellement cherche parmi les carres latins realisables.
Grille optimale (carre latin 5x5 min-cost):
   [2, 4, 1, 3, 5]
   [3, 2, 5, 1, 4]
   [4, 5, 3, 2, 1]
   [5, 1, 2, 4, 3]
   [1, 3, 4, 5, 2]

Interpretation : Benchmark OR-Tools CP-SAT

Les résultats du benchmark montrent que OR-Tools CP-SAT resout tous les puzzles avec des temps excellents.

Aspect Performance Analyse
Puzzles faciles (benchmark ci-dessus) Performance optimale
Puzzles difficiles (benchmark ci-dessus) Pas de degradation significative
Taux de succes 100% Solveur complet

Points cles : 1. Performance consistante : Les puzzles difficiles ne prennent pas beaucoup plus de temps que les faciles 2. Solveur complet : Tous les puzzles sont resolus 3. Simplicité : Le code est concis et lisible

Note technique : CP-SAT est specialement concu pour les problemes de satisfaction de contraintes avec des variables entieres. Sa performance excellente sur le Sudoku s’etend a de nombreux autres problemes combinatoires.

Conclusion

Ce notebook a presente l’approche declarative pour la resolution de Sudoku avec OR-Tools CP-SAT. Les points essentiels a retenir sont :

Resume des approches

Approche Type Avantages Inconvenients
Backtracking Imperatif Simple, pedagogique Lent sur puzzles difficiles
OR-Tools CP-SAT Declaratif Très rapide, API claire Dépendance externe

Recommandations

  • Apprentissage : Commencer par le backtracking pour comprendre les algorithmes
  • Production / Performance : OR-Tools CP-SAT
  • Problemes combinatoires varies : OR-Tools (portfolio de solveurs)

Au-dela du Sudoku

OR-Tools peut resoudre une grande variete de problemes : - Planification et ordonnancement - Routage et logistique - Bin packing et cutting stock - Emploi du temps et allocation de ressources

Le Sudoku est un excellent problème pedagogique car il est facile a comprendre mais assez complexe pour illustrer les concepts cles de la programmation par contraintes.

Navigation : << Python Backtracking | Index | Z3 Python >>

Retour au sommet