Résoudre un Sudoku avec la Programmation Linéaire en Nombres Entiers

Introduction

Si vous avez déjà résolu un Sudoku à la main, vous connaissez la chanson — parcourir les lignes, colonnes, blocs, noter les candidats au crayon, éliminer, recommencer. Ça marche, mais sur les grilles difficiles c'est péniblement lent et on finit toujours par faire une erreur quelque part.

Je voulais voir s'il existait une approche plus… mécanique. Et en fait, on peut décrire chaque règle du Sudoku sous forme d'équation, balancer le tout à un solveur d'optimisation, et récupérer la réponse en quelques millisecondes. Pas de devinette, pas de gomme.

La technique s'appelle la Programmation Linéaire en Nombres Entiers (PLNE, ou ILP en anglais). C'est la même mathématique qui sert à optimiser les plannings de compagnies aériennes, la logistique d'entrepôts ou la conception de puces. Sauf qu'ici on l'utilise pour résoudre un casse-tête de journal. Un peu comme sortir l'artillerie lourde pour ouvrir une noix… mais ça fonctionne admirablement.

1. Les règles du Sudoku — petit rappel

Une grille standard 9×9 obéit à trois règles :

1. Ligne : chaque ligne contient les chiffres 1 à 9 exactement une fois
2. Colonne : chaque colonne contient les chiffres 1 à 9 exactement une fois
3. Bloc : chaque sous-grille 3×3 contient les chiffres 1 à 9 exactement une fois

Certaines cases sont déjà remplies (les « données »). À vous de compléter le reste.

Ce qui est élégant, c'est que ces trois règles se traduisent quasiment mot pour mot en contraintes linéaires.

2. La formulation PLNE

Variables de décision

On introduit des variables binaires :

avec :

• $r$ = ligne (0 à 8)
• $c$ = colonne (0 à 8)
• $v$ = valeur (1 à 9)

$x_{r,c,v} = 1$ signifie « la case $(r, c)$ contient le chiffre $v$ ».

Ça fait $9 \times 9 \times 9 = 729$ variables binaires au total. Ça parait beaucoup, mais pour un solveur c'est minuscule.

Contraintes

1. Une seule valeur par case :

Dit simplement — pour chaque case, un seul des neuf créneaux est allumé.

2. Chaque chiffre une fois par ligne :

3. Chaque chiffre une fois par colonne :

4. Chaque chiffre une fois par bloc 3×3 :

5. Cases pré-remplies :

Si l'énoncé dit que la case $(r, c)$ vaut $v^*$, on fixe :

Fonction objectif

Y en a pas. Le Sudoku est un problème de faisabilité, pas d'optimisation. On cherche juste une affectation qui respecte toutes les contraintes. En pratique on met un objectif bidon :

Récapitulatif

Pour un solveur moderne, c'est trivial.

3. Implémentation Python

Voilà un solveur complet avec OR-Tools de Google (gratuit, open source). Je l'utilise régulièrement pour ce genre de problèmes et il s'en sort sans effort :

from ortools.sat.python import cp_model

def resoudre_sudoku(grille):
    """
    Résout une grille de Sudoku 9x9 par Programmation Linéaire en Nombres Entiers.
    grille : liste 9x9 d'entiers (0 = case vide)
    Retourne la grille résolue, ou None si insoluble.
    """
    modele = cp_model.CpModel()

    # Variables de décision : x[r][c][v] = 1 si la case (r,c) contient v+1
    x = [[[modele.NewBoolVar(f'x_{r}_{c}_{v}')
            for v in range(9)]
           for c in range(9)]
          for r in range(9)]

    # Contrainte 1 : une seule valeur par case
    for r in range(9):
        for c in range(9):
            modele.Add(sum(x[r][c][v] for v in range(9)) == 1)

    # Contrainte 2 : chaque chiffre une fois par ligne
    for r in range(9):
        for v in range(9):
            modele.Add(sum(x[r][c][v] for c in range(9)) == 1)

    # Contrainte 3 : chaque chiffre une fois par colonne
    for c in range(9):
        for v in range(9):
            modele.Add(sum(x[r][c][v] for r in range(9)) == 1)

    # Contrainte 4 : chaque chiffre une fois par bloc 3x3
    for bloc_r in range(3):
        for bloc_c in range(3):
            for v in range(9):
                modele.Add(sum(
                    x[r][c][v]
                    for r in range(bloc_r * 3, bloc_r * 3 + 3)
                    for c in range(bloc_c * 3, bloc_c * 3 + 3)
                ) == 1)

    # Contrainte 5 : fixer les valeurs initiales
    for r in range(9):
        for c in range(9):
            if grille[r][c] != 0:
                modele.Add(x[r][c][grille[r][c] - 1] == 1)

    # Résolution
    solveur = cp_model.CpSolver()
    statut = solveur.Solve(modele)

    if statut in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        solution = []
        for r in range(9):
            ligne = []
            for c in range(9):
                for v in range(9):
                    if solveur.Value(x[r][c][v]) == 1:
                        ligne.append(v + 1)
                        break
            solution.append(ligne)
        return solution

    return None  # pas de solution

Installation :

pip install ortools

4. Un exemple concret

Prenons une grille classique qu'on croise souvent dans les manuels (0 = case vide) :

 5 3 .  | . 7 .  | . . .
 6 . .  | 1 9 5  | . . .
 . 9 8  | . . .  | . 6 .
---------+---------+--------
 8 . .  | . 6 .  | . . 3
 4 . .  | 8 . 3  | . . 1
 7 . .  | . 2 .  | . . 6
---------+---------+--------
 . 6 .  | . . .  | 2 8 .
 . . .  | 4 1 9  | . . 5
 . . .  | . 8 .  | . 7 9

On la donne au solveur :

grille = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]

solution = resoudre_sudoku(grille)

for ligne in solution:
    print(" ".join(str(d) for d in ligne))

Résultat :

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

Résolu en moins de 10 ms. Chaque ligne, colonne et bloc 3×3 est valide.

Que se passe-t-il à l'intérieur du solveur ?

En gros :

1. Il reçoit 729 variables et 324+ contraintes
2. La propagation de contraintes réduit les possibilités — un peu comme ce qu'on fait de tête en éliminant les impossibilités
3. Quand la propagation ne suffit plus, le solveur branche : il choisit une variable indécise et teste les deux options
4. S'il tombe sur une contradiction, il revient en arrière
5. Et ainsi de suite jusqu'à trouver une solution valide (ou prouver qu'il n'y en a pas)

Les solveurs modernes ajoutent aussi l'apprentissage de clauses et les plans de coupe pour accélérer. Sur un problème de cette taille, ça ne leur prend même pas une seconde.

5. Comment se positionne le PLNE ?

Il y a pas mal de façons de résoudre un Sudoku. Voici un comparatif rapide :

Là où le PLNE se démarque vraiment, c'est l'extensibilité. On veut rajouter des règles ? On ajoute des contraintes, point. Pas besoin de réécrire l'algorithme :

• Sudoku diagonal — les chiffres 1–9 sur les deux diagonales :

# diagonale principale
for v in range(9):
    modele.Add(sum(x[i][i][v] for i in range(9)) == 1)

# anti-diagonale
for v in range(9):
    modele.Add(sum(x[i][8 - i][v] for i in range(9)) == 1)

• Sudoku Anti-Roi — les chiffres identiques ne se touchent pas en diagonale
• Killer Sudoku — des cages avec contraintes de somme
• Sudoku Thermomètre — les chiffres croissent le long d'un chemin

Quelques lignes de plus à chaque fois. Le solveur s'en fiche.

6. Au-delà du Sudoku

Le schéma de modélisation qu'on vient de voir n'a rien de spécifique aux puzzles. La même approche s'applique à des problèmes industriels concrets :

La recette :

1. Définir des variables binaires de décision
2. Exprimer les règles en égalités / inégalités linéaires
3. Éventuellement ajouter un objectif à minimiser ou maximiser
4. Laisser le solveur faire le boulot

Essayez vous-même

La théorie c'est bien, mais rien ne vaut la pratique. Le solveur interactif ci-dessous vous permet de saisir n'importe quelle grille et de la voir se résoudre directement dans le navigateur — pas de serveur, pas d'installation. Choisissez un exemple ou entrez votre propre grille.

Pour conclure

Le Sudoku est une excellente porte d'entrée vers la Programmation Linéaire en Nombres Entiers. Les règles sont intuitives, la formulation est propre (729 variables, 324 contraintes), et le solveur s'en sort en quelques millisecondes. Et surtout, le même outillage s'applique à des problèmes qui comptent vraiment dans l'industrie.

La prochaine fois que vous séchez sur une grille difficile, vous pouvez continuer à gommer… ou bien modéliser et laisser le solveur bosser.

Le code complet est ci-dessus, prêt à copier. Installez ortools et testez sur vos propres grilles.