优化 UMPC 应用程序的点触和手写操作

简介

去年，在纽约市西村的一家小咖啡馆，有人向我介绍了一款铅笔填数游戏，我的朋友 Luke 完全被这款游戏迷住了。当时与其他人的愉快谈话使我免于步其后尘，可是却没想到，躲得过初一躲不过十五。几个月之后，也就是 2005 年 6 月，我去伦敦看望兄弟和大学室友时又碰到了 Sudoku 游戏。显见 Sudoku 已经风靡一时，无弗远近。我从好奇、试探，最后也沉迷于其中。对开发人员来说往往会是这样，今天的激情极有可能转化为明天的开发项目。这次也毫不例外，我飞回美国后很快安装了第一个版本的 C# Sudoku 游戏，并马上开始运行。

而我对它却不太满意，总感觉缺点什么。用笔在纸上计算并得出正确数字是一件让人心情愉悦的事。而问题在于游戏转化为 Windows 表格形式后，这种乐趣不见了。这个问题深深地困扰着我。Sudoku 是一种非常适合在 Tablet PC 上实现的应用程序。第二天我下载了 Tablet PC SDK，很快就将这款由键盘和鼠标操作的游戏改为笔控操作。（请注意示例程序文件中的程序员注释使用的是英文，本文中将其译为中文是为了便于参考。本文章还包含指向英文网页的链接。）

图 1：Microsoft Sudoku

本文就如何基于 Tablet PC 实现 Sudoku 进行了深入探讨。与原来在 Touch Pack 上的实现方法相同，ultra-mobile PC (UMPC) 上预装了软件包。除了 Sudoku 游戏的特定细节外，本文还详述了游戏实现的算法问题，有助于您在 Tablet PC 上实现其他的应用程序设计。

什么是 Sudoku？

Sudoku 是一种填数游戏，风靡于日本和欧洲。在很短的时间内它又迅速占领了美国市场 － 书店里摆满了 Sudoku 产品，报纸也连篇累牍地对其进行报道。游戏的原型是一个 9x9 的网格，分成九个 3x3 的小框，每一小框包含 9 个单元格。如图 2 所示为包含 81 个单元格的完整图形。

图 2：空的 Sudoku 网格

这款游戏的玩法是：在每个单元格中填入一个数字（1-9），最后每行、每列和每一小框的九个单元格中都包含有全部的 9 个数字（超级 Sudoku 难度更高，它使用 16x16 网格，填入数字 1-9 和字母 A-G）。

如图 3 显示为一个 Sudoku 有效解法。

图 3：Sudoku 有效解法

通过计算，9x9 Sudoku 共有 10²¹ 种以上的有效解法（请登录 http.//www.afjarvis.staff.shef.ac.uk/sudoku/ 了解有关这方面计算的详细信息）。开局时，网格中已经填了一些数字，而其魅力就在于，每局游戏只有一种正确解法。您必须通过逻辑推导填入所有缺失的数字。

以图 4 所示的游戏为例（为便于讲解，我们以黄色和红色突出显示了几个单元格）。如上所述，每一小框都要包含全部的九个数字。现在，左上角的框中没有 2，只需简单推导一下就能知道 2 应该填入哪个单元格。第一行不行，因为第一行已经有 2 了（在右上角，已经用黄色突出显示）。中间一行也不行，这一行也有 2 （在第二行、第四列）。很明显也不能是第三行第二列，该单元格已经有一个 7 （以黄色突出显示）；也不可能是 7 右侧的单元格，这一列也有 2（第八行，以黄色突出显示）。所以，2 一定是填在第三行第一列，即以红色突出显示的单元格。确定了该框内 2 的位置后，我们离完成游戏更近了一步。

图 4：开始 Sudoku 游戏

现在您已经对游戏有了一定了解，本文的其余内容主要是关于如何在 Tablet PC 上实现 Sudoku 游戏的。首先，让我们来看一下 Tablet PC 应用程序的基本要求，并说明如何在 Sudoku 中满足这些要求，以及您在编写自己的应用程序时应该怎么做。接下来，我会具体讲解 Sudoku 游戏实现的具体问题，主要是如何通过适当算法完成 Sudoku 的相关任务，如生成新游戏和找出游戏解法。然后再讲一下有关 Tablet PC 的具体细节问题，主要是如何使用 Tablet PC API 来支持笔式交互。最后，我将会给出一些有趣的概念和示例，您可以用自己喜欢的方法玩游戏。

本部分涉及的概念适用于一般的 Tablet PC 应用程序，并非仅限于 Sudoku 游戏。

平台检测

多数为 Tablet PC 编写的程序只有在 Tablet PC 或采用相应配置的开发计算机上才能达到最佳运行状态。开发计算机需要同时安装 Microsoft Windows XP Tablet PC Edition Software Development Kit 1.7 和 Microsoft Windows XP Tablet PC Edition 2005 Recognizer Pack（可从 Mobile PC Developer Center（英文）获得这两个软件）。造成这种现象的部分原因是对 Microsoft.Ink.dll 程序集的依赖，该程序集与 Windows XP Tablet PC Edition 2005 一同发布。因而，在尝试执行依赖于这些程序集存在的代码之前，有必要检查 Tablet PC 应用程序是否可以使用必需的库和功能。由于必须使用平台检测来执行存在性检查，因此，即使应用程序定义为仅在发现库的时候才对库进行加载和使用，亦需执行如此操作，

注意重新发布 tpcman17.msm 和 mstpcrt.msmneed 时并不需要检查 Tablet PC 二进制文件，但您需要保证只在运行 Windows XP Tablet PC Edition 2005 的计算机上部署应用程序。如果您无法重新发布 Tablet PC 二进制文件，并且是在没有 Tablet PC 二进制的计算机上部署应用程序，则需要执行这些检查以确保应用程序的正常运行。在某些情形下需要特别注意这一点，例如在应用程序包含手写控件且部署于网站时。

在随附的示例代码中，所有平台检测代码均包含在 PlatformDetection.cs 文件的 PlatformDetection 类中，该文件位于 Utilities 文件夹下。该类包含的代码可用来执行多个不同的检查，还可以将查询结果提供给应用程序的其余部分。

首先，在启动后不久，您的应用程序会检查是否有可用的 Microsoft.Ink.dll 程序集。首先编译来自 Microsoft.Ink.dll 程序集的代码引用类时，将隐式执行这项检查，但是您并不会希望这样，因为在您没有预计会发生异常时，可能会很难从 JIT 编译器引发的异常中进行正确恢复。另外一种方法是，您可以选择使用 Assembly.Load 和 Assembly.LoadWithPartialName 方法来进行显式搜索，以确定是否能找到有效的 Microsoft.Ink.dll 程序集。

public static bool InkAssemblyAvailable 
{
get { return _inkAssemblyAvailable; } 
}

private static bool _inkAssemblyAvailable = 
(LoadInkAssembly() != null);

private static Assembly LoadInkAssembly()
{
try 
  {
Assembly a = Assembly.Load(
"Microsoft.Ink, Version=1.7.2600.2180, " + 
"Culture=neutral, PublicKeyToken=31bf3856ad364e35");
if (a == null)
    {
a = Assembly.LoadWithPartialName(
"Microsoft.Ink, PublicKeyToken=31bf3856ad364e35");
if (a != null && a.GetName().Version < 
new Version("1.7.2600.2180")) a = null;
    }
return a;
  }
catch(IOException){}
catch(SecurityException){}
catch(BadImageFormatException){}
return null;
}

公共的静态 InkAssemblyAvailable 属性返回的值存储在一个私有静态布尔值中，该布尔值以调用 LoadInkAssembly 的返回值进行初始化。LoadInkAssembly 使用程序集的全名（包括版本号、区域性和公钥标记），通过反射 API 来加载 Microsoft.Ink 程序集。如果加载程序无法找到包含这些信息的程序集，则 LoadInkAssembly 会尝试使用部分名称来加载 Microsoft.Ink 程序集。也就是说，执行搜索时会省略一些程序集全名信息。在此示例中，我省略了版本号。这种思路是，Sudoku 实现程序可能会与更新版本的 Microsoft.Ink.dll 一起使用（例如，如果游戏在 Windows Vista 下运行该版本的 Tablet PC API），则通过省略版本号，我允许加载程序查找所有版本的程序集。当然，假设找到的每一版本都能符合要求未免有些不切合实际；游戏有可能在缺少某些功能支持的较旧版本上运行，而如果在此时 JIT 编译器尝试对缺失部分的使用进行编译的话，将会导致操作失败。为避免这种情况的发生，我做了一个更为安全的假设（也不是 100% 的安全），即只接受较新的版本。因此，在按部分名称加载程序集之后，我检查其版本号以确保是经过我编译的版本或较新版本。

经过验证还有一种更好的选择（我也实际使用过），就是让 CLR 以其标准逻辑来尝试找到并加载适当的 Microsoft.Ink.dll 程序集，然后对程序集不可用或无法加载的情况进行处理。我在前面已经提到，在您没有预计会发生异常时，通常很难从程序集和类型加载异常中恢复。但是当您意识到可能会发生异常，并在受控环境下充分利用它们时，凭借 CLR 的功能通常是最好的方法。我可以按照下列方法重新编写 LoadInkAssembly 来更改我的实现程序。

private static Assembly LoadInkAssembly()
{
try { return LoadInkAssemblyInternal(); }
catch(TypeLoadException) {}
catch(IOException){}
catch(SecurityException){}
catch(BadImageFormatException){}
return null;
}
[MethodImpl(MethodImplOptions.NoInlining)]
private static Assembly LoadInkAssemblyInternal()
{
return typeof(InkOverlay).Assembly;
}

回到程序的 Main 方法（位于 Program.cs 文件中），我使用 InkAssemblyAvailable 属性来确定是否应该继续执行。Main 之后会显示一个消息框，如不允许继续执行则会退出。

bool validSystem = PlatformDetection.InkAssemblyAvailable && 
PlatformDetection.RecognizerInstalled;
if (!validSystem)
{
MessageBox.Show(ResourceHelper.NotRunningOnTablet,
ResourceHelper.DisplayTitle, MessageBoxButtons.OK,  
MessageBoxIcon.Error, MessageBoxDefaultButton.Button1);
return 1;
}

请注意，我不仅要求了手写程序集，还要求安装识别程序。在典型的 Tablet PC 安装中，手写程序集和识别程序总是成对出现。但是，也有可能出现识别程序被删除的情况。在开发环境下也有可能在没有识别程序的情况下安装了 Tablet PC API。因此，我使用下列代码来检查具体的情况。

public static bool RecognizerInstalled
{
get
  {
if (!InkAssemblyAvailable) return false;
return GetDefaultRecognizer() != null;
  }
}

RecognizerInstalled 属性首先检查手写程序集是否可用。这一点非常重要，因为 RecognizerInstalled 属性用来查看识别程序是否可用的 GetDefaultRecognizer 实现程序，依赖于来自 Microsoft.Ink.dll 的类型。

[MethodImpl(MethodImplOptions.NoInlining)]
public static Recognizer GetDefaultRecognizer()  
{
Recognizer recognizer = null;
try 
  { 
Recognizers recognizers = new Recognizers();
if (recognizers.Count > 1)
    {
try { recognizer = recognizers.GetDefaultRecognizer(); }  
catch {}

if (recognizer == null)
      {
try 
        { 
recognizer =  
recognizers.GetDefaultRecognizer(1033);  
        }
catch {}
      }
    }
  }
catch {} 
return recognizer;
}

GetDefaultRecognizer 实例化 Microsoft.Ink.Recognizers（英文）集合，并确保其中至少有一个识别程序可用。然后它会使用该集合来检索默认的识别程序。如果出于某种原因而无法如此操作，将会尝试检索 LCID 1033（美国英语环境）的默认识别程序。（因为唯一由 Sudoku 执行的识别是针对整数的，这就已经足够了。）

请注意，我在 GetDefaultRecognizer 上使用了 System.Runtime.CompilerServices.MethodImplAttribute（英文），将其标记为保持原样而不进行内联。内联是指编译器选择将目标函数内容复制到一个调用场所，而非真正进行方法调用的过程。对于较小的方法，执行方法的成本主要取决于进行方法调用的开销，而内联则可以大幅提升性能。实际上，因为 GetDefaultRecognizer 方法中代码数量的问题，JIT 编译器几乎没有什么机会来执行内联过程。

不管怎样，我都不希望 GetDefaultRecognizer 进行内联。请记住，当 JIT 编译一个方法时，JIT 编译器会尝试加载所有包含方法所用类型的程序集。举例来说，当 JIT 编译 GetDefaultRecognizer 时，JIT 编译器将会尝试加载 Microsoft.Ink.dll。如果 GetDefaultRecognizer 已经内联至 RecognizerInstalled，则 JIT 编译 RecognizerInstalled 时，会在 RecognizerInstalled 有机会检查是否存在手写程序集之前进行加载尝试。因此，我在 GetDefaultRecognizer 上使用 MethodImplAttribute 来确保它不会进行内联。这使得 RecognizerInstalled 首先执行程序集的存在性检查。

该 Sudoku 实现程序支持使用擦除手势来清除玩家之前输入的数字。在大多数示例代码中，如果没有安装有效的手势识别程序，尝试支持手势功能将会导致异常现象的发生，但很遗憾的是，这些您根本看不到。因此，我还使用了 PlatformDetection 来检查是否安装有手势识别程序。

public static bool GestureRecognizerInstalled
{
get
  {
return InkAssemblyAvailable && 
GestureRecognizerInstalledInternal;
  }
}
private static bool GestureRecognizerInstalledInternal  
{
[MethodImpl(MethodImplOptions.NoInlining)]
get
  {
try
    {
Recognizers recognizers = new Recognizers();
if (recognizers.Count > 0)
      {
using(new GestureRecognizer()) return true;
      }
    }
catch {} 
return false;
  }
}

如 RecognizerInstalled 一样，GestureRecognizerInstalled 公共静态属性不会显式地执行这项检查。由于其对 Microsoft.Ink 程序集的依赖关系，它同样会依赖于标记为 NoInlining 的帮助者成员。GestureRecognizerInstalledInternal 属性检查是否存在识别程序。然后它显式实例化 Microsoft.StylusInput.GestureRecognizer（英文），返回是否能够成功创建一个 Microsoft.StylusInput.GestureRecognizer 的值。如果无法成功实例化，则会引发 InvalidOperationException（因此，try-catch 围住实例化部分），表明“The requested recognizer is not available with the current setup or configuration”（请求的识别程序在当前设置或配置下不可用）。

PlatformDetection 提供的最后一项功能，是确定用户的左右手使用习惯。Tablet PC 操作系统允许用户根据左手操作或右手操作来配置系统。应用程序可查询此设置并修改用户界面，以便最好地适应用户的左右手使用习惯。

public static bool UserIsRightHanded
{
get
  {
if (IsRunningOnTablet)
    {
bool rightHanded = true;
if (NativeMethods.SystemParametersInfo(
NativeMethods.SPI_GETMENUDROPALIGNMENT, 0,  
ref rightHanded, 0))
      {
return rightHanded;
      }
    }
return true;
  }
}
private static bool IsRunningOnTablet
{ 
get 
  {
return NativeMethods.GetSystemMetrics(
NativeMethods.SM_TABLETPC) != 0;  
  }
}

此属性首先检查当前系统是否为 Tablet PC。这里没有使用 InkAssemblyAvailable，因为手写程序集的存在并不代表系统就是 Tablet PC，因而也不代表此设置可供查询。相反，其依赖于 user32.dll 提供的 GetSystemMetrics 函数。

[DllImport("user32.dll", CharSet=CharSet.Auto)]
internal static extern int GetSystemMetrics(int nIndex);

提供了 SM_TABLETPC 值 (86) 之后，如果当前操作系统为 Microsoft Windows XP Tablet PC Edition，则此函数返回一个非零值，否则返回一个零值。在知道应用程序将在 Tablet PC 上运行后，我可以使用 user32.dll 提供的 SystemParametersInfo 函数来查询左右手使用习惯设置。用户首选项可通过 SPI_GETMENUDROPALIGNMENT 设置得以体现，对于相应的菜单栏项目，该设置确定是以左对齐还是右对齐的方式弹出菜单。

为 Ultra-Mobile PC 设计应用程序

最近 Microsoft 和许多 OEM 推出了 ultra-mobile PC (UMPC) 这一体积小巧的计算机，对于我们这些熟悉 Tablet PC 开发的人来说是一个绝好的机会。由于在 UMPC 上运行 Windows XP Tablet PC Edition，所以我们可以充分利用在 Tablet PC 方面的开发经验。这就意味着每一 UMPC 中都含有 API，必然需要开发成熟的手写输入应用程序。实际上，您为 Tablet PC 编写的应用程序应该可以毫无障碍地在 UMPC 上运行。但是，在为 UMPC 设备编写新软件或调整现有软件以期更佳的 UMPC 体验时，需要特别注意如下几点。

首先是 UMPC 的屏幕较小，通常为 800x480。这就需要您清楚了解应用程序要求什么类型的屏幕。此外，如果您的应用程序使用对象除了 UMPC 之外还有标准的 Tablet PC，则需要对应用程序进行精心设计，使之在不同的屏幕尺寸上都能达到最佳效果。我将在 Windows 窗体和硬件交互中讨论如何在 Sudoku 中处理这种情况。

今天大多数 Tablet PC 拥有的是电磁感应屏幕，可与专用手写笔进行复杂的检测与交互，而 UMPC 配备的是触敏式屏幕。这样的话设备使用起来就更为简便，用户用手指或其他指点设备就可以轻松地操作 UMPC。但是，由于大多数的触摸屏上缺少手掌误触防护，用户体验起来与配备电磁感应数字板的 Tablet PC 会有不同。所以在设计应用程序用户界面时一定要考虑到这一点。我的 Sudoku 支持多种交互方式。使用键盘或手写笔可以轻松地在游戏中输入数字，而且还提供了较大的数字按钮，这样操作起来就更为简单，只需用手指点击一个数字，然后轻触在 Sudoku 网格内的单元格，单元格中就会出现该数字。

另外一个需要密切注意的地方是 UMPC 中的手写笔只是一个简单的指点设备，而不是电磁感应设备。也就是说其应用程序不能像配备电磁感应数字板的 Tablet PC 那样，通过手写笔的交互接收到同样多的信息。因此为保证各项功能的正常运行，请确保专为 UMPC 设计的应用程序不要依赖于其他信息，如空中数据包或数字版压力。

最重要的一点是，您完全可以借鉴在 Tablet PC 方面的开发知识。您在设计和开发 UMPC 应用程序时如果能够考虑到这些方面，就可以为用户带来更好的体验。正如所见，我开发的 Sudoku 在标准 Tablet PC 和 UMPC 设备上都能正常运行。

代码访问安全性

乍看之下，可能会有人认为像 Sudoku 这样的游戏实现无需考虑什么安全问题，但实情却并非如此。作为一名开发人员，应该始终关注安全问题，关注应该为客户带来什么样的安全相关要求。

例如 Sudoku 中要用到几个 Win32 API。访问这些 API 要求有非托管代码权限。如果 Sudoku 是从本地驱动器运行、默认的代码访问安全性 (CAS) 设置被完整保留，那么就万无一失了。但是，如果有人试图以网络共享的方式运行 Sudoku 将会如何？默认情况下，不会向 Intranet 应用程序授予非托管代码权限。因此，当 Sudoku 试图访问这些非托管 API 时将会引发系统的安全异常。

与其在部分信任的环境下运行 Sudoku，还不如像大多数托管应用程序一样，让 Sudoku 在完全信任的环境下运行。而且，如果在部分信任的环境下运行 Sudoku，那么用户体验也会极其糟糕，应用程序将在玩家面前发生悲剧性的灾难。所以，Sudoku 在启动之后会明确查看是否为完全信任的环境，如果与当前环境不兼容则向用户发出警告。以下是启动 Sudoku 主方法的代码。

[STAThread]
public static int Main()
{
Application.EnableVisualStyles();
Application.DoEvents();
if (!HasFullTrust)
  {
MessageBox.Show(ResourceHelper.LacksMinimumPermissionsToRun,  
ResourceHelper.DisplayTitle, MessageBoxButtons.OK,  
MessageBoxIcon.Error, MessageBoxDefaultButton.Button1);
return 1;
}

Sudoku 会检查是否已经授予应用程序完全信任级别。如果没有，Sudoku 会向用户显示一个友好的错误对话框，然后退出。HasFullTrust 属性可通过如下代码实现。

private static bool HasFullTrust
{
get
  {
try
    {
new PermissionSet(PermissionState.Unrestricted).Demand();
return true;
    }
catch (SecurityException) { return false; }
  }
}

该属性将 System.Security.PermissionSet 实例化为不受限制、完全信任的访问，并请求该权限。如果所请求的权限不可用，则 Demand 方法会抛出 SecurityException。其结果是，此代码会被包装进 try 代码块之中。如果 Demand 方法成功，HasFullTrust 则返回 true。如果出现异常而失败，HasFullTrust 则返回 false。

还有一件有趣的事件需要注意，如果检查完全信任失败，则应用程序将会试图显示一个消息框。实际上还有一个控制是否可以显示消息框的权限。如果没有设置 SafeSubWindows 的 UIPermission，则在应用程序试图显示消息框时会收到安全异常。有几种方法可以解决这个问题。一种是捕获产生的异常并退出程序，但是这样的话用户不知道何处出现错误。他们会在 Microsoft Windows 资源管理器中双击该应用程序，但不会有任何响应（或者更确切地讲是看不到任何响应。Windows 会在后台启动该应用程序，然后在尚未显示任何可见线索之前退出。）因此，我将程序集对此 SafeSubWindows 权限的要求标记为最低限度。

[assembly:UIPermission(SecurityAction.RequestMinimum,  
Window=UIPermissionWindow.SafeSubWindows)]

这样，如果程序集未被授予此最低权限，CLR 将会显示其自有对话框，通知用户因缺少必要的权限而无法加载应用程序。如果授予了此最低权限，则会加载应用程序，同时我的逻辑会检查 Main 方法所取得的完全信任。

处理严重异常错误

Main 方法首先查看完全信任，然后验证 Microsoft.Ink 程序集可用并且识别程序已安装后，会调用另外一个方法 MainInternal，该方法用于完成主窗体的设置和启动等核心工作。MainInternal 激活应用程序的主消息循环；因此，游戏中所有来自用户界面交互的未处理异常均从 MainInternal 向外传播。为确保正确地记录这些异常（用于诊断和调试），Main 方法会捕获所有这些异常，将其记录然后退出。

try
{
return MainInternal() ? 0 : 1;
}
catch(Exception exc)
{
ShutdownOnException(new UnhandledExceptionEventArgs(exc, false));
return 1;
}
catch
{
ShutdownOnException(new UnhandledExceptionEventArgs(null, false));
return 1;
}

我使用 ShutdownOnException 方法来记录严重错误条件，以确保应用程序能够尽快关闭。

internal static void ShutdownOnException(UnhandledExceptionEventArgs e)
{  
try
  {
string message = (e.ExceptionObject != null) ?
e.ExceptionObject.ToString() : 
ResourceHelper.ShutdownOnError;
EventLog.WriteEntry(ResourceHelper.DisplayTitle, message,  
EventLogEntryType.Error);
  }
catch {}

try
  {
MessageBox.Show(ResourceHelper.ShutdownOnError,  
ResourceHelper.DisplayTitle, MessageBoxButtons.OK,  
MessageBoxIcon.Hand, MessageBoxDefaultButton.Button1);
  } 
catch {}
  
if (!e.IsTerminating) Environment.Exit(1);
}

在使用 .NET Framework 2.0 中提供的 System.Environment.FailFast 方法之后，可以很好的完成大多数操作，但是此实现是基于 .NET Framework 1.1 的。

ShutdownOnException 方法接受描述何处出现错误的 System.UnhandledExceptionEventArgs 参数。该方法首先尝试记录有关异常的信息（包括堆栈跟踪），使用 System.Diagnostics.EventLog.WriteEntry 静态方法将该信息写入应用程序事件日志中。然后会显示消息框，通知用户发生了意外。最后，如果应用程序仍未关闭，Environment.Exit 方法会终止运行。

综上所述，仅在主 UI 线程出现未处理异常时调用 ShutdownOnException。其他线程出现严重异常时怎么办？为解决这一问题，MainInternal 方法所要做的第一件事，就是将事件处理器与 AppDomain 的当前 UnhandledException 事件以及 Windows Form 的 Application.ThreadException 事件联系起来。

AppDomain.CurrentDomain.UnhandledException +=  
new UnhandledExceptionEventHandler(
CurrentDomain_UnhandledException);
Application.ThreadException +=  
new ThreadExceptionEventHandler(Application_ThreadException);

这些事件的事件处理器委托给 ShutdownOnException。

private static void Application_ThreadException(
object sender, ThreadExceptionEventArgs e)
{
ShutdownOnException(new UnhandledExceptionEventArgs(
e.Exception, false));
}
private static void CurrentDomain_UnhandledException(
object sender, UnhandledExceptionEventArgs e)
{
ShutdownOnException(e);
}

利用这些代码，用户在应用程序使用过程中遇到的所有故障或严重异常都会被记录下来，产品故障的调试工作将会更加轻松。请注意，在 .NET Framework 2.0 之下，这些工作大多数都是自动完成的。逐一解决运行过程中所有未处理异常之后，Dr. Watson 开始转储应用程序以便于日后的分析和调试。

单实例应用程序

许多应用程序，尤其是 Tablet PC 应用程序，大都是单实例应用程序。单实例应用程序是指，始终只有一个执行该应用程序的进程在运行的应用程序，无论是在特定桌面应用还是整个计算机中均是如此，取决于您对“单实例”的定义以及对应用程序的需求。对于 Sudoku，我想要计算机上的每个用户每次只能运行 Sudoku 的一个实例。如果使用 Microsoft Visual Studio 2005 和 .NET Framework 2.0 来实现 Sudoku，则单实例支持已经可用。但我使用的是 .NET Framework 1.1，所以还需其他工作才能实现单实例支持。有关单实例支持的详细信息，请参阅 .NET Matters column in MSDN Magazine's September, 2005 issue（英文）。

我的单实例支持内置于 SingleInstance 类中，位于 Utilities 文件夹的 SingleInstance.cs 文件中。MainInternal 按照下列方式使用 SingleInstance。

using(SingleInstance si = new SingleInstance())
{
if (si.IsFirst)
  {
//创建主窗体并运行应用程序
    ...

//成功完成游戏
return true;
  }
else
  {
//不是第一个 Sudoku 实例... 显示另外一个
si.BringFirstToFront();
return false;
  }
}

我首先创建一个新的类实例并查询其 IsFirst 属性，以确定该应用程序当前是否有其他实例正在运行。如果这是第一个实例，则应用程序继续正常运行，创建并显示应用程序的主窗体。如果这不是第一个实例，BringFirstToFront 方法会把 Sudoku 应用程序第一个实例的窗口转至前台，然后退出第二个实例。

单实例功能需要某种进程间通信 (IPC) 的方式，这是由于一个实例需要通知其他实例已经有实例存在，不应继续加载第二个实例。SingleInstance 类实际上依赖两个不同的 IPC 机制：进程间同步原语和内存映射文件。

创建单纯的单实例功能十分简单，只需几行代码即可完成。

static void Main()
{
string mutexName = "2ea7167d-99da-4820-a931-7570660c6a30";
bool grantedOwnership;
using(Mutex singleInstanceMutex =  
new Mutex(true, mutexName, out grantedOwnership)
  {
if (grantedOwnership)
    {
... //此处为核心代码
    }
  }
}

当双线程或更多线程同时访问共享资源时，您需要有同步机制来确保在某一时间点只有一个线程可以访问该资源。对于我们而言，“资源”的逻辑含义要比其物理上的含义广阔的多。它是保证正在运行的应用程序只有一个实例的能力。所谓 mutex，如在 System.Threading.Mutex 类中所实现的，是在某一时间点，仅向一个线程授予独占访问权限的同步原语。如果一个线程获得 Mutex，则暂停其他请求相同 Mutex 的线程，直到第一个线程释放 Mutex 为止。或者，在某一线程等待资源时不将其暂停，而是在其尝试获得 Mutex 时被告知该 Mutex 已被其他线程占用。

此处，以 GUID 名称创建 Mutex（所有使用此类代码的不同应用程序将会选择其唯一的名称）。在您使用某一名称创建 Mutex 之后，就可以用来同步存在于不同进程之间的线程，而每一进程都可以根据其预设和已知的名称来引用 Mutex。Mutex 的一个构造函数不仅接受名称，还接受 out 布尔参数，该参数用于指示 Mutex 是否实际可得。这样就可以轻松创建单实例功能。该代码会创建 Mutex 并检查其是否可用。如果 Mutex 可用，则该应用程序的实例就是第一个实例，可以继续进行。如果 Mutex 不可用，那么它就是第二个实例，应该退出。

在内部，SingleInstance 围绕相同的原则构建，但是稍有不同。首先，SingleInstance 不使用硬编码 GUID，而是基于当前应用程序中输入程序集的身份生成 ID。

private static string ProgramID
{
get
  {
Assembly asm = Assembly.GetEntryAssembly();
Guid asmId = Marshal.GetTypeLibGuidForAssembly(asm);
return asmId.ToString("N") + asm.GetName().Version.ToString(2);
  }
}

ID 是程序集类型库 GUID 和程序集版本的组合。按照下列方式使用 ID 来构造 Mutex 名称。

string mutexName = "Local\\" + ProgramID + "_Lock";

如同上一个简单的单实例示例，我的 SingleInstance 类构造函数对 Mutex 进行实例化，尽管是将其存储在成员变量而非本地变量中。

_singleInstanceLock = new Mutex(true, mutexName, out _isFirst);

构造函数的第三个参数是布尔变量，该变量用于存储此 Mutex 实例能否获得锁定，然后可以通过 IsFirst 属性访问该布尔值。

public bool IsFirst { get { return _isFirst; } }

SingleInstance 实现的 IDisposable.Dispose 会关闭 Mutex。

如果这正是所要求的功能，那么我的工作就基本上完成了。但是，在试图启动第二个实例时，许多单实例应用程序还会把现有实例转至前台。这一功能要求可在进程间传递附加信息。尤其是，除了检测是否已经存在实例外，第二个实例必须能够确定应将哪个进程转至前台。我注意到，一些应用程序是通过搜索桌面上具有特定名称的所有顶层窗口来完成这一任务，但这种方法不太可靠。我采用的是另外一种方式，内存映射文件。

对于我们的情况，可以将内存映射文件看作一种内存共享方式。这允许一个进程可以向内存中写入信息，供其他进程读取。特别是，应用程序的第一个实例可向内存映射文件中写入其进程 ID，然后第二个实例可以读取该进程 ID 并使用该 ID 将主实例转至前台。

private void WriteIDToMemoryMappedFile(uint id)
{
_memMappedFile = new HandleRef(this,  
NativeMethods.CreateFileMapping(new IntPtr(-1), IntPtr.Zero,  
PAGE_READWRITE, 0, IntPtr.Size, _memMapName));
if (_memMappedFile.Handle != IntPtr.Zero &&  
_memMappedFile.Handle != new IntPtr(-1))
  {
IntPtr mappedView = NativeMethods.MapViewOfFile(
_memMappedFile.Handle, FILE_MAP_WRITE, 0, 0, 0);
try
    {
if (mappedView != IntPtr.Zero)  
Marshal.WriteInt32(mappedView, (int)id);
    }
finally
    {
if (mappedView != IntPtr.Zero)  
NativeMethods.UnmapViewOfFile(mappedView);
    }
  }
}

private uint ReadIDFromMemoryMappedFile()
{
IntPtr fileMapping = NativeMethods.OpenFileMapping(
FILE_MAP_READ, false, _memMapName);
if (fileMapping != IntPtr.Zero && fileMapping != new IntPtr(-1))
  {
try
    {
IntPtr mappedView = NativeMethods.MapViewOfFile(
fileMapping, FILE_MAP_READ, 0, 0, 0);
try
      {
if (mappedView != IntPtr.Zero) 
return (uint)Marshal.ReadInt32(mappedView);
      }
finally
      {
if (mappedView != IntPtr.Zero)  
NativeMethods.UnmapViewOfFile(mappedView);
      }
    }
finally { NativeMethods.CloseHandle(fileMapping); }
  }
return 0;
}

类似于进程间的互斥锁，也可以命名内存映射文件，以便多个进程通过该名称访问。可使用 kernel32.dll 提供的 CreateFileMapping 函数创建内存映射文件。然后使用同样由 kernel32.dll 提供的 MapViewOfFile 函数将内存映射文件映射到当前地址空间。MapViewOfFile 为内存提供起始地址，然后与来自 System.Runtime.InteropServices.Marshal 类的方法一起使用，读取内存中的数据以及向内存中写入数据。如果已经创建了内存映射文件，您可以使用来自 kernel32.dll 的 OpenFileMapping 函数打开该文件。

[DllImport("Kernel32", CharSet=CharSet.Auto, SetLastError=true)]
internal static extern IntPtr CreateFileMapping(IntPtr hFile,  
IntPtr lpAttributes, int flProtect, int dwMaxSizeHi,  
int dwMaxSizeLow, string lpName);

[DllImport("Kernel32", CharSet=CharSet.Auto, SetLastError=true)]
internal static extern IntPtr OpenFileMapping(int dwDesiredAccess,  
[MarshalAs(UnmanagedType.Bool)] bool bInheritHandle,  
string lpName);

[DllImport("Kernel32", CharSet=CharSet.Auto, SetLastError=true)]
internal static extern IntPtr MapViewOfFile(IntPtr hFileMapping,  
int dwDesiredAccess, int dwFileOffsetHigh, int dwFileOffsetLow,  
int dwNumberOfBytesToMap);

[DllImport("Kernel32", CharSet=CharSet.Auto, SetLastError=true)]
[return:MarshalAs(UnmanagedType.Bool)]
internal static extern bool UnmapViewOfFile(IntPtr pvBaseAddress);

[DllImport("kernel32.dll", SetLastError=true)]
[return:MarshalAs(UnmanagedType.Bool)]
internal static extern bool CloseHandle(IntPtr handle);
 

SingleInstance 构造函数创建 Mutex 并验证其是否为第一个实例。如果是第一个实例，SingleInstance 构造函数使用 WriteIDToMemoryMappedFile 方法来存储自己的进程 ID，以供第二个实例随后检索之用。当第二个实例开始运行并调用 BringFirstToFront 方法时，第二个实例首先使用 ReadIDFromMemoryMappedFile 来访问主实例的进程 ID。可将该进程 ID 与 user32.dll 提供的 ShowWindowAsync 和 SetForegroundWindow 函数结合使用，将主实例转至前台。

public void BringFirstToFront()
{
if (!_isFirst)
  {
uint processID = ReadIDFromMemoryMappedFile();
if (processID != 0)
    {
const int SW_SHOWNORMAL = 0x1;
const int SW_SHOW = 0x5;
IntPtr hwnd = new ProcessInfo(processID).MainWindowHandle;
if (hwnd != IntPtr.Zero)
      {
int swMode = NativeMethods.IsIconic(new HandleRef(
this, hwnd)) ?SW_SHOWNORMAL :SW_SHOW;
NativeMethods.ShowWindowAsync(hwnd, swMode);
NativeMethods.SetForegroundWindow(new HandleRef(
this, hwnd));
      }
    }
  }
}

Sudoku 算法

本部分将对 Sudoku 游戏特有的应用程序特征方面进行详细阐述。

维护游戏状态

编写这样的应用程序时，我会首先确定尽可能少的一组功能，将其作为以后工作的基础。具体到 Sudoku，就是首先创建必要的数据结构，以保存游戏状态。

可以简单地将填数游戏表示为一个二维数组。每个单元格必须能存储一个数字，或者为空。.NET Framework 2.0 能够提供可以为空的类型这种形式，从而给我们带来了一种良好的解决方案。.NET Framework 2.0 中“可以为空的类型”允许值类型也为空值，这代表着它使用了一种新的泛型结构：Nullable<T>。Nullable<T> 可以在内部保存两个值，一个是类型 T（在这里，T 是一个泛型类型参数，可以为任意的值类型，但不能为另一个可以为空的类型），存储的是实例的值；另一个是布尔型，表明该实例是否有值。.NET Framework 1.1 中不能使用泛型，但我还有其他办法。对于几个想要支持空值的类型，我可以创建自己的替代类型，如 NullableByte 和 NullableInt。每种替代类型都是一种包含相关类型的值（如 byte 适用于 NullableByte，int 适用于 NullableInt）和一个布尔值的结构，布尔值表示整数值中是否含有可用值。这虽然没有 .NET Framework 2.0 的泛型解决方案那么高明，从 C# 2.0 提供对 Nullable<T> 的语法支持之后更是如此，但就实现我的目标而言，已经足够了。游戏网格中的每个单元格或者为空，或者是一个较小的数值，所以我可以按照一个 NullableBytes 数组来保存网格。

[Serializable]
public sealed class PuzzleState :ICloneable, IEnumerable
{
private NullableByte[,] _grid;
private readonly byte _boxSize;
private readonly byte _gridSize;
  ...
}

PuzzleState 类包含几条信息，包括网格的大小和内容。目前的实现程序仅支持 9x9 Sudoku 网格，但是经完善后，该应用程序可以获得扩展，能够支持更大的网格，甚至是非正方形网格。

PuzzleState 最重要的特征之一是 ICloneable接口的实现。该接口实现后，您可以轻松地进行 PuzzleState 实例的深拷贝，将其深入应用到解决方案的其他各个方面，如游戏解法、游戏生成，甚至还可以用在与游戏相关的功能中，如撤消支持。

object ICloneable.Clone() { return this.Clone(); }
public PuzzleState Clone() { return new PuzzleState(this); }
private PuzzleState(PuzzleState state)
{
  _boxSize = state._boxSize;
  _gridSize = state._gridSize;
  _grid = (NullableByte[,])state._grid.Clone();
  ...
}

分析和完成填数游戏

完成 Sudoku 填数游戏的过程实际上是一个特殊的搜索过程，因此，我可以将标准的搜索算法运用到游戏当中。一种常见的搜索算法是深度优先搜索 (DFS)，在大学的数据结构和算法课程中，这通常是首先要学的算法之一。搜索时，有的实例需要探寻多条路径，在 DFS 中，要对其中一条路径进行整体探寻，包括由该路径引出的所有路径，然后再依次检查其他路径。虽然可以使用显式堆栈的方式执行 DFS，但我们通常使用递归法。假设在一个树节点数据结构中，除一列子节点外，还存储有一个值。可以通过如下方式对树内一个具体值执行 DFS 过程：

public class TreeNode<T> where T :IComparable
{
public TreeNode(T value) { Value = value; }
public T Value;
public List<TreeNode<T>> Children = new List<TreeNode<T>>();

public TreeNode<T> DfsSearch(T v)
  {
if (Value.CompareTo(v) == 0) return this;
foreach (TreeNode<T> child in Children)
    {
TreeNode<T> rv = child.DfsSearch(v);
if (rv != null) return rv;
    }
return null;
  }
}

在 TreeNode<T> 上调用 DfsSearch 以检查节点内存储的值是否与要搜索的值相同。如果相同，即返回当前的节点。如果不同，则调用每个子节点的 DfsSearch 方法，检查要搜索的值是否存在于该子节点的子树上。通过这种方式，我可以搜索整个树结构。

您可以用相同的方式搜索 Sudoku 的解法。将游戏盘的一个具体状态当作树内的一个节点。以该状态为起点，我可以在网格中的空单元格内输入一个数字，转到其他“子”状态。通过这种方式，我可以从每个状态达到一定数量的子状态（每在一个空单元格中输入一个值，即得到一个状态）。对于 9x9 的网格，最多有 729 个子状态，这是一个确定的数值。因此，我可以使用很少的 DFS 类似代码对 Sudoku 游戏的解法执行搜索。

static PuzzleState DfsSolve(PuzzleState state)
{
switch (CheckSolution(state))
  {
case PuzzleStatus.Solved:return state;
case PuzzleStatus.CannotBeSolved:return null;
default:
NullablePoint cell = FindFirstEmptyCell(state);
if (cell == null) return null;
for (byte n = 0; n < state.GridSize; n++)
      {
state[cell.Value] = n;
PuzzleState result = DfsSolve(state);
if (result != null) return result;
      }
state[cell.Value] = null;
return null;
  }
}

这种方法与 Sudoku 实现程序的部署方法类似，检查 PuzzleState 并确定是否已完成；当前是否处于无效状态（指存在冲突）并且已确定无法完成；或者是否仍有一个处于进程中的未完成游戏。执行这一检查与 TreeNode<T> 的 DfsSearch 检查类似，主要是看已找到的节点中是否包含正确值，以及检查是否存在解的位置。如果找到一个解，即将其返回。如果找到的是一个无效状态，则说明在某处出错，需要原路返回。如果游戏仍在继续，需要在一个空单元格中输入一个数字。找出首个为空的单元格，依次输入每个可能值。如果该游戏有解，其中某个值一定是正确的。我在每个单元格中输入一个数字，然后递归调用 DfsSolve。只要游戏有解，最后就一定能够找到。

遗憾的是，这种方法有一个致命的缺点：完成游戏需要相当长的时间。对于 9x9 的游戏盘，需要为每个单元格试填的值最高为九个。对于需要填充 81 个单元格的游戏盘，需要试填的盘数高达 9⁸¹。即使速度达到每十亿分之一秒处理一个单元格中的一个数字，结果也很恐怖，我和各位读者都不可能在有生之年看到游戏结束！事实上，找到解之前，太阳都可能已经不复存在了。问题的症结在于，这种方法需要搜索整个搜索空间，即使可以通过许多办法对搜索树进行“修枝剪叶”，例如限制搜索必须执行的寻找数量，但对于缩短时间来说，这些都是杯水车薪。我们玩 Sudoku 游戏时都知道有许多步骤是不必进行的，那为什么还要让计算机去试呢？所以，丢掉它们！

我们可以通过许多技巧让计算机省去一些步骤，其中最简单的一种是，通知计算机某个具体的单元格中一定不会含有哪些数字。这样，计算机进行强力搜索时只需要考虑剩余的可能数字。

对网格内的每个单元格，我会保留一个位数组。这里有一种思路，即通过检查其他自动设置数字，或者单元格的列、行和框中已“给出”的数字，为每个单元格排除一定量的可能数字；已出现的任何数字都不可能是该单元格中应有的数字。原则上，位数组是一组开关，通过打开或关闭来维护一组项目的布尔值。在.NET Framework 中表示位数组的最简便方法是使用 System.Collections.BitArray 类。但是，我在实现程序中使用该类并进行了一些配置文件测试之后，我发现创建适合具体要求的新的实现程序更为方便。所以，我创建了自己的实现程序 FastBitArray，它位于 Collections 目录下的 FastBitArray.cs 文件中。（如果您编写过位桶，就会对该实现程序非常熟悉。）因为 Sudoku 实现程序不需要处理大的值（假定其仅支持 9x9 游戏盘），FastBitArray 就可以对单一无符号整数进行限制，只允许最多保留 32 个布尔值。通过简单的位操作即可实现读写操作。

public bool Get(int index)  
{
return (_bits & (1u << index)) != 0;
}
public void Set(int index, bool value)  
{
bool curVal = Get(index);
if (value && !curVal)  
  {
_bits |= (1u << index);
_countSet++;
  }
else if (!value && curVal)
  {
_bits &= ~(1u << index);
_countSet--;
  }
}

之后，我会保留一个 FastBitArray 实例的二维数组，与包含网格中各单元格的值的二维数组相对应。

了解单元格中的可能值可以使 DfsSolve 方法更快地发挥作用。我可以将搜索限制在各单元格的备选值中，而不必像以前那样，在每个单元格中试填所有值。此外，通过 DfsSolve 实现程序查找并填充找到的第一个空单元格，这其实是一个误导。在具体单元格内试填的值中只有一个是正确的，这就给了我们一种启示：如果从我们知道的备选数字最少的单元格开始，将能够省去大量的搜索工作。因此，要进一步完善 DfsSolve，可以在所有空单元格中找出备选数字最少的单元格。在 DfsSolve 中每设定一个单元格，随即更新备选数字的数组，删除已经为单元格设置的备选数字。

创建 DfsSolve 是为了说明与解释，实际上，我用在 Sudoku 中的实现程序与之非常相似。在 Solver.cs 文件中，我的 Solver 类中有这两个核心方法的简略版本。请留意它们与 DfsSolve 的相似之处，以及我提到的补充建议。

private static SolverResults SolveInternal(
PuzzleState state, SolverOptions options)
{
state = state.Clone();

FastBitArray [][] possibleNumbers =  
FillCellsWithSolePossibleNumber(state,  
options.EliminationTechniques);

switch (state.Status)
  {
case PuzzleStatus.Solved:
case PuzzleStatus.CannotBeSolved:
return new SolverResults(state.Status, state, 0);
default:
if (options.AllowBruteForce)
      {
SolverResults results = BruteForceSolve(
state, options, possibleNumbers);
return results;
      } 
else return new SolverResults(
PuzzleStatus.CannotBeSolved, state, 0, null);
  }
}

private static SolverResults BruteForceSolve(PuzzleState state,  
SolverOptions options, FastBitArray [][] possibleNumbers)
{
//找到备选数字最少的单元格
ArrayList bestGuessCells = new ArrayList();
int bestNumberOfPossibilities = state.GridSize + 1;
for (int i = 0; i < state.GridSize; i++)
  {
for (int j = 0; j < state.GridSize; j++)
    {
int count = possibleNumbers[i][j].CountSet;
if (!state[i, j].HasValue)
      {
if (count < bestNumberOfPossibilities)
        {
bestNumberOfPossibilities = count;
bestGuessCells.Clear();
bestGuessCells.Add(new Point(i, j));
        }
else if (count == bestNumberOfPossibilities)
        {
bestGuessCells.Add(new Point(i, j));
        }
      }
    }
  }

//选择一个
SolverResults results = null;
if (bestGuessCells.Count > 0)
  {
Point bestGuessCell = (Point)bestGuessCells[
RandomHelper.GetRandomNumber(bestGuessCells.Count)];
FastBitArray possibleNumbersForBestCell = possibleNumbers[
bestGuessCell.X][bestGuessCell.Y];
for(byte p=0; p<possibleNumbersForBestCell.Length; p++)
    {
if (possibleNumbersForBestCell[p])
      {
PuzzleState newState = state;
newState[bestGuessCell] = p;
SolverOptions tempOptions = options.Clone();
if (results != null)  
        {
tempOptions.MaximumSolutionsToFind = (uint)(
tempOptions.MaximumSolutionsToFind.Value a