65.9K
CodeProject 正在变化。 阅读更多。
Home

使用 Microsoft Solver Foundation 进行数独

Atalia Beukes
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.85/5 (36投票s)

2012 年 7 月 29 日

CPOL

6分钟阅读

viewsIcon

88807

downloadIcon

2287

一个关于如何使用Microsoft Solver Foundation解决约束满足问题的示例。

引言

以下是Microsoft Solver Foundation如何用于解决约束满足问题（CSP），例如生成一个典型的数独问题。

在本文中，我不会试图解释有关约束满足问题的所有知识，但我会介绍一些概念，希望即使您从未听说过CSP，也能理解其中的含义。

关于数独

尽管这个游戏很简单，但也有一些变体。在本例中，我们只生成数独，但相同的原理也可以用于解决数独。无论我们是生成还是解决数独，我们拥有的约束条件和目标基本相同。在本例中，我们遵循以下游戏规则：

  1. 每行包含每个数字*恰好一次。
  2. 每列包含每个数字恰好一次。
  3. 每个区域**包含每个数字恰好一次。

生成数独后，我们需要隐藏一些数字，以便玩家可以进行游戏。我们将显示给用户的数字称为提示，最初我们会随机选择它们。

* 我们将使用数字1到9。
** 区域是我们网格中的子正方形（3x3）。

约束满足问题

CSP只是一种描述问题的方式。为了将问题格式化为CSP，需要识别以下内容：

  1. 一组变量。
  2. 每个变量的域。换句话说，每个变量可能的取值。
  3. 一组约束。约束将指定允许的数值组合。

当所有变量都有值并且我们满足了所有约束条件时，问题就解决了。并非所有问题都适用于此，但最好的例子之一是地图着色问题，其中我们不能用相同的颜色给两个相邻的区域着色。

以澳大利亚地图着色为例，变量将是昆士兰州、南澳大利亚州、西澳大利亚州等。

域是颜色。

我们的约束条件是昆士兰州的颜色应与南澳大利亚州的颜色不同，南澳大利亚州的颜色应与西澳大利亚州的颜色不同，依此类推。

数独作为约束满足问题

让我们开始解决我们的问题，生成一个数独。

  • 变量：我们将有81个变量，每个变量对应网格中的一个方格。
  • 域：我们选择使用数字1到9。
  • 约束：根据我们的规则，我们得到以下约束：每行应恰好包含每个数字一次。每列应恰好包含每个数字一次，每个区域应恰好包含每个数字一次。

要求

所以，这大致是我们希望应用程序实现的功能：

  1. 生成一个谜题，并使用一个9x9的网格来显示谜题。
  2. 隐藏一些数字，以便玩家可以填写。
  3. 检查生成的谜题是否有唯一解，如果没有，则警告玩家。
  4. 验证玩家的走法。
  5. 祝贺玩家完成游戏。

设计

由于我们有行、列和区域的概念，我将它们都添加到了一个Grid类中。Grid类将通过提供行、列和区域的getter使我们的工作更轻松，每个getter都返回整数列表。

SudokuProblem类将负责找出解决方案，并在每一步之后进行验证。

在处理数独这样的问题时，我们经常需要生成随机数，但不仅是随机数，而是唯一的随机数。我添加了一个Utils类，其中包含一个名为GetUniqueRandomNumbers()的方法。

正如我们之前所说，我们有一个包含81个变量的CSP。在使用Solver Foundation时，这会被封装在一个名为Decision的类中。这让我想到了我们需要一个DecisionFactory。这在保持SudokuProblem类整洁方面非常有帮助。

代码

要使用Microsoft Solver Foundation，需要将其添加为引用，并在使用的类中包含它。我从http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx获取了Express Edition。

要生成数独，我们只需要这些：

代码片段 #1 来自 SudokuProblem.cs
1   SolverContext context = SolverContext.GetContext();
2   Model model = context.CreateModel();
3   // See code snippet #2 for BuildDecisions
4   List<Decision> decisionList=DecisionFactory.BuildDecisions(Grid.GetAllSquares());
5   model.AddDecisions(decisionList.ToArray());
6
7   for (int j = 0; j < 9; j++)
8   {
9       model.AddConstraints("constraint_" + j,
10            Model.AllDifferent(getDecision(decisionList, Grid.GetRow(j))),
11            Model.AllDifferent(getDecision(decisionList, Grid.GetColumn(j))),
12            Model.AllDifferent(getDecision(decisionList, Grid.GetRegion(j)))
13      );
14  }
15
16  List<int> seedValues = Utils.GetUniqueRandomNumbers(1, 10, 9);
17  for (int i = 0; i < 9; i++)
18  {
19               model.AddConstraints("seed_" + i.ToString(),decisionList[i] == seedValues[i]);
20  }
21  context.Solve(new ConstraintProgrammingDirective());
22  solution = ConvertDecicionsToIntegers(decisionList);

我们首先向上下文添加一个新模型（代码片段 #1 的第1-2行）。我们将使用该模型来定义我们的CSP。

我们之前说过，我们需要81个变量，每个变量对应我们谜题中的一个方格。借助我们的Grid，我们可以获得所有81个方格。对于每个方格，我们构建一个Decision。（尽管文档对我帮助不大，但我仍会添加一些参考。）Decision是一个带有其域的变量。以下是创建具有1到9整数域的Decision的方法（代码片段 #2 的第13行）。

代码片段 #2 来自 DecisionFactory.cs
1  private static Domain domain = Domain.IntegerRange(1, 9);
2  public static List<Decision> BuildDecisions(List<int> squares)
3  {
4      if (squares == null || squares.Count == 0)
5      {
6           return new List<Decision>();
7      }
8
9      Decisions.Clear();
10
11     foreach (int i in squares)
12     {
13          Decisions.Add(new Decision(domain, Constants.StringAffix + i));
14     }
15     return Decisions;
16 }

我们需要将所有81个Decision添加到模型中。这在代码片段 #1 的第5行完成。

现在我们准备添加约束。我们从第一个游戏规则中得到前9个约束，即每行每个数字只能出现一次。这意味着每行应该有9个唯一的数字。最简单的方法是使用AllDifferent函数，并将每行的所有值传递给它（代码片段 #1 的第10行），我们的Grid使这项工作变得容易。然后，我们对列和区域也做同样的事情（代码片段 #1 的第11-12行）。

为了确保每次生成不同的数独谜题，我添加了9个种子。种子只是九个唯一的随机数，我用它们来填充第一行。我选择将它们添加为约束（代码片段 #1 的第16-20行）。

在代码片段 #1 的第21行，CSP被求解，并且我们的每个决策都会有一个值。

在代码片段 #1 的第22行，我们只是将它转换回一个整数列表。整数列表被传递给网格，并在那里显示。

代码片段 #3 来自 SudokuProblem.cs
1    public static bool HasUniqueSolution()
2    {
3        SolverContext context = SolverContext.GetContext();
4    context.ClearModel();
5    Model model = context.CreateModel();
6
7    List<decision> decisionList = DecisionFactory.BuildDecisions(Grid.GetAllSquares());
8    model.AddDecisions(decisionList.ToArray());
9
10    // Add 27 constraints to model
11    for (int j = 0; j < 9; j++)
12    {
13        model.AddConstraints("constraint_" + j,      
14               Model.AllDifferent(getDecision(decisionList, Grid.GetRow(j))),
15               Model.AllDifferent(getDecision(decisionList, Grid.GetColumn(j))),
16            Model.AllDifferent(getDecision(decisionList, Grid.GetRegion(j)))
17        );
18    }
19    // Add all hints as constraints
20    for (int i = 0; i < problem.Count; i++)
21    {
22        if (problem[i] != 0)
23        {
24            // This is a hint
25        model.AddConstraints("hint_" + i.ToString(), decisionList[i] == problem[i]);
26           }
27    }
28
29    List<decisionbinding> decisionBindings = new List<decisionbinding>();
30    for (int i = 0; i < problem.Count; i++)
31    {
32        if (problem[i] == 0) // This is hidden square
33        {
34        DecisionBinding binding = decisionList[i].CreateBinding();
35        decisionBindings.Add(binding);
36        }
37    }
38    context.FindAllowedValues(decisionBindings);
39    foreach (DecisionBinding decisionBinding in decisionBindings)
40    {
41        if (decisionBinding.Int32FeasibleValues.ToList().Count > 1)
42        {
43        return false;
44        }
45    }
46    return true;
47    }

我们现在需要确定用户将看到的谜题是否是真正的数独，换句话说，谜题是否只有一个解决方案。

我在SudokuProblem类中添加了另一个方法HasUniqueSolution()，可以在代码片段 #3 中看到。

确定谜题是否为真正的数独，又是一个CSP。为了简单起见，我们将使用81个决策，但现在我们不仅有最初的27个约束，还加上了每个提示作为约束。

我们将再次创建一个模型，添加决策和约束，但不是求解问题，而是调用FindAllowedValues来查找隐藏方格（代码片段 #3 的第38行）。

在代码片段 #3 的第29-37行，我创建了一个隐藏方格的决策绑定列表。这些列表被传递给FindAllowedValues()“允许值是问题可行解的一部分。”

以下是第38行之后决策绑定可能的样子。

我们真正关心的是每个允许值的数量。当有多个可行值时，意味着存在多个可能的解决方案。

© . All rights reserved.