按年被提到
20002013 · 3 次2026
算法与数据结构›经典算法与数据结构·arXiv:cs/0011047 · cs.DS

Dancing links

舞蹈链
Donald E. Knuth · 2000

用双向链表的可逆操作加速精确覆盖类回溯搜索

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 14 人首次 2009-05-29 · 最近 2026-09-30
14不同的人
16活跃月份
16讨论串
242被引(OpenAlex)

Knuth 介绍两个加速组合谜题深度优先搜索的技巧:一是用双向链表上可逆的局部操作实现搜索中的每一步假设,使数据随搜索增量变化;二是为每块拼图增加一个幽灵格,使每块只用一次与每格只盖一次的规则地位相同,从而归结为 0-1 整数规划的抽象形式。他还报告了在 19 块 hexiamond 铺六边形和最多 18 皇后问题上的优异性能。

HN 为什么提它

HN 上的人常把它当作写得漂亮、好读的经典算法论文来推荐,用它解数独等精确覆盖问题,并称它展示了链表这种简单数据结构的威力。

方法难度 2 / 5约 30 分钟经得起时间
读之前最好知道
1双向链表(doubly linked list)
2回溯搜索(backtracking)
3精确覆盖问题(exact cover)
4基本的算法分析

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
强烈推荐ChrisLomont · 2015-07

“It's amazingly useful for solving such problems, for enumerating all solutions, and it is fast and completely general.”

强烈推荐:求解这类问题和枚举全部解都极有用,快速且通用
How wooden puzzles can destroy dev teams原评论 ↗
推荐relaunched · 2013-05

“Lots of fun and is a weekender, but you can expand it to solve anything from sudoku to all kinds of tiling problems.”

推荐作周末读物,可扩展到数独和各种铺砌问题,很有趣
Ask HN: Practical CS papers you've read and would recommend?原评论 ↗
推荐johnsonjo · 2017-12

“very well written and a somewhat easy read”

推荐它,行文清晰、读起来不难
Ask HN: What was the best CS paper you read in 2017?原评论 ↗
推荐dragontamer · 2021-03

“Seriously, study the algorithm before hating on it.”

劝人先认真学这个算法再去批评它
Drop millions of allocations by using a linked list (2015)原评论 ↗
推荐sprawld · 2022-11

“Donald Knuth's Dancing Links paper is a beautiful exploration of the power of linked lists.”

推荐 Knuth 这篇论文,是对链表威力的精彩探索
In defense of linked lists原评论 ↗
推荐OskarS · 2025-09

“He presented an earlier version of the algorithm in this legendary article”

指出 Knuth 在这篇传奇文章中给出了该算法的早期版本
Solving a wooden puzzle using Haskell原评论 ↗
看全部 12 条 →
推荐ventana · 2026-08

“For anyone interested in solving sudokus, I recommend reading Knuth's Dancing Links paper [1]”

向想解数独的人推荐 Knuth 这篇论文
Simple Sudoku Solvers原评论 ↗
推荐csense · 2026-09

“I suggest implementing your own version of these two interesting, satisfying algorithms”

建议自己动手实现 Algorithm X 和 Dancing Links 这两个有趣的算法
Solving a corn puzzle with CP-SAT原评论 ↗
引用Someone · 2013-02

“Real programmers implement Knuth's dancing links and use it to solve a way larger class of problems.”

调侃真正的程序员会实现舞蹈链,并用它解决大得多的一类问题
All N-Rooks algorithm and a linear time N-Queens solution原评论 ↗
引用carapace · 2018-10

“Dancing Links (Knuth's paper: Dancing links )”

列出 Knuth 的舞蹈链论文,作为精确覆盖问题的技术
Ask HN: What's your favorite elegant/beautiful algorithm?原评论 ↗
引用pge · 2019-09

“Here's the paper describing the algorithm: Dancing links”

给出描述该算法的论文,可用于精确覆盖如数独
Solving Every Sudoku Puzzle (2006)原评论 ↗
引用carapace · 2021-01

“FWIW, "Dancing Links" is a wonderful technique that would be worse than pointless in an immutable language.”

指出舞蹈链是妙招,但在不可变语言里毫无意义
Haskell is our first choice for building production software systems原评论 ↗
被提交为 story · 4 次