八皇后问题算什么，来看看无穷皇后问题吧
当 1848 年国际象棋玩家 Max Bezzel 提出八皇后问题（eight queens puzzle）时，他恐怕怎么也想不到，100 多年以后，这个问题竟然成为了编程学习中最重要的必修课之一。八皇后问题听上去非常简单：把八个皇后放在国际象棋棋盘上，使得这八个皇后互相之间不攻击（国际象棋棋盘是一个 8×8 的方阵，皇后则可以朝横竖斜八个方向中的任意一个方向走任意多步）。虽然这个问题一共有 92 个解，但要想徒手找出一个解来也并不容易。下图就是其中一个解：
八皇后问题有很多变种，不过再怎么也不会比下面这个变种版本更帅：请你设计一种方案，在一个无穷大的棋盘的每一行每一列里都放置一个皇后，使得所有皇后互相之间都不攻击。具体地说，假设这个棋盘的左下角在原点处，从下到上有无穷多行，从左到右有无穷多列，你需要找出一个全体正整数的排列方式 a1, a2, a3, … ，使得当你把第一个皇后放在第一行的第 a1 列，把第二个皇后放在第二行的第 a2 列，等等，那么任意两个皇后之间都不会互相攻击。
下面给出一个非常简单巧妙的构造。首先，我们给出五皇后问题的一个解。并且非常重要的是，其中一个皇后占据了最左下角的那个格子。
接下来，我们把五皇后的解扩展到 25 皇后，而依据则是五皇后本身的布局：
这样一来，同一组里的五个皇后显然不会互相攻击，不同组的皇后之间显然也不会互相攻击，这便是一个满足要求的 25 皇后解了。注意到，在扩展之后，之前已经填好的部分并未改变。
再接下来怎么办呢？没错，我们又把 25 皇后的解复制成五份，再次按照五皇后的布局来排列，从而扩展到 125 皇后！
像这样不断地根据已填的部分，成倍地向外扩展，便能生成一个无穷皇后问题的解。
这个解法收录在了 Proofs without Words 一书中。
No comments:
Post a Comment