主题
Search

象棋问题


RooksMax

象是国际象棋中的棋子,每步可以水平或垂直移动任意格。在 n×n 棋盘上最多可以放置 n 个互不攻击的象。这种布局可以通过沿对角线放置象来实现 (Madachy 1979)。在 n×n 棋盘上放置 n 个互不攻击的象的总方式数为 n! (Madachy 1979, 第 47 页)。一般来说,多项式

 R_(mn)(x)=sum_(k)r_k^((m,n))x^k

其系数 r_k^((m,n)) 给出了在 m×n 棋盘上放置 k 个互不攻击的象的方式数,被称为象多项式

n×n 棋盘上放置 n 个互不攻击的象的旋转和反射不等价方式的数量为 1, 2, 7, 23, 115, 694, ... (OEIS A000903; Dudeney 1970, 第 96 页; Madachy 1979, 第 46-54 页)。

8×8 棋盘上占据或攻击所有格子所需的最少象的数量是 8 (Madachy 1979),以上述相同的方向排列。

考虑一个 n×n 棋盘,限制条件是,对于 {1,...,n} 的每个子集,当在行 j 时,象不能放在列 s+j (mod n) 中,其中行的编号为 0, 1, ..., n-1。Vardi (1991) 将如此限制的象解的数量表示为 rook(s,n)rook({1},n) 仅仅是在 n 个符号上的错位数,被称为次阶乘。前几个值是 1, 2, 9, 44, 265, 1854, ... (OEIS A000166)。rook({1,2},n)已婚夫妇问题的解,有时被称为夫妇数。前几个夫妇数是 0, 0, 1, 2, 13, 80, 579, ... (OEIS A000179)。

虽然对于一般的 {1,...,p} 没有简单的公式,但可以使用递推关系在多项式时间内计算 rook({1,...,p},n),对于 p=3, ..., 6 (Metropolis et al. 1969, Minc 1978, Vardi 1991)。


另请参阅

国际象棋, 已婚夫妇问题, 象数, 象多项式, 象互反定理

使用 Wolfram|Alpha 探索

参考文献

Dudeney, H. E. "The Eight Rooks." §295 in 数学娱乐. New York: Dover, pp. 88 and 96, 1970.Kraitchik, M. "The Problem of the Rooks" and "Domination of the Chessboard." §10.2 and 10.4 in 数学娱乐. New York: W. W. Norton, pp. 240-247 and 255-256, 1942.Madachy, J. S. Madachy 的数学娱乐. New York: Dover, pp. 36-37 and 46-54, 1979.Metropolis, M.; Stein, M. L.; and Stein, P. R. "Permanents of Cyclic (0, 1) Matrices." J. Combin. Th. 7, 291-321, 1969.Minc, H. §3.1 in 积和式. Reading, MA: Addison-Wesley, 1978.Riordan, J. Chs. 7-8 in 组合分析导论. Princeton, NJ: Princeton University Press, 1978.Sloane, N. J. A. Sequences A000903/M1761, A000166/M1937, and A000179/M2062 in "The On-Line Encyclopedia of Integer Sequences."Vardi, I. Mathematica 中的计算娱乐. Reading, MA: Addison-Wesley, pp. 123-124, 1991.Watkins, J. 纵横棋盘:棋盘问题的数学. Princeton, NJ: Princeton University Press, 2004.

在 Wolfram|Alpha 中引用

象棋问题

引用为

Weisstein, Eric W. “象棋问题。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/RooksProblem.html

主题分类