八皇后问题算什么,来看看无穷皇后问题吧

    当 1848 年国际象棋玩家 Max Bezzel 提出八皇后问题(eight queens puzzle)时,他恐怕怎么也想不到,100 多年以后,这个问题竟然成为了编程学习中最重要的必修课之一。八皇后问题听上去非常简单:把八个皇后放在国际象棋棋盘上,使得这八个皇后互相之间不攻击(国际象棋棋盘是一个 8×8 的方阵,皇后则可以朝横竖斜八个方向中的任意一个方向走任意多步)。虽然这个问题一共有 92 个解,但要想徒手找出一个解来也并不容易。下图就是其中一个解:

     

    八皇后问题有很多变种,不过再怎么也不会比下面这个变种版本更帅:请你设计一种方案,在一个无穷大的棋盘的每一行每一列里都放置一个皇后,使得所有皇后互相之间都不攻击。具体地说,假设这个棋盘的左下角在原点处,从下到上有无穷多行,从左到右有无穷多列,你需要找出一个全体正整数的排列方式 a1, a2, a3, … ,使得当你把第一个皇后放在第一行的第 a1 列,把第二个皇后放在第二行的第 a2 列,等等,那么任意两个皇后之间都不会互相攻击。

     


 
 
 
 
 
 
 
 
 
    下面给出一个非常简单巧妙的构造。首先,我们给出五皇后问题的一个解。并且非常重要的是,其中一个皇后占据了最左下角的那个格子。

     

    接下来,我们把五皇后的解扩展到 25 皇后,而依据则是五皇后本身的布局:

     

    这样一来,同一组里的五个皇后显然不会互相攻击,不同组的皇后之间显然也不会互相攻击,这便是一个满足要求的 25 皇后解了。注意到,在扩展之后,之前已经填好的部分并未改变。

    再接下来怎么办呢?没错,我们又把 25 皇后的解复制成五份,再次按照五皇后的布局来排列,从而扩展到 125 皇后!

     

    像这样不断地根据已填的部分,成倍地向外扩展,便能生成一个无穷皇后问题的解。

    这个解法收录在了 Proofs without Words 一书中。

52 条评论

回复给 xiadaomike 取消回复

6  +  4  =