# 使用 MSF 库完成 Sudoku 填数游戏

James McCaffrey

## 规划求解微软基础库

``````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");
}
static void AddDataConstraints(int[][] data,
Model model, Decision[][] grid) { . . }
static int NumberSolutions(SolverContext problem) { . . }
}
} // ns
``````

Visual Studio模板生成源代码的顶部，我删除所有不必要的使用只有一个顶级的系统命名空间引用的语句。 接下来，我添加了一个引用到的无国界医生组织库 DLL 文件，然后使用添加引用库把它带到范围的声明。

## 问题的设置

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

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

``````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)
``````

``````for (int r = 0; r < 9; ++r)
for (int c = 0; c < 9; ++c)
``````

## 添加泛型约束

``````Console.WriteLine("Creating generic row constraints");
for (int r = 0; r < 9; ++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]);
}
``````

``````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
``````

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

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

## 添加了解决问题的具体约束

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

## 解决这一难题

``````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;
}
``````

``````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");
} // Main
``````

## 总结

CSP 本文中描述的特定类型真的是一个组合优化问题。 那就是，目标是找到的值具有最少约束错误的组合。 此处提供的信息应允许您使用 MSF 库来解决您可能会遇到的许多实际的组合优化问题。

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