af83

Résolution de problèmes avec la programmation par contraintes

La semaine dernière, je suis tombé sur Numberjack, package Python de modélisation pour programmer par contraintes. La programmation par contraintes consiste à décrire un modèle constitué de :

  • variables, dont le domaine de définition peut varier;
  • contraintes, qui régissent ces variables (les contraintes peuvent impliquer une ou plusieurs variables).

Une fois le modèle défini, on laisse le système trouver une solution (ie: une valeur pour chaque variable) qui satisfasse toutes les contraintes, ou pas (si le système n'a pas de solution par exemple). Ce modèle de programmation a l'intérêt d'être très générique, et accessible : il "suffit" de modéliser le problème, et le solver trouvera une solution. On peut ainsi bénéficier de solvers très performants pour une large gamme de problèmes.

Numberjack propose donc une interface de programmation par contraintes en Python à la syntaxe agréable et peut faire appel à différents solvers. Vous trouverez plusieurs exemples d'utilisation sur leur site, dont celui des huit reines (Définition Wikipedia), dont la modélisation est faite en cinq lignes de code. Pour donner un exemple (différent de ceux listés sur leur site), je vous propose donc de résoudre le problème du Sudoku. Il s'agit d'un problème simple : sur une grille de 9 x 9 cases, chaque colonne, chaque ligne et chaque "sous grille" de 3 x 3 (il y en a donc 9) possède tous les chiffres de 1 à 9.

La modélisation de ce problème est "évidente" :

  • 81 variables représentant les cases de la grille, et dont la valeur est comprise entre 1 et 9;
  • 27 contraintes (9 pour les colonnes, 9 pour les lignes, et 9 pour les sous grilles), chacune spécifiant que les valeurs des cases (de la colonne / ligne / sous grille) sont toutes différentes.

Ce qui donne, pour la déclaration des variables :

# Matrice de 9 par 9 dont les variables sont comprises entre 1 et 9
squares = Matrix(9, 9, 1, 9) 

Et pour la déclaration des contraintes :

model  = Model()
for group in squares.row + squares.col + square_groups:
  model += AllDiff(group)

La plus "grande" difficulté va donc résider à constituer "square_groups", liste de listes représentant les sous grilles. Je vais pour ce faire utiliser itertools.product, qui génère des combinaisons (ici de paires):

square_groups = []
for x_begin, y_begin in itertools.product(range(0, 9, 3), range(0, 9, 3)):
  square_groups.append([squares[(x, y)]
                        for x, y in itertools.product(range(x_begin, x_begin+3), 
                                                      range(y_begin, y_begin+3))

Et voilà, le problème est modélisé, il n'y a plus qu'à lancer le solver (ici Mistral) :

solver = model.load("Mistral")
solver.solve()

Et lire la valeur attribuée à chaque variable (et éventuellement quelques informations associées à la résolution) :

print squares
print 'Nodes:', solver.getNodes(), ' Time:', solver.getTime()

Ici la solution trouvée est triviale, mais c'est parce que nous n'avons donné de valeur initiale à aucune des variables :

[[1, 2, 3, 4, 5, 6, 7, 8, 9],
 [4, 5, 6, 7, 8, 9, 1, 2, 3],
 [7, 8, 9, 1, 2, 3, 4, 5, 6],
 [2, 6, 1, 9, 3, 4, 8, 7, 5],
 [8, 3, 4, 5, 1, 7, 6, 9, 2],
 [9, 7, 5, 2, 6, 8, 3, 1, 4],
 [3, 1, 2, 6, 7, 5, 9, 4, 8],
 [5, 4, 8, 3, 9, 1, 2, 6, 7],
 [6, 9, 7, 8, 4, 2, 5, 3, 1]]
Nodes: 45  Time: 1.1096131609e-18

Pour ajouter des valeurs initiales aux variables, il suffit de rajouter des contraintes. Avec la solution initiale suivante (0 = valeur non initialisée) :

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

on obtient la réponse :

[[9, 1, 2, 4, 7, 8, 6, 3, 5],
 [3, 8, 6, 5, 1, 9, 4, 2, 7],
 [5, 7, 4, 3, 2, 6, 1, 8, 9],
 [4, 6, 9, 8, 3, 5, 7, 1, 2],
 [1, 2, 5, 7, 9, 4, 3, 6, 8],
 [7, 3, 8, 1, 6, 2, 9, 5, 4],
 [2, 5, 3, 9, 4, 1, 8, 7, 6],
 [8, 9, 1, 6, 5, 7, 2, 4, 3],
 [6, 4, 7, 2, 8, 3, 5, 9, 1]]
Nodes: 24  Time: -8.33480420098e-19

On observera que la réponse est trouvée en moins d'étapes que pour une grille vide. C'est amusant, quand on pense que pour le cerveau humain, la solution est bien plus rapide à trouver à partir d'une grille vide. Vous trouverez le code complet à la fin de ce billet.

Le problème du Sudoku étant un problème très simple, et n'apportant pas beaucoup d'intérêt en soi, j'ai voulu résoudre le problème de l'emploi du temps en utilisant la programmation par contraintes. La problème de l'emploi du temps consiste à établir l'emploi du temps de plusieurs personnes en fonction d'objectifs et de contraintes matérielles. Par exemple, dans le milieu scolaire, il s'agit de répartir les cours de façon à ce que chaque classe ait le bon nombre d'heures de cours. Bien sûr chaque classe ne peut avoir qu'un cours à la fois, et idem pour les professeurs (et dans la réalité il faudra encore ajouter des contraintes sur les salles disponibles, les préférences horaires des professeurs…). Ce problème est modélisable en de nombreuses manières.

Après avoir essayé différentes modélisations et de solvers, je pense pouvoir dire que la programmation par contrainte n'est pas la bonne solution à ce problème. Il s'agit en effet d'un problème très complexe (de par le nombre combinaisons que peuvent générer l'ensemble des variables du modèle), et la solution est juste trop longue à trouver. Il faudra se tourner vers d'autres types de solutions, les algorithmes génétiques par exemple, mais ça c'est pour une autre fois :)

On retiendra cependant que la programmation par contraintes, sans être "the silver bullet", peut apporter des solutions à certains problèmes. Numberjack propose une interface haut niveau en Python - reposant sur des librairies performantes (codées en C ou C++) - qui rend son utilisation relativement facile. Dans le problème proposé, nous n'utilisions que des contraintes de type AllDiff, mais de nombreux autres types de contraintes sont disponibles (somme, [in]égalités, expressions logiques…).

Et comme promis, le code complet du Sudoku solver :

import itertools
import math

from Numberjack import Variable, Model, AllDiff, Sum, Matrix


def model_sudoku(SIZE, init_sol=None):
  """Returns variables (Matrix) and model asociated with sudoku problem.

  Arguments:
    - SIZE: int, size of sudoku game, must be square of integer.
    - init_sol: optional [[]], default to None, if given, positive number in this 
      array will be considered as initial solution.
  """
  SIZE_SQRT = int(math.sqrt(SIZE))
  assert SIZE_SQRT ** 2 == SIZE
  squares = Matrix(SIZE, SIZE, 1, SIZE)

  square_groups = [] # SIZE Subsquares of size "SIZE_SQRT"
  for x_begin, y_begin in itertools.product(range(0, SIZE, SIZE_SQRT),
                                            range(0, SIZE, SIZE_SQRT)):
    square_groups.append([squares[(x, y)]
                          for x, y in itertools.product(range(x_begin, x_begin+SIZE_SQRT),
                                                        range(y_begin, y_begin+SIZE_SQRT))])
  model  = Model()
  for group in squares.row + squares.col + square_groups:
    model += AllDiff(group)

  if init_sol:
    for x in range(SIZE): 
      for y in range(SIZE):
        if init_sol[x][y] > 0:
          model += (squares[(x, y)] == init_sol[x][y])

  return squares, model


def solve_sudoku(SIZE, solver, init_sol=None):
  """Given SIZE of problem and initial solution (optional), print solution.
  """
  squares, model = model_sudoku(SIZE, init_sol)
  print "Number of variables: %i" % len(model.variables)
  print "Numbder of constraints: %i" % len(model.get_exprs())
  solver = model.load(solver)
  solver.solve()
  print squares
  print 'Nodes:', solver.getNodes(), ' Time:', solver.getTime()


init_sol = [[0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 9, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 1, 0, 0],
            [0, 0, 0, 0, 3, 0, 0, 0, 2],
            [0, 2, 0, 0, 0, 0, 0, 6, 0],
            [7, 0, 0, 0, 6, 0, 0, 0, 4],
            [0, 0, 3, 0, 0, 0, 0, 0, 0],
            [8, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 4, 0, 2, 0, 0, 5, 0, 1]]
solve_sudoku(9, 'Mistral', init_sol)

blog comments powered by Disqus