• Artikel

Dieser Artikel wurde maschinell übersetzt.

Testlauf

Lösen von Sudoku-Rätseln mithilfe der MSF-Bibliothek

James McCaffrey

Laden Sie die Codebeispiele herunter

James McCaffreyEine Sudoku-Puzzle ist ein Beispiel dafür, was ein Constraint-Satisfaction-Problem (CSP) genannt wird. Eine Möglichkeit, CSPs programmgesteuert anzugehen ist die Microsoft Solver Foundation (MSF)-Bibliothek verwenden. Obwohl es höchst unwahrscheinlich, dass Sie jemals brauchen werden ist, um ein Sudoku-Rätsel als Teil Ihrer normalen Arbeit Aufgaben zu lösen, gibt es mindestens drei Gründe, warum Sie diesen Artikel zu lesen möchten. Erstens können die hier vorgestellten Techniken verwendet werden, um viele realistische Probleme zu lösen. Zweitens wird dieser Artikel Ihnen die MSF-Bibliothek und seine Fähigkeiten vorstellen. Und drittens können Sie nur feststellen, dass unterhaltsam und ist interessant programmgesteuert Sudoku-Rätsel zu lösen.

Um eine Vorstellung davon, dieser Artikel wohin zu erhalten, schauen Sie sich das Demoprogramm in Abbildung 1. Die Demo-Konsolenanwendung beginnt einrichten und Anzeigen der Daten für eine typische Sudoku-Puzzle. Anschließend programmgesteuert definiert Einschränkungen (Voraussetzungen), die gemeinsam alle Sudoku-Rätsel sind, und richtet dann die Zwänge, die speziell für das Rätsel. Anschließend wird die Demo hinter den Kulissen die MSF-Bibliothek zum Lösen des Rätsels. Die Demo endet durch die Anzeige der Lösung.

Sudoku mit Microsoft Solver Foundation
Abbildung 1-Sudoku mit Microsoft Solver Foundation

Dieser Artikel setzt voraus, Sie haben mindestens Mittelstufe Programmierkenntnisse und eine vage Vorstellung davon, was Sudoku Rätsel sind, sondern übernimmt keine weißt du alles über Einschränkung Zufriedenheit Probleme oder die MSF-Bibliothek. Das Demoprogramm ist codiert mit c#, aber Sie sollten möglicherweise die Demo .NET Sprachen ohne allzu viel Mühe umgestaltet werden kann. Der Code wird vorgestellt und es gibt es auch in den Codedownload zu diesen Artikel bei msdn.microsoft.com/magazine/msdnmag0814. Alle normalen Fehlerüberprüfung wurde entfernt, um die wichtigsten Ideen klar zu halten.

Die Microsoft Solver Foundation-Bibliothek

Die Bibliothek der MSF-Version 3.1 steht als separater Codedownload zur Verfügung. Der Speicherort des Downloads hat tendenziell im Laufe der Zeit zu bewegen, aber ich fand es am bit.ly/1vayGh1. Ich bevorzuge, 32-Bit-Bibliotheken zu verwenden, wenn Sie experimentieren, also klickte ich auf diesen Link, die mir die Option zum Ausführen oder speichern das MicrosoftSolverFoundation.msi-Installationspaket. Ich wählte die Option ausführen.

Der Installations-Assistent sagt Ihnen, dass Sie die Express Edition installieren. MSF kam ursprünglich in zwei Versionen, eine kostenlose Express-Edition und eine für Kauf-Enterprise-Edition, aber die Enterprise Edition wurde eingestellt. Die MSF-Bibliothek wird im Wesentlichen nicht mehr aktiv weiterentwickelt, aber die aktuelle 3.1 Version funktioniert für mich. Nach den schnellen aber etwas klobig Installationsvorgang abgeschlossen ist, die wichtigsten Bibliotheksdatei Microsoft.Solver.Foundation.dll wird auf dem Computer im Verzeichnis C:\Program Files (X 86) \Reference Assemblies\ kopiert­Microsoft\Framework\.NETFramework\v4.0.

Um das Demoprogramm zu erstellen, ins Leben gerufen Visual Studio I und die C#-Konsole Anwendung Programm-Vorlage ausgewählt und benannt SudokuSolver. Die Demo hat keine signifikante Microsoft .NET Framework Versionsabhängigkeiten so eine relativ neue Version von Visual Studio sollte funktionieren. Nachdem der Template-Code geladen, umbenannt im Projektmappen-Explorer Fenster ich Datei Program.cs umbenannt in SudokuProgram.cs und Visual Studio dann automatisch Klasse Programm. Die allgemeine Struktur des Demo-Programm mit einigen geringfügigen Änderungen platzsparend, präsentiert sich in Abbildung 2.

Abbildung 2 Allgemeine Programmstruktur

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

Am oberen Rand der Vorlage generiert Quellcode von Visual Studio entfernt habe ich alle unnötigen using-Anweisungen außer diejenige, die den Top-Level-System-Namespace verweist. Als nächstes einen Verweis auf die MSF-Bibliothek-DLL-Datei hinzugefügt und fügte eine using-Anweisung, die Bibliothek, um es in den Gültigkeitsbereich einzubinden verweist.

Fast alle der Arbeit erfolgt innerhalb der Main-Methode. Zwei Hilfsmethoden, AddDataConstraints und NumberSolutions, sind nur Annehmlichkeiten, den Code in Main ein wenig aufgeräumter zu halten. Nach einer vorläufigen beginnen-Meldung gründet die Demo die Sudoku-Rätsel-Daten in ein Array von Arrays Stil-Matrix.

Im Gegensatz zu vielen anderen Sprachen c# unterstützt ein wahre zweidimensionales Array, aber wie Sie sehen werden, der Array von Arrays-Ansatz ist einfacher zu bedienen. Auch wenn Sie ein erfahrener Programmierer sind, wenn Sie nicht oft mit numerische Programmierung arbeiten, können Sie nicht mit Matrix Codierungstechniken vertraut sein. Die Demo-Daten-Matrix ist vertreten Abbildung 3. Daten können von einzelnen Zelle oder von einer ganzen Zeile, aber nicht durch eine ganze Spalte zugegriffen werden. Z.B. Daten [0] [2] ist die Zelle in Zeile 0 und Spalte 2 und hat Wert 6 und Daten [1] verweist die gesamte zweite Zeile. Es gibt keine bequeme Möglichkeit, eine Spalte zugreifen. Die leeren Zellen in Abbildung 3 0-Werte tatsächlich haben, da c# automatisch Integer-Array Zellen alle Nullen initialisiert.

der Datenmatrix Problem
Abbildung 3 der Datenmatrix Problem

Einrichten des Problems

Nachdem die Problem-Data-Matrix erstellt wurde, zeigt das Demoprogramm die Werte in der Shell:

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("");
}

Hier sind die Grenzen der Schleife Hardcoded als 9. Meiner Meinung nach, vor allem mit Demo-Programme ist manchmal es besser, Dinge einfach zu halten, anstatt Sie zu allgemeineren Code zu machen. Als nächstes macht die Demo der erste Einsatz des MSF-Codes:

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];

Arbeitet mit der MSF hat Bibliothek eine etwas ungewöhnliche fühlen, weil der Code in einer Hybrid-Forschung-Entwicklung-Umgebung entwickelt wurde. Sie können die ersten beiden Zeilen als ein magisches Denken Inka­Dokumentation ein CSP-Objekt erstellen. Anstatt zu arbeiten mit einem einzelnen Objekt, da Sie wahrscheinlich gewöhnt sind, die MSF-Bibliothek tendenziell mehrere Objekte wie z. B. das Problem und Modellobjekte hier verwenden.

Das Grid-Objekt ist ein Array von Arrays Stil-Matrix, wobei jede Zelle eine Entscheidung-Objekt ist. Sie können eine Entscheidung-Objekt als eine Kapselung von Antwort vorstellen. Oder anders ausgedrückt, ein Sudoku-Rätsel zu lösen, Sie 9 x 9 = 81 ermitteln müssen, Werte. Jeder dieser Werte wird durch eine Entscheidung-Objekt dargestellt, und die Demo speichert sie in einer Matrix.

An diesem Punkt hat der Rastermatrix Entscheidung Objekte instanziiert. Die Demo instanziiert jede Zelle wie folgt:

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]);

Der Entscheidung-Konstruktor akzeptiert zwei Parameter. Die erste beschreibt den Datentyp eine Antwort. Hier ist jede Antwort eine Ganzzahl zwischen 1 und 9. Der zweite Parameter ist ein nicht-optionale Name als Zeichenfolge. Diese Namen müssen eindeutig sein, damit die Demo die Namen "grid00", "grid01" und so weiter zu jedem der 81 Entscheidung Objekte programmgesteuert weist. Nachdem die Entscheidung-Objekte instanziiert wurden, müssen sie auf das Modell-Objekt hinzugefügt werden. Die AddDecisions-Methode akzeptiert ein einzelnes Entscheidung-Objekt oder ein Array von Objekten der Entscheidung, damit die Demo die neun Zeilen der Raster-Matrix übergibt. Eine Alternative wäre, zwei nested Loops, wie folgt zu verwenden:

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

Generische Einschränkungen hinzufügen

Es gibt drei Gruppen von generische Einschränkungen, die gemeinsam alle Sudoku-Rätsel sind. Zuerst müssen die Werte in jeder Zeile alle unterscheiden. Zweitens müssen die Werte in jeder Spalte alle unterschiedlich sein. Und drittens die Werte in jedem 3 x 3-Sub-Cube müssen alle unterschiedlich sein. Es ist einfach, kümmert sich um die erste Reihe von Einschränkungen:

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

Die AddConstraint-Methode akzeptiert ein Einschränkungsname, gefolgt von einer Einschränkung. Hier sind die Namen "rowConstraint0", "rowConstraint1" und so weiter. Die Demo benutzt die AllDifferent-Methode erstellen Sie eine Einschränkung. In Worten für jede der neun Zeilen, Hinzufügen einer Einschränkung, dass alle Werte in der Zeile anders sein müssen.

Hinzufügen der Spalteneinschränkung der generischen erfordert ein wenig mehr Aufwand:

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]);
}

Da eine ganze Spalte nicht direkt zugegriffen werden kann, funktioniert die Demo separat für jede Spalte. Für Spalte 0, zum erste Mal durch die zwei innere nested Loops setzt die Einschränkung mit dem Namen "colConstraint001" als Raster [0] [0]! = Grid [1] [0]. Die zweite Iteration setzt "colConstraint002" als Raster [0] [0]! = Grid [2] [0]. Zusammenfassend möchte ich sagen, akzeptiert die AllDifferent-Methode, eine Reihe von Entscheidung Objekten als Array und hinter den Kulissen explizite Ungleichheiten generiert. In Situationen, wo Ihre Entscheidung-Objekte in einem Array (wie die Spaltenwerte) nicht sind, müssen Sie explizit die Ungleichheiten generieren.

Bei weitem ist der schwierigste Teil des Demo-Programm einrichten die Einschränkungen, die angeben, dass alle Werte in jedem der neun 3 x 3 Sub-Cubes unterschiedlich sein müssen. Dass Code präsentiert werden Abbildung 4. Geduld mit mir — der Code ist nicht annähernd so komplex wie es scheint.

Abbildung 4 Einrichten der Sub-Cube-Einschränkungen

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

Betrachten Sie den Sub-Cube in der unteren linken Ecke des Abbildung 3. Die notwendigen Einschränkungen für diese Sub-Cube sind:

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

Es gibt 8 + 7 + 6 +... + 1 = 36 Einschränkungen für diese Sub-Cube, und so gibt es 9 * 36 = 324 insgesamt Ungleichheiten bei den neun Sub-Cube-Einschränkungen. Nun, es wäre möglich, jede Liste mit Copy & Paste und etwas Geduld, aber ein programmatischen Ansatz ist schneller.

Im Code richten zwei äussersten eine obere linke Ecke der einzelnen Sub-Cubes. In die vier innersten Schleifen Zellen werden dargestellt als Raster [a] [b]! = Grid [x] [y]. Schaut man nur auf die Indizes in dem Beispiel und Bild, die gewöhnliche Ganzzahlen sind, erhalten Sie:

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

Beachten Sie, dass in jedem Fall eine Ungleichheit-Einschränkung beim Ab < XY. Innersten vier Schleifen a, b durchlaufen, X und y, alle möglichen Paare der Indizes und die wenn-dann-Bedingung zu generieren erstellt eine Einschränkung auf Raster [a] [b] und Grid [x] [y] erst Ab < XY.

Hinzufügen von Problem-spezifische Einschränkungen

Nachdem die generischen Einschränkungen erstellt und dem Modell hinzugefügt wurden, fügt das Demoprogramm die Einschränkungen, die das spezifische Sudoku-Rätsel zu definieren. Das Demo-Puzzle hat 27 feste Werte, so dass du rohe Gewalt gebrauchen wie folgt:

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

Es ist nichts falsch mit einem brute-Force-Ansatz, aber da die Daten bereits in eine Matrix platziert wurde, es ist einfach, die Übertragung der Werte, die mit einem Programm definierten Helper-Methodenaufruf wie folgt:

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]);
      }
    }
  }
}

Beachten Sie die seltsame Kopplung zwischen Modell und Entscheidung. Bibliothek-Code geschrieben von Entwicklern für Entwickler würde wahrscheinlich die Entscheidung (Antwort)-Objekte nach dem Vorbild der model.grid[r][c verwiesen haben]. Der ungewöhnliche Stil der MSF-Bibliothek dauerte etwa drei Beispiele, um bequem mit.

Das Rätsel zu lösen

Alles ist vorhanden kann das Demoprogramm lösen des Rätsels mit diesem Code:

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

Die NumberSolutions-Methode ist ein Programm definierten Helfer, der aufgerufen wird, um zu prüfen ob es gibt 0 (null) Lösungen (was bedeutet, dass widersprüchliche Einschränkungen irgendwie definiert wurden) oder mehr als eine Lösung:

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

Die Ärzte ohne Grenzen zu lösen-Methode macht genau das, platzieren die tatsächlichen Antworten in die Entscheidung-Objekte, die im Modell-Objekt sind, die durch einen Verweis auf das SolverContext-Objekt verknüpft ist. Als Nebeneffekt hat das Solution-Objekt ein Qualität-Feld, das einen von acht Werten, darunter durchführbar und Infeasible sein kann. Die Lösung GetNext-Methode ändert das Qualität-Feld jedoch keinen expliziten Wert zurück. Don' t mir die Schuld für das MSF-Design.

Die Sudoku-Demo schließt mit der Darstellung der Antworten, die in der Entscheidung-Objekten in der Rastermatrix gespeichert:

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

GetDouble-Methode extrahiert den Antwort-Wert aus dem Beschluss-Objekt. Daran erinnern Sie, dass Antworten definiert wurden, um ganze Zahlen im Bereich von 1 bis 9 sein. Allerdings gibt es keine GetInteger-Methode, so dass Antwort Werte implizit Doppelzimmer Typ umgewandelt werden. Weil sie alle am Ende mit Punkt Null ist, wenn angezeigt sie erscheinen als ganze Zahlen, obwohl sie Typ double sind.

Zusammenfassung

Die besondere Art der CSP, die in diesem Artikel beschriebenen ist wirklich ein kombinatorisches Optimierungsproblem. Das heißt, ist das Ziel, die Kombination der Werte zu finden, die die wenigsten Einschränkung Fehler aufweist. Die hier dargestellten Informationen können Sie die MSF-Bibliothek benutzen, um viele praktische kombinatorische Optimierungsprobleme zu lösen, die Sie möglicherweise stoßen sollte.

Ich habe ein Geständnis. Der Freund meiner Schwester machte mich mit Sudoku, auf einen Familienausflug nach Palm Springs vor ein paar Jahren. Er schlägt mich konsequent, wenn wir mal auf Sudoku oder Kreuzworträtsel oder sonst was konkurrieren. Er weiß nicht, dass es möglich ist, alle Sudoku-Rätsel mit diesem Code zu lösen. Ich freue mich auf unsere nächsten Familienausflug. Ich muss mein Laptop.

Dr. James McCaffrey arbeitet für Microsoft Research in Redmond, Washington Er arbeitete an verschiedenen Microsoft-Produkten, einschließlich Internet Explorer und Bing. Sie erreichen ihn am jammc@microsoft.com.

Unser Dank gilt dem folgenden technischen Experten für die Durchsicht dieses Artikels: Kirk Olynyk (Microsoft Research)