项目
07/06/2015

此文章由机器翻译。

测试运行

使用 MSF 库完成 Sudoku 填数游戏

James McCaffrey 数独谜题是所谓的约束满足问题 (CSP) 的一个例子。以编程方式解决 Csp 一种方法是使用 Microsoft 规划求解基金会 (MSF) 图书馆。虽然它是极不可能你需要解决数独谜题作为你正常的工作职责的一部分，有至少三个理由为什么你可能会想要读这篇文章。第一，这里介绍的技术可以用于解决很多现实问题。第二，这篇文章将介绍你到无国界医生组织库，它的功能。第三，你可能发现以编程方式解决数独谜题是有趣和引人入胜。

要得到一个何方这篇文章的想法，看看该演示程序中图 1。演示控制台应用程序的设置和显示典型的数独谜题的数据开始。下一步，它通过编程方式定义约束（所需条件）所共有的所有的数独谜题，然后设置特定于拼图数据约束。然后，在幕后，演示使用的无国界医生组织库来解决这一难题。演示结束通过显示解决方案。

使用规划求解 Microsoft 基础数独
使用规划求解 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 库来解决您可能会遇到的许多实际的组合优化问题。

我要忏悔。我姐姐的男朋友把我介绍给数独家庭旅行到棕榈泉几年前。他始终如一地打败我，每当我们竞争数独游戏或填字游戏或任何其他时间。他不知道这是可能解决任何与此代码的数独谜题。我期待我们下次的家庭旅行。我有我的笔记本电脑。

James McCaffrey 为在雷德蒙微软研究院工作他曾在几个 Microsoft 产品，包括互联网资源管理器和必应。联系到他在 jammc@microsoft.com。

由于以下的技术专家对本文的审阅：KirkOlynyk （微软研究）