使用Microsoft Solver Foundation的Sudoku(译文)
By robot-v1.0
本文链接 https://www.kyfws.com/games/sudoku-using-microsoft-solver-foundation-zh/
版权声明 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
- 9 分钟阅读 - 4194 个词 阅读量 0使用Microsoft Solver Foundation的Sudoku(译文)
原文地址:https://www.codeproject.com/Articles/419389/Sudoku-using-Microsoft-Solver-Foundation
原文作者:Atalia Beukes
译文由本站 robot-v1.0 翻译
前言
An example of how to use Microsoft Solver Foundation on a constraint satisfaction problem.
有关如何在约束满足问题上使用Microsoft Solver Foundation的示例.
介绍(Introduction)
以下是如何使用Microsoft Solver Foundation解决问题的示例(The following is an example of how Microsoft Solver Foundation can be used to solve a) 约束满足问题(constraint satisfaction problem) (CSP)就像生成典型的((CSP) like generating a typical) 数独(Sudoku) 问题.(problem.) 在本文中,我不会尝试解释关于约束满足问题的所有知识,但是我将继续研究这些概念,希望即使您从未听说过CSP,您仍然可以理解.(In this article, I do not attempt to explain everything there is to know about constraint satisfaction problems, but I will go over the concepts, in the hope that even if you have never heard of CSP, you will still get the idea.)
关于数独的一点(A Little About Sudoku)
尽管游戏非常简单,但仍有一些变化.在此示例中,我们仅生成一个数独,但是相同的原理也可用于求解数独.无论我们生成还是求解数独,我们都具有相同数量的约束和几乎相同的目标.在此示例中,我们遵循以下游戏规则:(Although the game is pretty simple, there are a few variations. In this example we only generate a Sudoku, but the same principles can be used to solve a Sudoku. Whether we generate or solve a Sudoku, we have the same amount of constraints and pretty much the same objective. In this example, we stick to the following game rules:)
- 每行仅包含一次*.(*Each row contains each digit* exactly once.*)
- 每列只包含每个数字一次.(Each column contains each digit exactly once.)
- 每个区域仅包含每个数字一次.(Each region contains each digit exactly once.*) 生成数独之后,我们需要隐藏一些值,以便玩家做某事.我们将参考显示给用户的数字作为提示,并且我们将首先随机选择这些数字.(After generating a Sudoku, we need to hide some of the values so that the player has something to do. We will refer to the digits that we show to the user as hints and we will choose these randomly at first.) 我们将使用数字1到9.( We will use digit 1 to 9.) 区域是我们网格中的子正方形(3x3).( Regions are the sub-squares (3x3) in our grid.*)
约束满足问题(Constraint Satisfaction Problem)
CSP只是描述问题的一种特定方式.为了将问题引入CSP格式,需要确定以下内容:(A CSP is just a specific way to describe a problem. In order to get a problem into a CSP format, the following needs to be identified:)
- 一组变量.(A set of variables.)
- 每个变量的域.换句话说,每个变量的可能值.(The domain for each variable. In other words, possible values for each variable.)
- 一组约束.约束将指定允许的值组合.(A set of constraints. The constraints will specify allowable combinations of values.) 当所有变量都具有值并且我们满足所有约束时,问题就解决了.并非所有问题都可以解决这个问题,但是,解决问题的最好的例子之一就是为地图着色的问题,因为我们无法为2个相邻的零件着色相同的颜色.(When all of the variables have values and we met all the constraints, the problem is solved. Not all problems lend themselves to this, but one of the best examples of a problem that do, is the problem of colouring a map were we can’t colour 2 adjacent parts with the same colour.) 在为澳大利亚着色的示例中,变量将为昆士兰州,南澳大利亚州,西澳大利亚州等.(In the example of colouring Australia, the variables will be Queensland, South Australia, Western Australia and so on.) 领域,颜色.(The domain, the colours.) 我们的约束条件是昆士兰州的颜色应与南澳大利亚州不同,南澳大利亚州的颜色应与西澳大利亚州不同,依此类推.(And our constraints will be that Queensland’s colour should differ from South Australia, South Australia’s colour should differ from Western Australia and so on.)
数独作为约束满足问题(Sudoku as a Constraint Satisfaction Problem)
让我们开始解决我们的问题,生成数独.(Let’s get started on our problem, generating a Sudoku.)
- 变量:我们将有81个变量,网格中的每个正方形一个.(Variables: We will have 81 variables, one for each square in our grid.)
- 域:我们选择使用数字1到9.(Domains: We have chosen to use digits 1 to 9.)
- 约束:从我们的规则中,我们得到以下约束:每行应只包含一次数字.每列仅包含一次数字,每个区域仅包含一次数字.(Constraints: From our rules, we get the following constraints: Each row should contain each digit exactly once. Each column contains each digit exactly once and each region contains each digit exactly once.)
要求(The Requirements)
因此,这或多或少是我们希望我们的应用程序要做的:(So this is more or less what we want our application to do:)
- 生成拼图并使用9x9网格显示拼图.(Generate a puzzle and use a 9x9 grid to display the puzzle.)
- 隐藏值,以便玩家可以填写它们.(Hide values, so that the player can fill them in.)
- 检查所产生的问题是否具有独特的解决方案,如果不是,请警告玩家.(Check to see if the generated problem has a unique solution, if not, warn the player.)
- 验证玩家的动作.(Validate the player’s moves.)
- 祝贺玩家完成.(Congratulate the player on completion.)
该设计(The Design)
由于我们具有行,列和区域的概念,因此将它们全部添加到(Since we have the concept of rows, columns and regions, I added these all into a) Grid
类.的(class. The) Grid
类通过为我们提供行,列和区域的吸气剂,使我们的生活更加轻松,每个吸气剂均以整数列表形式返回值.(class will make our lives easier by providing us with getters for rows, columns and regions, each returning the values as a List of integers.)
的(The) SudokuProblem
类必须提出解决方案,并且在每次移动后都必须进行验证.(class will have to come up with the solution and also do the validation after each move.)
处理Sudoku之类的问题时,通常需要生成随机数,但不仅要生成随机数,还要生成唯一的随机数.我加了(When working with a problem like Sudoku, one often needs to generate random numbers, but not only random numbers but unique random numbers. I added a) Utils
具有方法的类(class which has a method) GetUniqueRandomNumbers()
.(.)
就像我们之前说的,我们有一个带有81个变量的CSP.使用求解器基础时,它被包装在称为(Like we said earlier, we have a CSP with 81 variables. When using solver foundation, this gets wrapped in a class called) Decision
.这使我认为我们需要一个(. This made me think that we need a) DecisionFactory
.这对保持(. This helped a lot with keeping the) SudokuProblem
全班干净.(class clean.)
代码(The Code)
为了使用Microsoft求解器基础,需要将其包含为参考,并将其包含在使用它的类中.我得到了速成版(In order to use Microsoft solver foundation, one needs to include it as a reference and include it in the classes using it. I got the express edition from) http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx(http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx) 要生成数独,这就是我们所需要的:(To generate a Soduko, this is all we need:)
SudokuProblem.cs的代码片段#1(Code snippet #1 from 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-2行代码段#1).我们将使用该模型来定义我们的CSP.(We start by adding a new model to our context (lines 1-2 snippet #1). We will use the model to define our CSP.)
前面我们说过,我们将需要81个变量,每个谜题中的每个变量一个.在我们的帮助下(We said earlier that we will need 81 variables, one for each square in our puzzle. With the help of our) Grid
,我们得到所有81个正方形.为此,我们建立了一个(, we get all 81 squares. For each of these, we build a) 决断(Decision) . (尽管文档对我没有帮助,但我仍将添加一些参考.)(. (Although the documentation wasn’t that helpful to me, I am still going to add some reference to it.) A) Decision
是具有其域的变量.这是我们如何创建一个(is a variable with its domain. Here is how we create a) Decision
范围为1到9的整数域(第13行代码段2).(with the Domain of integers which range from 1 to 9 (line 13 snippet #2).)
DecisionFactory.cs中的代码段#2(Code snippet #2 from 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(We need to add all the 81) Decision
到模型.这在代码段1的第5行完成.(s to the model. This gets done on line 5 of snippet #1.)
现在我们准备添加约束.我们从第一个游戏规则中得到了前9个约束,该约束说明在每一行中,每个数字只能出现一次.这意味着我们每行应该有9个唯一值.最简单的方法是使用(Now we are ready to add constraints. We get our first 9 constraints from the first game rule stating that in each row, each digit can occur only once. This means that we should have 9 unique values in each row. The easiest way to get to this, is to use the) AllDifferent
函数并向其馈送每行(第10行代码段1)中的所有值,(function and feed it all the values from each row (line 10 snippet #1), our) Grid
使此操作变得容易.然后,我们也对列和区域执行相同的操作(第11-12行代码段1).(makes this easy to do. We then also do the same for our columns and regions (line 11-12 snippet #1).)
为了确保每次都遇到不同的Sudoku问题,我添加了9个种子.种子只是我用于第一行的九个唯一随机数.我选择将它们添加为约束(第16-20行代码段1).(To ensure that we get a different Sudoku problem each time, I have added 9 seeds. The seeds are just nine unique random numbers which I use for the first row. I have chosen to add them as constraints (line 16-20 snippet #1).) 在代码片段1的第21行中,CSP得到了解决,我们的每个决策都将具有价值.(In line 21 of snippet #1, the CSP gets solved and each of our decision will have a value.) 在代码片段1的第22行中,我们只是将其转换回整数列表.整数列表将传递到显示它的网格.(In line 22 of snippet #1 we just convert this back to a list of integers. The list of integers gets passed to the gird where it gets displayed.)
SudokuProblem.cs的代码片段#3(Code snippet #3 from 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 }
现在,我们需要确定将向用户呈现的问题是否是真正的Sudoku,换句话说,如果问题只有一个解决方案.(We now need to determine if the problem the user will be presented with is a real Sudoku, in other words if the problem has only one solution.)
我添加了另一种方法(I added another method to the) SudokuProblem
类,(class,) HasUniqueSolution()
可以在代码片段3中看到(that can be seen in snippet #3.)
确定问题是否是真正的Sudoku是另一个CSP.为简单起见,我们将使用81个决策,但我们现在不仅将每个提示都作为约束,而不仅仅是最初的27个约束.(Determining if the problem is a real Sudoku, is yet another CSP. To keep it simple we will use 81 decisions, but instead of only the initial 27 constraints, we now also have each of the hints as a constraint.)
我们将再次创建一个模型,添加决策和约束,但是我们将不称其为解决问题(We will again create a model, add decisions and constraints but instead of solving the problem, we will call) FindAllowedValues(FindAllowedValues) 用于隐藏的正方形(第38行代码段#3).(for the hidden squares (line 38 snippet #3).)
在代码段3的第29 – 37行中,我为隐藏的正方形创建了决策绑定列表.这些被传递给(On line 29 – 37 of snippet #3, I create a list of decision bindings for the hidden squares. These gets passed to) FindAllowedValues()
"(“)允许值是该问题某些可行解决方案的一部分.(An allowed value is one that is part of some feasible solution to the problem.)"(”)
这是第38行之后决策绑定的外观示例.(Here is an example of what a decision binding might look like after line 38.)
我们真的只对每个可行值的数量感兴趣.当我们拥有不止一个可行值时,这意味着存在不止一种可能的解决方案.(We are really only interested in the amount of feasible values of each. When we have more than one feasible value, it means that there is more than one possible solution.)
许可
本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。
C# WPF AI 新闻 翻译