algorithm - Knuth 的 Dancing Links 算法的数据结构

Question

如果我的问题听起来很愚蠢，我很抱歉，因为我对数据结构的理解不是很好。

我一直在阅读 Knuth's Dancing Links算法并且非常了解它的基本工作原理。提到 dancing link 的数据结构可视化看起来像一个包含列和行的表格，每个单元格都连接到它们的上、下、左和右单元格。我还读到该算法中使用了循环双链表。

我想知道的是如何将双链表做成这样的列和行表？

据我所知，大多数双向链表只有 2 个指针(向上和向下)，这是否意味着我必须制作自己的自定义链表，它有 4 个指针(向上、向下、向左和向右) ？还是有其他方法？

提前致谢。

Answer 1

该算法对每一行和每一列都使用一个双向链表，而不仅仅是一个列表。

这article on using dancing links to solve sudoku有一张漂亮的照片。

至少在本文的代码中，行确实表示为左右指针，列表示为同一节点中的上下指针，或多或少如您所述，因此列表是相互关联的。