挂画谜题

poe

Erik D. Demaine的挂画谜题论文预印本终于出来了。此谜题极为精彩，既有简单的原始版本，又有非常一般的推广形式。如论文所述，它将以下领域联系起来：puzzles, magic, topology, Borromean rings, Brunnian links, group theory, free groups, monotone Boolean function theory, circuit complexity, AKS sorting networks, combinatorics, and algorithms.
论文地址：http://arxiv.org/pdf/1203.3602v1.pdf

（简单形式参见http://www.matrix67.com/blog/archives/3930 及http://blog.sina.com.cn/s/blog_8d1adcb301010aq1.html）

poe

那篇论文只解决了很简单的情形。Erik 的这篇既是很好的综述，也给出了最一般情形的数学和算法理论。

[ 本帖最后由 poe 于 2012-4-16 23:21 编辑 ]

Cielo

M67博客里也给了个链接http://jedidiah.stuff.gen.nz/link_problem.pdf
不知两篇的内容差别大不大。————————————————————————————————

回楼下：
了解了，那看一楼链接里的这篇就行了！

[ 本帖最后由 Cielo 于 2012-4-16 22:45 编辑 ]

sokoban

看上去很有趣，下回来慢慢看。