带有LINQ的Sudoku Solver(C#3.0)（译文）

原文地址：https://www.codeproject.com/Articles/14714/Sudoku-Solver-with-LINQ-C-3-0

原文作者：derekliang

译文由本站 robot-v1.0 翻译

前言

In this article, I am presenting a solution for solving and creating Sudoku puzzles with LINQ which is Microsoft’s latest enhancement to the C# language.

在本文中,我将介绍一种使用LINQ解决和创建Sudoku拼图的解决方案,这是Microsoft对C#语言的最新增强.

• 下载源代码299.6 KB(Download source code - 299.6 KB)

介绍(Introduction)

在本文中,我将介绍一种使用LINQ解决和创建Sudoku拼图的解决方案,这是Microsoft对C#语言的最新增强.(In this article, I am presenting a solution for solving and creating Sudoku puzzles with LINQ which is Microsoft’s latest enhancement to the C# language.)

什么是LINQ？(What is LINQ?)

LINQ项目是.NET Framework 2.0语言扩展集的代号,这些语言扩展包含语言集成的查询,设置和转换操作.这些扩展使您可以使用类似SQL的语法来构建表达力强大的表达式.实际上,作为LINQ项目的组成部分的Dlinq提供了SQL和LINQ对象之间的直接转换,这使数据库应用程序的编程变得更加容易.所有LINQ程序都被编译为IL,可以直接在.NET Framework下运行.不需要翻译.(The LINQ project is a code name for a set of language extensions to the .NET Framework 2.0 that encompass language-integrated query, set, and transformation operations. The extensions enable the construction of expressive and powerful expressions in SQL-like syntax. In fact, Dlinq which is a component of the LINQ project, provides direct translation between SQL and LINQ objects which makes programming database applications much easier. All LINQ programs are compiled into IL which can be run directly under .NET Framework. There is no interpreter required.)

什么是数独？(What is Sudoku?)

数独是数字难题.难题的目的是在由3x3区域(标记为灰色)组成的9x9网格的每个单元格中输入1到9的数字.难题从预定单元格中的各个数字开始,如下图的左侧所示.难题的解决方案必须确保每个3x3区域,每一行和每一列都必须包含所有数字1到9,如下图的右侧所示.(Sudoku is number puzzle. The aim of the puzzle is to enter numerical digits from 1 to 9 in each cell of a 9x9 grid made up of 3x3 region (as marked grey). The puzzle starts with various digits in pre-determined cells as shown in left hand side of the following diagram. A solution of the puzzle must ensure that each 3x3 region, each row and each column, must contain all the numbers 1 to 9 as shown in the right hand side of the following diagram.)

LINQ构造函数(LINQ constructor)

在本节中,我将从最简单到最复杂的LINQ"查询表达式"进行介绍.要获得完整参考,可以在以下位置找到它(I will introduce some of the LINQ “query expression” used in this project in this section from the easiest to the more complex one. For complete reference, you can find it in) C#3.0版规范(2006年5月)(C# Version 3.0 Specification (May 2006)) .(.) 查询表达式是一种用于查询的语言集成语法,与关系和层次查询语言(例如SQL和XQuery)相似.查询表达式以from子句开头,以select或group子句结尾.查询表达式具有3个对编程有用的属性.(Query expression is a language integrated syntax for queries that is similar to relational and hierarchical query languages such as SQL and XQuery. A query expression begins with a from clause and ends with select or group clause. A query expression has 3 properties which are useful in programming.)

• 查询表达式可以用作其他查询表达式的数据源,以进一步优化数据(A query expression can be used as a data source for other query expression to further refine data)
• 查询表达式是具有以下内容的对象(An query expression is an object with) IEnumerable<t /> 接口,因此可以在(interface therefore it can used in) foreach 声明(statement)
• 查询表达式可以转换为(An query expression is can be converted to) Array<t /> 要么(or) List<t /> 通过(via the) ToArray() 要么(or) ToList() 方法(method) 在上述第2点和第3点中,类型T是基于以下内容推断和创建的匿名类型的编译器:(In the above points 2 and 3, type T is a compiler inferred and created anonymous type based on the) select 要么(or) group 查询表达式的子句.例如下面的代码:(clause of the query expression. For example for the following code:)

var smallNumbers = from n in numbers
                   where n<5
                   select ( new { number=n, powerOf2=n*n }) ;

LINQ编译器将生成一个匿名类型,该匿名类型不能在您的代码中的任何地方引用.显示如下:(LINQ compiler will generate an anonymous type which canNOT be referenced anywhere in your code. It is shown as the following:)

class __anonymouse_class
{
     public int number;
     public int powerOf2;
}

然后,以下语句将遍历查询表达式中所述的所有小于5的数字.(Then the following statement will loop through all the numbers that are less then 5 as stated in the query expression.)

foreach( var n in smallNumbers )
     Console.WriteLine(n.number + " " + n.powerOf2);

在内部,LINQ编译器将查询表达式转换为遵循查询表达式模式的方法的调用.在我们的示例中,它将被转换为以下代码:(Internally the LINQ compiler translates query expression into invocations of methods that adhere to the query expression pattern. In our example, it will be translated into the following code:)

smallNumbers = numbers.Where( n => n<5 ).Select( n => new 
                    { number=n, powerOf2=n*n });

n => n<5 是Lambda表达式.可以明确地写成(is a Lambda expression. It can be written explicitly as) (int n) => { return n<5; } 它将进一步转换为委托类型(which will be further translated into delegate type) bool (int n) 和匿名方法(and anonymous method) {return n<5;} .(.) 有关详细信息,请参考(For details, please reference the) C#3.0版规范(2006年5月)(C# Version 3.0 Specification (May 2006)) .(.) 在开始之前,让我们看一下C#3.0版中的另一个新功能,即"隐式本地变量声明".当局部变量声明指定(Before we start, let us look at another new feature in the C# version 3.0 called “implicitly typed local variable declaration”. When a local variable declaration specifies) var 作为类型,没有类型名称(as the type and no type name) var 在范围内,声明是隐式类型的局部变量声明,并且要声明的局部变量的实际类型是从用于初始化变量的表达式中推断出来的.例如:(is in scope, the declaration is an implicitly type local variable declaration and the actual type of the local variable being declared is inferred from the expression used to initialize the variable. For example:)

var i = 0 ;         // same as: int i = 0 ;
var s = "abc" ;     // same as: string s = "abc" ;
var sb = new StringBuilder() ; 
                    // same as: StringBuilder sb = new StringBuilder();

查询表达简介(Introduction to query expression)

顺序(Sequence)

让我们开始(Let us start with) Sequence .(.) Sequence.Range(1, 9) 是一个方法调用,该方法返回一个查询表达式,该表达式表示来自(is a method call that returns a query expression which represents an array of number from) 1 至(to) 9 .(.)

var numbers = Sequence.Range(1, 9) ;
foreach( var n in numbers )
   Console.WriteLine(n);

结果:(Result:)

选择(select)

select 查询表达式中的子句指定将返回的类型(或匿名类型).在以下情况下,它是类型(clause in the query expression specifies the type (or anonymous type) that will be returned. In the following case it is of type) int .(.)

var numbers = Sequence.Range(1, 9);
var SameNumbers = from n in numbers
                  select n;
foreach( var n in SameNumbers )
   Console.WriteLine(n);

结果:(Result:) (与上面的输出相同)((same as the above output))

哪里(where)

where 查询表达式中的子句,指定(clause in a query expression specifying a filtering condition of the)查询表达式(query expression).(.)

var numbers = Sequence.Range(1, 9) ;
var smallNumbers = from n in numbers
                   where n<5
                   select n ;
foreach( var n in smallNumbers )
    Console.WriteLine(n);

结果:(Result:)

除了(Except)

Except 是一个集合运算符,它返回一个查询表达式,该查询表达式具有一个查询表达式的所有元素,但不包含在另一个查询表达式中.(is a set operator which returns a query expression that has all the elements of a query expression but not in another query expression.)

var numbers = Sequence.Range(1, 9) ;
var smallNumbers = Sequence.Range(1, 4) ;
var bigNumbers = numbers.Except(smallNumbers);
foreach( var n in bigNumbers )
    Console.WriteLine(n);

结果:(Result:)

折(Fold)

Fold 是一个聚合运算符,它接受查询表达式中的每个元素并对其执行某些操作.在我们的示例中,一个临时变量(is an aggregate operator which takes every elements in the query expression and does something about it. In our example, a temp variable) r 将被创建并分配给(will be created and assigned to) 0 ,以及每个元素(, and for each elements) r = r + n 将被评估.结果将分配给变量(will be evaluated. Result will be assigned to variable) sum .(.)

var numbers = Sequence.Range(1, 9) ;
var sum = numbers.Fold(0, (r, n) => r+n);
Console.WriteLine("The sum is: "+sum);

结果:(Result:)

该程序如何工作？(How the program works?)

拼图以一维数组表示((A puzzle is represented in a one dimensional array () int [] ).每个单元格的值可以是(). The value of each cell can be) 1 至(to) 9 要么(or) 0 如果单元格为空.选择一维数组可使用LINQ语言构造函数轻松进行数据处理/转换,因为无需更改大量代码即可轻松实现16x16难题求解器和生成器.数独谜题声明为以下代码:(if the cell is empty. One dimensional array was chosen for easy data manipulation/transformation using LINQ language constructors as it is easy to implement a 16x16 puzzle solver and generator without changing much of the code. A Sudoku puzzle is declared as the following code:)

int [] sudokuPuzzle =
{
                   0, 7, 1, 0, 9, 0, 8, 0, 0,
                   0, 0, 0, 3, 0, 6, 0, 0, 0,
                   4, 9, 0, 0, 0, 0, 7, 0, 5,
                   0, 1, 0, 9, 0, 0, 0, 0, 0,
                   9, 0, 2, 0, 0, 0, 6, 0, 3,
                   0, 0, 0, 0, 0, 8, 0, 2, 0,
                   8, 0, 5, 0, 0, 0, 0, 7, 6,
                   0, 0, 0, 6, 0, 7, 0, 0, 0,
                   0, 0, 7, 0, 4, 0, 3, 5, 0
};

主要例程是(The main routine is) solvePuzzle 这将一个难题作为单个输入参数.其他辅助输入变量将用于确定谜题的大小,终止条件,是否我们尝试通过按随机顺序尝试数字来解决谜题.输出变量是(which takes a puzzle as the single input parameter. Other auxiliary input variables will be used to determined the size of the puzzle, termination condition, whether we try to solve the puzzle by trying numbers in random order. Output variables are the) return 的价值(value of the) solvePuzzle ,(,) true 如果找到解决方案,并且(if it finds a solution and) false 如果找不到解决方案.如果找到多个解决方案,它将设置一个变量.它主要用于生成拼图.(if it finds no solution. Also it will set a variable if more than 1 solution found. It is mainly for generation of puzzles.) 如果您想了解求解器的工作原理,我建议打开调试输出.该代码是不言自明的.(I will recommend to turn on the debugging output if you are curious to see how the solver works. The code is quite self-explanatory.) 为了创建数独谜题,我采取了2个步骤:(For creating a Sudoku puzzle, the approach I took had 2 steps:)

• 通过使用空单元格调用求解器来创建难题解决方案.每次都会返回相同的解决方案.为了随机化,求解器将对数字进行重新排序以尝试,如以下代码所示:(Create a puzzle solution by invoking the solver with empty cells. It will return the same solution every time. To randomize, the solver will re-order the number to try as shown in the following code:)

• 尝试找出难题解的每个单元格中的数字,然后查看数独难题是否仍然具有唯一的解.如果仍然有效,则将单元格清空.否则不要做任何事情.我们必须在此处执行相同操作,以随机化从单元格中取出数字的顺序.如下所示:(Try to take out numbers in each cell of the puzzle solution and see if the Sudoku puzzle still has a unique solution. If it still does, make the cell empty. Otherwise do not do anything. We have to do the same here to randomize the order in which the numbers are being taken out of cells. As shown below:)

兴趣点(Points of Interest)

LINQ语言构造函数提供了更高的抽象度,并使程序员可以在实际算法和/或问题域上花费更多时间.使用LINQ,对元素的变换/网格数组进行常规操作从未如此简单.(LINQ language constructor provides a higher abstraction and enables programmers to spend more time on the actual algorithm and/or problem domain. Common operations on transform/mesh array of elements can never be easier with LINQ.) 本文中的所有代码均已通过编译和测试(All the code in this article has been compiled and tested with) Microsoft LINQ项目2006年5月CTP(Microsoft LINQ project May 2006 CTP) .(.)

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。