本文章是由機器翻譯。

測試回合

使用 MSF 程式庫破解數獨難題

James McCaffrey

下載代碼示例

數獨謎題是所謂的約束滿足問題 (CSP) 的一個例子。 以程式設計方式解決 Csp 一種方法是使用 Microsoft 規劃求解基金會 (MSF) 圖書館。 雖然它是極不可能你需要解決數獨謎題作為你正常的工作職責的一部分，有至少三個理由為什麼你可能會想要讀這篇文章。 第一，這裡介紹的技術可以用於解決很多現實問題。 第二，這篇文章將介紹你到無國界醫生組織庫，它的功能。 第三，你可能發現以程式設計方式解決數獨謎題是有趣和引人入勝。

要得到一個何方這篇文章的想法，看看該演示程式中圖 1。 演示主控台應用程式的設置和顯示典型的數獨謎題的資料開始。 下一步，它通過程式設計方式定義約束 （所需條件） 所共有的所有的數獨謎題，然後設置特定于拼圖資料約束。 然後，在幕後，演示使用的無國界醫生組織庫來解決這一難題。 演示結束通過顯示解決方案。

使用規劃求解 Microsoft 基礎圖 1 數獨

這篇文章假設你有至少中級程式設計技能和一個模糊的想法的數獨遊戲是什麼，但不是承擔你知道任何有關約束滿足問題或無國界醫生組織庫。 該演示程式使用 C# 編寫，但你應該能夠重構的演示給其他.NET 語言沒有太多的麻煩。 所有代碼都在這裡都提出，也是可用的代碼下載中伴隨著這篇文章在 msdn.microsoft.com/magazine/msdnmag0814。 已刪除所有正常的錯誤檢查，保持清晰的主要思想。

規劃求解微軟基礎庫

無國界醫生組織 3.1 版庫是可作為一個單獨的代碼下載。 下載位置已傾向于隨著時間的推移左右移動，但我發現它在 bit.ly/1vayGh1。 我更願意使用 32 位的庫，在實驗過程中所以我點擊該連結，給了我選擇運行或保存 MicrosoftSolverFoundation.msi 的安裝包。 運行的選擇。

安裝精靈會告訴你你安裝速成版。 無國界醫生組織最初進來了兩個版本，免費的速成版和為購買企業版上，但已停產的企業版。 無國界醫生組織圖書館基本上不再正在積極地開發，但當前的 3.1 版本對我的好作品。 後迅速但有點笨重安裝過程完成後，金鑰庫檔 Microsoft.Solver.Foundation.dll 複製到您的機器在目錄 C:\Program 檔 (86) \Reference Assemblies\­Microsoft\Framework\。NETFramework\v4.0。

若要創建該演示程式，我發起Visual Studio和選定的 C# 主控台應用程式範本，將它命名為 SudokuSolver。 演示有沒有重大的 Microsoft.NET 框架版本依賴關係，因此，任何相對較新版本的Visual Studio應該工作。 範本代碼載入後，在解決方案資源管理器視窗我重 Program.cs 檔命名為 SudokuProgram.cs 和Visual Studio然後自動重命名類的程式。 整體結構的演示程式，與幾個小編輯為了節省空間，提出了圖 2。

圖 2 程式的整體結構

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

Visual Studio範本生成原始程式碼的頂部，我刪除所有不必要的使用只有一個頂級的系統命名空間引用的語句。 接下來，我添加了一個引用到的無國界醫生組織庫 DLL 檔，然後使用增加參考庫把它帶到範圍的聲明。

幾乎所有的工作都被執行內部方法 Main。 兩個説明器方法，AddDataConstraints 和 NumberSolutions，是公正的便利，以使代碼保持在 Main 內有點更整齊些。 初步開始的消息後，演示在一個陣列的陣列樣式矩陣設置數獨謎題資料。

很多與語言不同，C# 支援真正的二維陣列，但是你會看到，陣列的陣列的方法是與工作更容易。 即使你是一個有經驗的程式師，如果你不經常工作與數控程式設計，您可能不熟悉矩陣編碼技術。 演示資料矩陣代表圖 3。 可以訪問資料，通過單個儲存格，或一整行，而不是由一整列。 例如，[0] [2] 的資料是 0 行和第 2 列的儲存格，值 6，和資料 [1] 引用整個第二行。 那裡是沒有方便的方式來訪問某一列。 中的空白儲存格圖 3 其實有 0 值，因為 C# 自動初始化為全 0 的整數陣列儲存格。

圖 3 問題資料矩陣

問題的設置

已創建的問題資料矩陣後，該演示程式向 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("");
}

在這裡，迴圈限制是硬編碼為 9。 在我看來，尤其是與演示的程式，有時它是更好地保持事情簡單，而不是使代碼更一般。 下一步，演示使無國界醫生組織代碼的第一次使用：

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

圖書館與無國界醫生組織工作有一個有點不尋常的感覺，因為代碼開發的混合動力研究開發環境。 您可以看作一種神奇的前兩行印加­張力來創建一個 CSP 物件。 而不是使用一個單一的物件，正如你可能習慣，MSF 圖書館傾向于使用多個問題的物件和模型物件在這裡。

網格物件是每個儲存格在哪裡決定物件陣列的陣列樣式矩陣。 你可以認為決定物件的作為答案的封裝。 或把另一種方法，來解決數獨謎題，你需要確定 9 × 9 = 81 的值。 每個這些值都是由決定的物件和演示將它們存儲在一個矩陣中。

在這一點上，網格矩陣具有未決定物件。 演示具現化每個儲存格就像這樣：

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

決定建構函式接受兩個參數。 第一次描述資料類型的一個答案。 在這裡，每個答案是 1 和 9 之間的一個整數。 第二個參數作為一個字串是一個非可選的名稱。 這些名稱必須是唯一的所以演示以程式設計方式分配名稱"grid00""grid01"等對每個 81 的決策物件。 決策物件已具現化後，必須將它們添加到模型物件。 AddDecisions 方法可以接受單個決策物件或物件的陣列的決定，所以演示通過網格矩陣的九行。 替代方法是使用兩個嵌套的迴圈，像這樣：

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

添加泛型約束

有三套的都是共同的所有數獨謎題的泛型約束。 第一中的每一行的值都必須不同。 第二，每個列中的值都必須不同。 第三，在每個 3 × 3 子多維資料集中的值都必須不同。 對約束條件的第一套的照顧是很容易：

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

AddConstraint 方法接受約束的名稱後, 跟一個約束。 在這裡的名稱是"rowConstraint0""rowConstraint1"，等等。 演示使用 AllDifferent 方法來創建一個約束。 換句話說，對於每個九行，添加約束行中的所有值必須都是不同。

添加泛型列約束要求多一點點的努力：

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

因為一整列不能被直接存取，演示單獨工作的每個列。 為 0 的列，第一次通過了兩個內部嵌套迴圈設置名為"colConstraint001"作為網格 [0] [0] 的約束! = 網格 [1] [0]。 第二次反覆運算設置"colConstraint002"作為網格 [0] [0]! = 網格 [2] [0]。 總結一下，AllDifferent 方法接受一套的決策物件作為一個陣列並在幕後生成顯式的不平等現象。 在哪裡你的決定並不是物件陣列 （如列的值） 中的情況下，您必須顯式生成方面的不平等。

到目前為止的演示程式中最棘手的部分設置指定每年的 9 個 3 × 3 子多維資料集的所有值必須都是不同的約束。 代碼提出了一種在圖 4。 和我一起承擔 — — 代碼不近看起來的那樣複雜。

圖 4 設置子多維資料集中的約束

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

考慮的子多維資料集在左下角的圖 3。 此子多維資料集中的必要約束條件是：

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

有 8 + 7 + 6 +......+ 1 = 36 此子多維資料集中的約束，所以有 9 * 36 = 324 共九個子多維資料集中的約束不等式。 現在，它將列出每個可能使用複製粘貼和一些耐心，但一種程式設計方法是更快。

在代碼中，兩個外迴圈建立的每一個子多維資料集中的左上角。 在四個最內層迴圈中，儲存格表示為網格 [a] [b]! = 網格 [x] [y]。 如果你只是看的指數中的示例和形象，都是只是普通整數，你得到：

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

請注意在每個案件，是不等式約束時 ab < xy。 最深層的四個迴圈遍歷 a、 b、 x 和 y 來生成所有可能的指數和如果那麼條件對上創建約束 [a] [b] 和網格 [x] [y] 只有當 ab < xy。

添加瞭解決問題的具體約束

泛型約束已創建並添加到模型中後，該演示程式將添加定義特定的數獨謎題的約束。 演示益智有 27 的固定的值，所以您可以使用蠻力，就像這樣：

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

沒什麼錯蠻力的方法，但因為資料已經已放置在一個矩陣，它很容易轉移使用像這樣的程式定義的説明器方法調用的值：

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

注意到的奇怪的耦合模型及決策物件之間。 為開發人員開發人員編寫的庫代碼將很可能有引用的決定 （答案） 物體沿 model.grid[r][c 的行]。 無國界醫生組織庫的不尋常風格花了我大約三個例子就能熟悉它。

解決這一難題

一切就緒，該演示程式可以解決這一難題與此代碼：

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

NumberSolutions 方法是程式自訂的説明器被調用來檢查是否有零解 （這意味著衝突的約束被以某種方式定義） 或多個解決方案：

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

無國界醫生組織解決方法僅僅做那，放置到決定物件，是在模型物件中，這種關聯由對 SolverCoNtext 物件的引用的實際的答案。 作為一個副作用，解決方案物件都有一個品質欄位，可以包括可行和不可行的八個值之一。 解決方案使用 GetNext 方法不會返回一個明確的值，但不修改品質領域。 Don不怪我的無國界醫生組織設計。

數獨遊戲演示結束通過顯示儲存在裡面的網格矩陣決策物件的答案：

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

想得到方法從決策物件中提取問題答案的值。 記得答案被定義為 1 到 9 範圍內的整數。 然而，那裡是沒有 GetInteger 的方法所以答案值隱式強制轉換為 double 類型。 因為他們都以結束點為零，顯示時它們顯示為整數即使他們是 double 類型。

總結

CSP 本文中描述的特定類型真的是一個組合優化問題。 那就是，目標是找到的值具有最少約束錯誤的組合。 此處提供的資訊應允許您使用 MSF 庫來解決您可能會遇到的許多實際的組合優化問題。

I我要懺悔。 我姐姐的男朋友把我介紹給數獨家庭旅行到棕櫚泉幾年前。 他始終如一地打敗我，每當我們競爭數獨遊戲或填字遊戲或任何其他時間。 他不知道這是可能解決任何與此代碼的數獨謎題。 我期待我們下次的家庭旅行。 我有我的筆記本電腦。

博士。 James麥卡弗裡為在雷德蒙微軟研究院工作 他曾在幾個 Microsoft 產品，包括互聯網資源管理器和必應。聯繫到他在 jammc@microsoft.com。

由於以下的技術專家對本文的審閱：KirkOlynyk （微軟研究）