Dancing Links 库

• 下载源代码 - 46.8 KB

引言

这是一个 VB.NET 库，包含使用跳舞链解决精确覆盖问题的所有必要类。演示项目展示了如何使用该库解决数独问题。

背景

两年前，我开始解决数独问题，这仍然是我最喜欢的消磨时间的方式之一。在互联网上搜索任务时，我发现了top 95 数独。没有给出解决方案，当我尝试解决它们时，我经常发现在解决的早期阶段犯了一个错误。为了验证部分解决方案，我需要解决方案，当时找不到求解器。

在搜索解决方案方法时，我发现了Knuth 的跳舞链算法。我将 Knuth 算法转换为对象时遇到问题，直到我找到了Stan Chesnutt 的 Java 实现。将 Java 代码转换为 VB 很容易。起初，程序不起作用，但在查阅了 Knuth 的论文并进行了一些调整后，我设法解决了这个问题。

起初，解决时间因任务而异，在某些情况下，长达两分钟，这是不可接受的。当我更改了选择列的顺序，以便先处理行数最少的列时，我设法在不到一秒的时间内解决了尝试的任何任务。实际上，Knuth 建议进行这样的列选择，除非先前对列进行了排序以加速求解。

虽然跳舞链库或多或少是从 Java 转换而来的，但它已经得到改进和扩展，并且通过演示程序证明是有效的。我使用了 Chesnutt 的命名，我发现这非常方便。

使用代码

该库由三个类组成

• DancingNode (跳舞节点)
• DancingColumn (跳舞列)
• DancingArena (跳舞竞技场)

解决实际问题的类必须扩展 DancingArena 类。用户应该只编写类的构造函数和 HandleSolution 过程。SudokuArena 类是此类扩展的一个例子。演示项目展示了如何使用 SudokuArena 类。您可以打开以 XML 或文本文件保存的数独并解决它。程序显示解决方案的数量和第一个有效解决方案。

该库允许一些有用的设置。我们可以设置是否应该保存所有解决方案，或者仅保存第一个解决方案，或者不保存解决方案（如果我们想知道解决方案的数量）。我提供了一些数独任务 (4.1 KB)，以不同的格式供您使用。

DancingArena 类通过构造函数进行扩展，从而可以使用辅助列来解决类似于八皇后等问题。QueenArena 类展示了如何使用跳舞链解决八皇后问题。

关注点

我在我的项目“另一个数独求解器”中使用了跳舞链库。它被证明对于快速验证是否存在唯一解很有用。

数独任务的表示格式有很多种，其中很多没有提供非方形任务表示。长期以来，我一直在使用 XML 存储数据，因此我决定制作一个规范 (76 KB)，用于将数独任务和解决方案存储在 XML 文件中。在我的演示项目中，包含了规范和模式定义。我想将此规范公开，如果有感兴趣的各方，我很乐意继续与他们一起进行规范项目。

历史

• 2007-07-04：版本 1.0。