n王后问题

n 王后问题是高斯(Gauss)提出(n=8)的一个著名问题: 在 n×n 的国际象棋棋盘上摆上 n 个王后,使得每一个王后都不能攻击另外一个(王后可以横走、竖走,还可以沿着棋盘的两条对角线中任何一条的方向走)。这个问题是有意义的,它等价于求一个单纯图 G=(X,E)的极大稳固集,其中 G 有n~2个顶点并且如果顶点 x 和 y 处于同一行或同一列或处于与对角线平行的同一条直线上,则 y∈F_G(x)。(见文1])。这个问题也等价于求满足一定条件的特殊置换类的问题。此外,有趣的是,1977年,Loren C.Larson 利用 n 王后