主題
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)。


另請參閱

國際象棋, 已婚夫婦問題, 象數, 象多項式, 象互反定理

使用 探索

參考文獻

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.

在 中引用

象棋問題

引用為

Weisstein, Eric W. “象棋問題。” 來自 Web 資源。 https://mathworld.tw/RooksProblem.html

主題分類