Partager via

  • Article

Cet article a fait l'objet d'une traduction automatique.

Série de tests

Résoudre des casse-têtes Sudoku à l'aide de la bibliothèque MSF

James McCaffrey

Télécharger l'exemple de code

James McCaffreyUn puzzle de Sudoku est un exemple de ce qu'on appelle un problème de satisfaction de contraintes (CSP). S'attaquer à l'EFPC par programmation consiste à utiliser la bibliothèque Microsoft Solver Foundation (MSF). Bien qu'il est peu probable que vous aurez besoin résoudre un puzzle de Sudoku dans le cadre de vos responsabilités de travail normal, il y a au moins trois raisons pourquoi vous pouvez lire cet article. Tout d'abord, les techniques présentées ici peuvent servir à résoudre de nombreux problèmes réalistes. En second lieu, cet article vous présentera à la bibliothèque MSF et ses capacités. Et Troisièmement, vous pourriez juste trouver que résoudre des puzzles de Sudoku par programme est intéressant et divertissant.

Pour avoir une idée d'où va cet article, jetez un oeil sur le programme de démonstration en Figure 1. L'application de console démo commence par la mise en place et afficher les données d'un puzzle de Sudoku typique. Ensuite, il définit par programme les contraintes (conditions requises) qui sont communes à tous les puzzles de Sudoku et configure les contraintes de données spécifiques à l'énigme. Puis, dans les coulisses, la démo utilise la bibliothèque MSF à résoudre l'énigme. La démo conclut en affichant la solution.

Sudoku en utilisant la Microsoft Solver Foundation
Figure 1 Sudoku en utilisant la Microsoft Solver Foundation

Cet article suppose que vous avez des compétences en programmation au moins au niveau intermédiaire et une vague idée de ce que Sudoku puzzles sont, mais n'assume pas vous savez quelque chose sur les problèmes de satisfaction de contrainte ou la bibliothèque MSF. Le programme de démonstration est codé à l'aide de c#, mais vous devriez être capable de refactoriser la démo d'autres langages .NET sans trop d'ennui. Tout le code est présenté ici et il est également disponible dans le téléchargement de code qui accompagne cet article à msdn.microsoft.com/magazine/msdnmag0814. Vérification des erreurs normales tout a été supprimé pour garder les idées claires.

La bibliothèque de Microsoft Solver Foundation

La bibliothèque de la version 3.1 de MSF est disponible en téléchargement code séparé. L'emplacement du téléchargement a eu tendance à déplacer au fil du temps, mais je l'ai trouvé à bit.ly/1vayGh1. Je préfère utiliser les bibliothèques 32 bits lorsque des expériences donc j'ai cliqué sur ce lien, qui m'a donné la possibilité d'exécuter ou d'enregistrer le package d'installation de MicrosoftSolverFoundation.msi. J'ai sélectionné l'option Exécuter.

L'Assistant d'installation vous indique que vous installez l'édition Express. MSF provient à l'origine en deux versions, une édition Express gratuite et une version d'entreprises pour l'achat, mais la version enterprise edition a été abandonnée. La bibliothèque MSF est essentiellement n'est plus activement développée, mais la dernière version 3.1 fonctionne très bien pour moi. Après la rapide mais un peu maladroit installation processus terminé, le fichier de bibliothèque clé Microsoft.Solver.Foundation.dll est copié sur votre ordinateur dans le répertoire C:\Program Files (x 86) \Reference Assemblies\­Microsoft\Framework\.NETFramework\v4.0.

Pour créer le programme de démonstration, j'ai lancé Visual Studio et sélectionné le modèle de programme d'application de console c# et nommé SudokuSolver. La démo n'a aucune dépendance de version Microsoft .NET Framework significative pour toutes les versions relativement récentes de Visual Studio devraient fonctionner. Une fois le code du modèle est chargé, dans l'Explorateur de solutions fenêtre j'ai renommé le fichier Program.cs à SudokuProgram.cs et Visual Studio puis renommé automatiquement class Program. La structure générale du programme de démonstration, avec quelques modifications mineures pour économiser l'espace, est présentée en Figure 2.

Figure 2 Structure globale du programme

using System;
using Microsoft.SolverFoundation.Services;
namespace SudokuSolver
{
  class SudokuProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin MS Solver Foundation Sudoku demo");
      Console.WriteLine("The problem is: ");
      int[][] data = new int[9][];
      data[0] = new int[] { 0, 0, 6,
        2, 0, 0,
        0, 8, 0 };
      data[1] = new int[] { 0, 0, 8,
        9, 7, 0,
        0, 0, 0 };
      data[2] = new int[] 
      { 0, 0, 4,
        8, 1, 0,
        5, 0, 0 };
      data[3] = new int[] 
      { 0, 0, 0,
        0, 6, 0,
        0, 0, 2 };
      data[4] = new int[] 
      { 0, 7, 0,
        0, 0, 0,
        0, 3, 0 };
      data[5] = new int[] 
      { 6, 0, 0,
        0, 5, 0,
        0, 0, 0 };
      data[6] = new int[] 
      { 0, 0, 2,
        0, 4, 7,
        1, 0, 0 };
      data[7] = new int[] 
      { 0, 0, 3,
        0, 2, 8,
        4, 0, 0 };
      data[8] = new int[] 
     { 0, 5, 0,
       0, 0, 1,
       2, 0, 0 };
      // all program logic here
      Console.WriteLine("End Solver Foundation Sudoku demo");
      Console.ReadLine();
    }
    static void AddDataConstraints(int[][] data,
      Model model, Decision[][] grid) { . . }
    static int NumberSolutions(SolverContext problem) { . . }
  }
} // ns

En haut du code source généré par modèle Visual Studio , j'ai enlevé tous les inutiles à l'aide de déclarations à l'exception de celui qui fait référence à l'espace de noms System niveau supérieur. Ensuite, j'ai ajouté une référence au fichier DLL bibliothèque MSF et ensuite ajouté une aide instruction qui fait référence à la bibliothèque pour l'aligner sur le champ d'application.

Presque tout le travail est effectué à l'intérieur de la méthode Main. Deux méthodes d'assistance, AddDataConstraints et NumberSolutions, sont les convenances justes de conserver le code à l'intérieur de la Main un peu plus rangé. Après un lancer-message préliminaire, la démo met en place les données de puzzle de Sudoku dans une matrice de baie-des-baies de style.

Contrairement à nombreux langages, c# prend en charge un vrai tableau à deux dimensions, mais comme vous allez le voir, l'approche de la baie-des-baies est plus facile de travailler avec. Même si vous êtes un programmeur expérimenté, si vous ne travaillez souvent avec la programmation numérique, vous ne serez peut-être pas familier avec les techniques de codage de matrice. La matrice de données démo est représentée dans Figure 3. Données peuvent être accédées par des cellules individuelles, ou par une ligne entière, mais pas par une colonne entière. Par exemple, data [0] [2] est la cellule à la ligne 0 et la colonne 2 et a la valeur 6, et les données [1] fait référence à la deuxième ligne. Il n'y a aucun moyen pratique d'accéder à une colonne. Les cellules de l'essai à blanc en Figure 3 ont en fait des valeurs 0 parce que c# initialise automatiquement des cellules de tableau d'entiers à nulle.

la matrice de données du problème
Figure 3 la matrice de données du problème

Mise en place du problème

Après avoir créé la matrice de données du problème, le programme de démonstration affiche les valeurs de l'interpréteur de commandes :

for (int r = 0; r < 9; ++r)  {
  for (int c = 0; c < 9; ++c)  {
    if (data[r][c] == 0)
      Console.Write(" _");
    else
      Console.Write(" " + data[r][c]);
  }
  Console.WriteLine("");
}

Ici, les limites de la boucle sont codés en dur dans le 9. À mon avis, en particulier avec les programmes de démonstration, il est parfois préférable de garder les choses simples plutôt que de rendre le code plus général. Ensuite, la démo fait la première utilisation du code MSF :

SolverContext problem = SolverContext.GetContext();
Model model = problem.CreateModel();
Decision[][] grid = new Decision[9][];
for (int r = 0; r < 9; ++r)
  grid[r] = new Decision[9];

Travailler avec MSF bibliothèque a une sensation un peu particulier parce que le code a été développé dans un environnement de recherche-développement hybride. Vous pouvez considérer les deux premières lignes comme une magie Inca­tation pour créer un objet CSP. Plutôt que de travailler avec un objet unique, comme vous êtes probablement habitué à, la bibliothèque MSF a tendance à utiliser plusieurs objets tels que le problème et les objets du modèle ici.

L'objet grid est une matrice de baie-des-baies de style où chaque cellule est un objet de la décision. Vous pouvez considérer d'un objet de la décision comme une encapsulation d'une réponse. Ou autrement dit, pour résoudre un puzzle de Sudoku, vous devez déterminer 9 x 9 = 81 valeurs. Chacune de ces valeurs est représentée par un objet de la décision et la démo stocke dans une matrice.

À ce stade, la matrice de la grille a uninstantiated des objets de la décision. La démo instancie chaque cellule comme suit :

for (int r = 0; r < 9; ++r)
  for (int c = 0; c < 9; ++c)
    grid[r][c] = new Decision(Domain.IntegerRange(1, 9),
      "grid" + r + c);
for (int r = 0; r < 9; ++r)
  model.AddDecisions(grid[r]);

Le constructeur de décision accepte deux paramètres. Le premier décrit le type de données de réponse. Ici, chaque réponse est un nombre entier compris entre 1 et 9. Le deuxième paramètre est un nom non optionnel sous forme de chaîne. Ces noms doivent être uniques, donc la démo par programme affecte les noms de "grid00," "grid01" et ainsi de suite pour chacun des objets décision 81. Après que les objets de la décision ont été instanciés, ils s'ajoutent à l'objet de modèle. La méthode AddDecisions peut accepter un seul objet de décision ou d'un tableau d'objets de la décision, donc la démo passe les neuf lignes de la matrice de la grille. Une alternative serait d'utiliser deux boucles imbriquées, comme ceci :

for (int r = 0; r < 9; ++r)
    for (int c = 0; c < 9; ++c)
      model.AddDecisions(grid[r][c]);

Ajout de contraintes génériques

Il y a trois ensembles de contraintes génériques qui sont communes à tous les puzzles de Sudoku. Tout d'abord, les valeurs de chaque ligne doivent toutes être différentes. Deuxièmement, les valeurs de chaque colonne doivent tous être différents. Et Troisièmement, les valeurs dans chaque cube sous 3 x 3 doivent tous être différents. Il est facile de prendre soin de la première série de contraintes :

Console.WriteLine("Creating generic row constraints");
for (int r = 0; r < 9; ++r)
  model.AddConstraint("rowConstraint" + r, 
  Model.AllDifferent(grid[r]));

La méthode AddConstraint accepte un nom de contrainte suivi d'une contrainte. Ici, les noms sont « rowConstraint0, » « rowConstraint1 » et ainsi de suite. La démonstration utilise la méthode TousDifférents pour créer une contrainte. Dans les mots, pour chacune des neuf lignes, ajouter une contrainte que toutes les valeurs de la ligne doivent être différents.

Ajout de la contrainte de colonne générique nécessite un peu plus d'efforts :

Console.WriteLine("Creating generic column constraints");
for (int c = 0; c < 9; ++c)
{
  for (int first = 0; first < 8; ++first)
    for (int second = first + 1; second < 9; ++second)
      model.AddConstraint("colConstraint" + c + first + second,
        grid[first][c] != grid[second][c]);
}

Parce qu'une colonne entière ne sont pas directement accessibles, la démo fonctionne sur chaque colonne séparément. Pour la colonne 0, la première fois dans les deux boucles imbriquées internes définit la contrainte nommée « colConstraint001 » comme une grille [0] [0]! = grille [1] [0]. La deuxième itération définit « colConstraint002 » comme une grille [0] [0]! = grille [2] [0]. En résumé, la méthode TousDifférents accepte qu'un ensemble d'objets sous forme de tableau et dans les coulisses de la décision génère des inégalités explicites. Dans les situations où vos objets de décision ne sont pas dans un tableau (comme dans les valeurs de colonne), vous devez explicitement générer les inégalités.

De loin la partie la plus délicate du programme démo met en place les contraintes qui spécifient que toutes les valeurs de chacun des cubes sous neuf 3 x 3 doivent être différents. Que le code est présentée en Figure 4. Ours avec moi — le code n'est pas presque aussi complex, tel qu'il apparaît.

Figure 4 mise en place du Cube sous contraintes

Console.WriteLine("Creating generic sub-cube constraints");
for (int r = 0; r < 9; r += 3) {
  for (int c = 0; c < 9; c += 3) {
    for (int a = r; a < r + 3; ++a) {
      for (int b = c; b < c + 3; ++b) {
        for (int x = r; x < r + 3; ++x) {
          for (int y = c; y < c + 3; ++y) {
            if ((x == a && y > b) || (x > a))
            {
              model.AddConstraint("cubeConstraint" + a + b + x + y,
                grid[a][b] != grid[x][y]);
            }
          } // y
        } // x
      } // b
    } // a
  } // c
} // r

Considérez le cube subsidiaire dans le coin en bas à gauche de Figure 3. Les contraintes nécessaires pour ce cube secondaires sont :

grid[6][0] != grid[6][1]
grid[6][0] != grid[6][2]
grid[6][0] != grid[7][0]
...
grid[8][1] != grid[8][2]

Il y a 8 + 7 + 6 +... + 1 = 36 contraintes pour ce cube sous, et donc il y a 9 * 36 = 324 total des inégalités pour les contraintes de cube sous neuf. Maintenant, il serait possible d'énumérer chacun d'utiliser copier-coller et peu de patience, mais une approche programmatique est plus rapide.

Dans le code, les deux boucles externes établissent un coin supérieur gauche de chaque cube subsidiaire. Dans les quatre boucles plus intimes, les cellules sont représentés comme grille [a] [b]! = grille [x] [y]. Si vous regardez juste les indices dans l'exemple et l'image, qui sont tout à fait ordinaire entiers, vous obtenez :

60 and 61
60 and 62
...
81 and 82

Notez que dans chaque cas, il y a une contrainte de l'inégalité lorsqu'ab < XY. La plus profonde quatre boucles itérer sur a, b, x et y pour générer toutes les paires possibles d'indices et de la condition si-alors crée une contrainte sur la grille [a] [b] et grille [x] [y] uniquement lorsque ab < XY.

Ajout de contraintes spécifiques au problème

Une fois que les contraintes génériques ont été créés et ajoutés au modèle, le programme de démonstration ajoute les contraintes qui définissent le puzzle de Sudoku spécifique. Le puzzle de la démo a 27 valeurs fixes, donc vous pourriez utiliser la force brutale, comme suit :

model.AddConstraint("v02", grid[0][2] == 6);
model.AddConstraint("v03", grid[0][3] == 2);
...
model.AddConstraint("v86", grid[8][6] == 2);

Il n'y a rien de mal à une approche de la force brute, mais parce que les données a déjà été placées dans une matrice, il est facile de transférer les valeurs à l'aide d'un appel de méthode d'assistance programme-défini comme ceci :

AddDataConstraints(data, model, grid);
where the helper is defined as:
static void AddDataConstraints(int[][] data, Model model, 
  Decision[][] grid)
{
  for (int r = 0; r < 9; ++r) {
    for (int c = 0; c < 9; ++c) {
      if (data[r][c] != 0) {
        model.AddConstraint("v" + r + c,
          grid[r][c] == data[r][c]);
      }
    }
  }
}

Remarquez l'étrange attelage entre les objets de modèle et de la décision. Code de la bibliothèque écrit par les développeurs pour les développeurs serait probablement ont référencé les objets de la décision (réponse) le long des lignes de model.grid[r][c]. Le style hors du commun de la bibliothèque MSF m'a pris environ trois exemples à l'aise avec elle.

Résoudre le casse-tête

Le programme de démonstration, avec tout en place, peut résoudre le puzzle avec ce code :

Console.WriteLine("Solving. . . " );
int numSolutions = NumberSolutions(problem);
Console.WriteLine("There is/are " + 
  numSolutions + " Solution(s)");
Solution solution = problem.Solve();

La méthode NumberSolutions est un Assistant défini par le programme qui est appelé pour vérifier si il n'y a nulle solutions (ce qui signifie des contraintes contradictoires ont été définis en quelque sorte) ou plusieurs solutions :

static int NumberSolutions(SolverContext problem)
{
  int ct = 0;
  Solution soln = problem.Solve();
  while (soln.Quality == SolverQuality.Feasible) {
    ++ct;
    soln.GetNext();
  }
  return ct;
}

La méthode de résoudre de MSF fait justement cela, plaçant les réponses réelles dans les objets de la décision, qui se trouvent dans l'objet de modèle, qui est lié par la référence à l'objet SolverContext. Comme effet secondaire, l'objet Solution possède un champ de qualité qui peut être une des huit valeurs, y compris faisable et Infeasible. La méthode de Solution GetNext ne renvoie pas une valeur explicite mais modifie-t-il le domaine de la qualité. Don' t blame me pour la conception MSF.

La démo de Sudoku conclut en affichant les réponses stockées dans les objets à l'intérieur de la matrice de la grille de décision :

for (int r = 0; r < 9; ++r) {
    for (int c = 0; c < 9; ++c) {
      double v = grid[r][c].GetDouble();
      Console.Write(" " + v);
    }
    Console.WriteLine("");
  }
  Console.WriteLine("End Solver Foundation Sudoku demo");
  Console.ReadLine();
} // Main

La méthode GetDouble extrait la valeur de la réponse de l'objet de la décision. Rappelons que les réponses ont été définies pour être entiers dans la plage 1 à 9. Cependant, il n'y a aucune méthode GetInteger donc implicitement, les valeurs de réponse sont converties en type double. Parce qu'ils sont tous terminent avec zéro point, lorsque affiché, ils apparaissent comme des entiers même s'ils sont de type double.

Synthèse

Le type particulier de CSP décrit dans cet article est vraiment un problème d'optimisation combinatoire. Autrement dit, le but est de trouver la combinaison de valeurs qui a le moins d'erreurs de contrainte. L'information présentée ici devrait vous permettre d'utiliser la bibliothèque MSF à résoudre de nombreux problèmes d'optimisation combinatoire pratique vous pourriez rencontrer.

J'ai une confession. Petit ami de ma sœur m'a présenté à Sudoku sur un voyage en famille à Palm Springs il y a quelques années. Il me bat régulièrement chaque fois que nous sommes en concurrence pour le moment sur Sudoku, mots croisés ou quoi que ce soit d'autre. Il ne sait pas qu'il est possible de résoudre n'importe quel puzzle Sudoku avec ce code. Je suis impatient pour notre prochain voyage en famille. Je vais avoir mon ordinateur portable.

Dr. James McCaffrey travaille pour Microsoft Research à Redmond, Washington Il a travaillé sur plusieurs produits Microsoft, y compris Internet Explorer et Bing. Le contacter au jammc@microsoft.com.

Merci aux experts techniques suivants d'avoir relu cet article : Kirk Olynyk (Microsoft Research)