书接上回，我们考虑如何构造这个游戏。这里就是研究如何构造一个7阶的Finite Projective Plane。这篇的内容，大量参考 The what, how and why of Finite projective planes。然后我又找到了一个更好的视频资料：Module 4: Projective and Affine Planes。

我时不时会浏览一些大佬的个人主页(如Knuth和Sedgewick)，好久好久之前我就看到了Sedgewick关于HyperBitBit的研究了，一直就等他论文发表了。后来才想，不会这大爷忘了更新主页吧，去搜其他合作者，果然，论文刚刚都发布了。本文先罗列资料，然后再贴我的分析笔记。

• 论文代码仓库：https://github.com/robert-sedgewick/hyperbitbit
• Sedgewick教授个人主页关于基数估计的部分：https://sedgewick.io/research/#cardinality
• 2022年Sedgewick关于基数估计的一个talk: https://www.birs.ca/events/2022/5-day-workshops/22w5004/videos/watch/202211140856-Sedgewick.html
• 上面talk的slide：https://www.birs.ca/workshops/2022/22w5004/files/Bob%20Sedgewick/HyperBit.pdf
• Paper: Janson, Svante, Jérémie Lumbroso, and Robert Sedgewick. “Bit-Array-Based Alternatives to HyperLogLog.” 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2024.
• Paper Link: https://www2.math.uu.se/~svantejs/papers/sj383-aofa.pdf
• Sedgewick教授个人主页里的talk的 https://sedgewick.io/talks/
  • LogLog Counting of Large Cardinalities Marianne Durand and Philippe Flajolet
  • Cardinality Estimation

华容道之水，不下赤壁。—— 孔明(火凤燎原)

问题

慕慕妈妈给慕慕外卖凑单，多买了一个华容道游戏。

看到这种面板，脑子里自然而然的涌现几个问题：

1. 所有可能的排列有多少种？分别是什么？
2. 所有可能的关卡有多少种？分别是什么？（有答案的排列才能称之为关卡）
3. 给定一个关卡，怎么写一个程序自动求解？

针对这些问题，一个一个的解决。所有代码和数据文件在 https://github.com/kainwen/misc/tree/main/dancing_links

Knuth教授的第28届圣诞讲座的视频：Stanford Lecture: Dr. Don Knuth – Strong Components and Weak Components (2024)，这引导我们继续去读一读这个Knuth教授这辈子最喜欢的算法，来自他的学生TARJAN(图灵奖得主)。

• Robert Tarjan的论文 Depth-First Search and Linear Graph Algorithms
• Knuth的TAOCP手稿 https://www-cs-faculty.stanford.edu/~knuth/fasc12a+.pdf

其中Knuth教授在上面的手稿里引用了一个别人对Tarjan这个算法的评论：

这更加让人想深刻理解这些科学家们的思路了。

Knuth教授近期在自己的个人主页上强烈呼吁大家要更正对弱连通分量的定义，不要用大部分教材里三心二意的定义，而是要用上个世纪70年代一篇关于离散数学的论文里的定义。Knuth教授的呼吁在此：https://www-cs-faculty.stanford.edu/~knuth/news22.html#weakcomps，部分引用如下：

Let’s all agree as soon as possible to use the easily understood term undirected components, or (as suggested by Doug West) underlying components, for what many people have unfortunately been calling weak components, and to celebrate the properties of directed graphs whose weak components are defined in a truly useful way.

本文研究学习上个世纪70年代一篇离散数学的话题，它有一个很好的关于图(Graph)的弱连通分量的定义。论文信息如下：

• Graham, Ronald L., Donald E. Knuth, and Theodore S. Motzkin. “Complements and transitive closures.” Discret. Math. 2.1 (1972): 17-29.
• https://mathweb.ucsd.edu/~ronspubs/72_08_complements.pdf