素数阶棋盘上的皇后问题Queens on a prime order board
N皇后问题要求在n×n的棋盘上放置n个皇后且使其互不攻击。当棋盘阶数n为大于等于5的素数时，存在一种极其优雅的几何求解策略。只需将皇后放置在斜率为2、3、4等特定数值的直线上，即可满足无任何水平、垂直或对角线攻击的条件。这为数论与经典组合谜题的结合提供了一个巧妙的数学证明。
John
The n queens problem is to place on an n × n chessboard n queens so that none attacks any other. This means there is only one queen on every horizontal, vertical, and diagonal line.
When n is a prime number ≥ 5, it is sufficient to place the queens on a line that has slope 2, 3, 4, …, n − 2. (The slope cannot be 1 because that’s a diagonal. And it cannot be n − 1 because n − 1 = −1 mod n is also a diagonal.) [1]
Here we imagine opposite edges of the board being joined together. Geometrically, this makes the chessboard a torus (donut). Algebraically, the points on a line of slope s have the coordinates
(a + k, b + ks)
where addition is carried out mod n.
All solutions to the n queens problem have this form when n = 5. Some solutions will have this form for larger prime values of n but not all.
For example, when n = 7, here is a solution where all the queens are on a line of slope 2.
But here is another solution where the queens do not all lie on a line of constant slope.
Related posts
[1] W. H. Bussey. A Note on the Problem of the Eight Queens. The American Mathematical Monthly, Vol. 29, No. 7 (August 1922), pp. 252–253
需要完整排版与评论请前往来源站点阅读。