使用 LINQ (C# 3.0) 解决数独

• 下载源代码 - 299.6 KB

引言

在本文中，我将介绍一种使用 LINQ 来解决和创建数独谜题的方案，LINQ 是 Microsoft 对 C# 语言的最新增强。

什么是 LINQ？

LINQ 项目是 .NET Framework 2.0 的一套语言扩展的代码名称，它包含了语言集成查询、集合和转换操作。这些扩展能够以类似 SQL 的语法构建富有表现力和强大的表达式。事实上，LINQ 项目的一个组成部分 Dlinq 提供了 SQL 和 LINQ 对象之间的直接转换，这使得数据库应用程序的编程更加容易。所有 LINQ 程序都将被编译成 IL，可以直接在 .NET Framework 下运行。不需要解释器。

什么是数独？

数独是一种数字益智游戏。游戏的目的是在一个由 9x9 的网格（由 3x3 的区域组成，标记为灰色）的每个单元格中填入数字 1 到 9。游戏开始时，在预先确定的单元格中填入各种数字，如以下图的左侧所示。解决此游戏必须确保每个 3x3 的区域、每行和每列都包含数字 1 到 9，如以下图的右侧所示。

LINQ 构造

在本节中，我将介绍本项目中使用的一些 LINQ“查询表达式”，从最简单的到更复杂的。有关完整的参考，请参阅 C# 版本 3.0 规范 (2006 年 5 月)。

查询表达式是一种类似于 SQL 和 XQuery 的关系型和层次型查询语言的、用于查询的语言集成语法。查询表达式以 from 子句开头，以 select 或 group 子句结尾。查询表达式有 3 个对编程有用的属性。

1. 查询表达式可以用作另一个查询表达式的数据源，以进一步优化数据。
2. 查询表达式是一个具有 IEnumerable<t /> 接口的对象，因此可以在 foreach 语句中使用。
3. 查询表达式可以通过 ToArray() 或 ToList() 方法转换为 Array<t /> 或 List<t /> 。

在以上第 2 点和第 3 点中，类型 T 是一个编译器推断并根据查询表达式的 select 或 group 子句创建的匿名类型。例如，对于以下代码

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

LINQ 编译器将生成一个匿名类型，该类型在您的代码中的任何位置都不能被引用。它显示如下

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

然后，以下语句将遍历查询表达式中指定的、小于 5 的所有数字。

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

内部，LINQ 编译器将查询表达式翻译成符合查询表达式模式的方法调用。在我们的示例中，它将被翻译成以下代码

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

n => n<5 是一个 Lambda 表达式。它可以显式地写成 (int n) => { return n<5; }，它将被进一步翻译成委托类型 bool (int n) 和匿名方法 {return n<5;}。
有关详细信息，请参考 C# 版本 3.0 规范 (2006 年 5 月)。

在我们开始之前，让我们看一下 C# 3.0 中的另一个新特性，称为“隐式类型的局部变量声明”。当局部变量声明指定 var 作为类型，并且没有类型名称 var 在作用域内时，该声明就是一个隐式类型的局部变量声明，被声明的局部变量的实际类型是从用于初始化变量的表达式中推断出来的。例如

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();

查询表达式简介

序列

让我们从 Sequence 开始。Sequence.Range(1, 9) 是一个方法调用，它返回一个查询表达式，该表达式表示一个从 1 到 9 的数字数组。

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

结果

select

查询表达式中的 select 子句指定将返回的类型（或匿名类型）。在以下情况下，它为 int 类型。

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

结果
(与上面输出相同)

其中

查询表达式中的 where 子句指定了查询表达式的过滤条件。

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

结果

Except

Except 是一个集合运算符，它返回一个查询表达式，该表达式包含第一个查询表达式的所有元素，但不包含第二个查询表达式的任何元素。

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

结果

Fold

Fold 是一个聚合运算符，它获取查询表达式中的每个元素并对其进行处理。在我们的示例中，将创建一个临时变量 r 并将其赋值为 0，然后对每个元素求值 r = r + n。结果将赋值给变量 sum。

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

结果

程序如何工作？

谜题用一维数组（int []）表示。每个单元格的值可以是 1 到 9 ，如果单元格为空则为 0 。选择一维数组是为了方便使用 LINQ 语言构造函数进行数据操作/转换，因为它易于实现 16x16 的谜题求解器和生成器，而无需更改太多代码。数独谜题声明如下代码所示

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

主例程是 solvePuzzle ，它以谜题作为唯一的输入参数。其他辅助输入变量将用于确定谜题的大小、终止条件，以及是否尝试以随机顺序尝试数字来求解谜题。输出变量是 solvePuzzle 的 return 值，如果找到解决方案则为 true，如果找不到解决方案则为 false。此外，它还会设置一个变量，指示是否找到多个解决方案。这主要是为了生成谜题。

如果您想知道求解器是如何工作的，我建议您打开调试输出。代码本身很容易理解。

对于创建数独谜题，我采取了 2 步方法

1. 通过调用求解器并传入空单元格来创建谜题解决方案。它每次都会返回相同的解决方案。为了随机化，求解器将重新排列尝试的数字顺序，如以下代码所示

   if (_isRondomized)
           arrayOfAllNumber =
                  from  n in arrayOfAllNumber
                  orderby _random.Next()
                  select n ;
   

2. 尝试从谜题解决方案的每个单元格中移除数字，看看数独谜题是否仍然有唯一解。如果仍然有，则将单元格设置为空。否则，不做任何操作。我们必须在这里做同样的事情来随机化从单元格中移除数字的顺序。如下所示

   var arrayOfNumberToRemove =
                  from  n in Sequence.Range(0,  size*size-1)
                  orderby _random.Next()
                  select n ;
   

关注点

LINQ 语言构造提供了更高的抽象级别，使程序员能够花费更多时间在实际算法和/或问题域上。使用 LINQ 可以轻松地对元素数组进行转换/网格化等常见操作。

本文中的所有代码都已使用 Microsoft LINQ 项目 2006 年 5 月 CTP 进行了编译和测试。