跳舞链接库(译文)
By robot-v1.0
本文链接 https://www.kyfws.com/games/dancing-links-library-zh/
版权声明 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
- 4 分钟阅读 - 1970 个词 阅读量 0跳舞链接库(译文)
原文地址:https://www.codeproject.com/Articles/19630/Dancing-Links-Library
原文作者:Miran.Uhan
译文由本站 robot-v1.0 翻译
前言
A VB.NET library with all necessary classes for exact cover solving with dancing links.
一个VB.NET库,其中包含所有必需的类,用于通过跳舞链接精确地解决封面问题.
介绍(Introduction)
这是一个VB.NET库,其中包含用于通过Dancing Link解决确切的封面问题的所有必需类.该演示项目展示了如何使用该库求解Sudoku.(This is a VB.NET library with all the necessary classes for exact cover problem solving with Dancing Links. The demo project shows how to use the library for solving Sudoku.)
背景(Background)
两年前,我开始解决数独问题,而数独仍然是我业余时间的最爱之一.在互联网上搜索任务时,我发现(Two years ago, I started solving Sudoku which is still one of my favorites for spending free time. When searching the internet for tasks, I found the) 95数独(top 95 Sudokus) .没有给出解决方案,当试图解决它们时,我经常发现我在解决方案的早期阶段犯了一个错误.为了验证零件解决方案,我需要解决方案,但当时找不到求解器.(. There were no solutions given, and when trying to solve them, I often figured out I made a mistake in some earlier stage of solving. To verify part solutions, I needed the solutions and couldn’t find a solver at that time.) 在寻找解决方法时,我发现(When searching for methods for solving, I found) Knuth的跳舞链接算法(Knuth’s Dancing links algorithm) .在找到Knuth算法到对象之前,我一直遇到问题(. I had problems transferring Knuth algorithms to objects till I found) Stan Chesnutt的Java实现(Stan Chesnutt’s Java implementation) 该算法.将Java代码转换为VB很容易.最初,该程序无法正常工作,但是在查阅了Knuth的论文并进行了一些调整之后,我设法将其解决.(of this algorithm. Converting Java code to VB was easy. At first, the program didn’t work, but after consulting Knuth’s paper and making some adjustments, I managed to work it out.) 刚开始时,解决时间因任务而异,有时甚至是无法接受的两分钟.当我更改列的选择顺序,以便首先处理行数最少的列时,我设法在不到一秒钟的时间内解决了我尝试的任何任务.实际上,Knuth建议选择这样的列,除非对列进行了先前的排序以加快求解速度.(At the beginning, the solving time varied very much from task to task, in some cases, to an unacceptable two minutes. When I changed the order of the selection of the columns so that the columns with the smallest number of rows are handled first, I managed to solve in times less than a second for any task I tried. Actually such a columns selection is advised by Knuth, except when a previous ordering of columns is done to speed up solving.) 尽管Dancing Links库或多或少是从Java转换而来的,但它已得到改进,扩展和运行,并已通过演示程序证明.我使用了Chesnutt的命名方式,觉得很方便.(Though the Dancing Links library is more or less converted from Java, it has been improved, extended, and works, proven with the demo program. I used Chesnutt’s naming, which I find very convenient.)
使用代码(Using the code)
该库包含三个类:(The library consists of three classes:)
DancingNode
DancingColumn
DancingArena
解决实际问题的课程必须扩展(Classes for solving the actual problems must extend the)DancingArena
类.用户只应编写类的构造函数,(class. The user should only write the class constructor and the)HandleSolution
程序.的(procedure. The)SudokuArena
class是此类扩展的示例.该演示项目展示了如何使用(class is an example of such an extension. The demo project shows how to use the)SudokuArena
类.您可以打开保存在XML或文本文件中的Sudoku并解决它.该程序将显示解决方案的数量和第一个有效的解决方案.(class. You can open a Sudoku saved in an XML or text file and solve it. The program show the number of solutions and the first valid solution.) 该库允许一些有用的设置.我们可以设置是否应保存所有解决方案,或仅保存第一个解决方案,或者不保存(如果我们想知道解决方案的数量).我提供了一些(The library allows some useful settings. We can set whether all solutions, or only the first solution, or no solution (in case we want to know the number of solutions) should be saved. I have provided some) 数独任务(4.1 KB)(Sudoku tasks (4.1 KB)) 以不同的格式播放.(in different formats to play with.) 的(The)DancingArena
类通过构造函数扩展,从而允许使用辅助列来解决8个皇后之类的问题.班级(class is extended with the constructor, enabling the use of secondary columns to enable use in solving problems like 8 queens. The class)QueenArena
展示了如何使用Dancing Links解决8个皇后区问题.(shows how to solve the 8 queens problem with Dancing Links.)
兴趣点(Points of interest)
我在我的项目"另一个Sudoku求解器"中使用The Dancing Link库.它被证明可用于快速验证是否只有一个解决方案.(I’m using The Dancing Link library in my project “Yet another Sudoku solver”. It proves useful for fast verification of if there exists one and only one solution.) Sudoku任务演示的格式很多,其中许多不提供非正方形任务表示.很长时间以来,我一直在使用XML来存储数据,因此我决定制作一个(There are many formats for Sudoku task presentation, and many of them don’t provide non-square task representations. For a long time, I’ve been using XML for storing data, so I decided to make a) 规格(76 KB)(specification (76 KB)) 将Sudoku任务和解决方案存储在XML文件中.在我的演示项目中,包括规范和架构定义.我想公开此规范,如果有感兴趣的人士,我很乐意与他们继续进行规范项目.(to store Sudoku tasks and solutions in an XML file. In my demo project, the specification and schema definition are included. I would like to make this specification public, and if there are interested parties, I would be happy to continue the specification project with them.)
历史(History)
- 2007-07-04:版本1.0.(2007-07-04: Version 1.0.)
许可
本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。
VB VB8.0 .NET1.1 .NET2.0 .NET3.0 .NET1.0 VS2005 Visual-Studio VS.NET2003 Dev 新闻 翻译