上一道數學謎題
下一道數學謎題

西洋棋擺放問題數學謎題

答對率:略
(建議使用電腦版閱覽題目,且無興趣閱讀引言者可直接跳至下方題目)
 
西洋棋(Chess)是一種兩人在8×8的棋盤上對弈的棋類遊戲,
棋種包含:國王(King)、皇后(Queen)、主教(Bishop)、騎士(Knight)、城堡(Rook)、士兵(Pawn)。

國王的移動範圍為直橫斜向相鄰一格,即以國王為中心的九宮格。
皇后的移動範圍為直橫斜向任意步數,不可越過其他棋子。
主教的移動範圍為斜向任意步數,不可越過其他棋子。
騎士的移動範圍為2×1矩形的對角線,與象棋的馬走法相同,但沒有拐馬腳的問題。
城堡的移動範圍為直橫向任意步數,不可越過其他棋子,與象棋的車走法相同。
上述棋類的移動範圍亦為吃子範圍,即範圍內有敵方棋子則可以吃子。
士兵的移動範圍則只能往前一步,首步則可往前兩步;吃子範圍則為士兵的斜前方。

關於西洋棋的詳細內容及規則可見維基百科或自行上網搜尋。
 

而在8×8的棋盤上,最多可以擺幾個城堡,使城堡間不在彼此的吃子範圍內?
答案是8個,因根據城堡的走法,每行每列最多只會有1個城堡,因此不可能擺超過8個,
且擺了n個城堡後,必還有8-n行及8-n列可以擺,因此能確保一定能擺到8個。
下圖為其中一種擺法:
而8個城堡的在8×8棋盤上彼此不在攻擊範圍內的擺法,
又與8樣東西任意排列是等價的,即兩者的關係是一一對應且可回推的。
假設第i行第j列有棋子表示第i個位置擺第j樣東西,
因城堡的擺法,i不會重複且j亦不會重複,
不會有一個位置擺多個東西或多個位置擺同一東西的情況,
因此可以得到彼此的對應關係。
若第i行的城堡在第j列,則第i個數字為j的話,
以上圖為例,便會得到27851346,是1到8的排列。

根據這種對應關係,我們可以得到8個城堡在8×8棋盤上共有8!=40320種擺法,
即為8樣東西進行排列的數量。

而在數學上,也會將排列帶到城堡在棋盤上的放置來計算其結果,
假設第i個位置不能擺第j樣東西,那就讓第i行第j列不能擺城堡,
得到的答案就能滿足對應要求。
棋盤多項式,又被稱為城堡多項式(Rook polynomial),
就是將有受限的排列問題轉換為受限的城堡擺放問題的應用。
 


看完城堡問題後,你知道在8×8的棋盤上最多可以擺幾個皇后,使彼此不在吃子範圍內?
因為皇后同時擁有城堡的移動方式,因此可以知道能擺的數量絕對不超過8個,
至於是否真的能擺到8個,實際上是可以的,下圖為一例:
實際上這是一個相當困難的題目,被稱為八皇后問題
目前已經得到共有92種擺法,
若將旋轉、鏡射後相同的擺法視為同一種擺法的話,則只有12種擺法。

八皇后問題在排列上並沒有重大的意義,
但若第i行第j列擺放皇后轉換為第i個數字為j的話,
則這串數字除了是排列外,還會滿足相異的任意兩數的距離和相減值不同,
用數學的方式來說,即對於任意i≠j,|ai-aj|≠|i-j|,其中an代表排列中第n個數字。
且這是一個等價關係,即若一排列滿足該條件,也可以反推轉換為皇后擺法,
其原因與兩皇后不能擺在同一斜線有所關聯,有興趣者可自行推論。

任舉1到8排列出的數為例,
17463825中,6和8相隔2位且相減為2,不滿足條件;
63752814中,6和2相隔4位且相減為4,不滿足條件。
若改以上圖為例,皇后的位置可以轉換為53172864,
8個數字中任意取相異2數,得到的距離和相減值會不同。
 

那麼:
 
在8×8的棋盤上,最多能同時放幾個國王,使得彼此不在吃子範圍內呢?
如果改為放主教的話又能放幾個?
改為騎士的話又如何呢?
 
jen8810556(耀☆羽)2019-11-30提供(2019-12-04修改)
看答案
國王:16個
主教:14個
騎士:32個

解析

我要編輯
國王:
考慮國王站在上圖16個區塊中任意一個藍色或綠色區塊中,
則該區塊均在那個國王的吃子範圍內,因此每個區塊最多只能擺放1個國王,
即可以擺放的數量不超過16個。
 
下圖為一種16個國王的擺法:
 

主教:
將棋盤順時針旋轉45度後,可以轉換為非矩形盤面的城堡問題,
而深色和淺色的版面是互不干涉的,所以可以分開處理,
且兩個版面僅為旋轉90度的差距,因此只需處理一個版面即可。
看淺色版面,因只有7行,因此可擺放的主教不超過7個,
而從只有2格的2行開始推理,可以得到每行都能擺1個主教,即擺7個主教是可行的,
將兩個盤面綜合起來即可得知原盤面最多可以擺放14個主教。
下圖為其中一種擺法:

 


騎士:
先看4×4的棋盤,上圖被分為4種不同顏色的區域,
而每種顏色的區域最多只能放2個騎士,因為每個騎士的吃子範圍會包含2個同色格子,
因此在這個這個棋盤上能擺放的騎士不超過8個,
而8×8的棋盤由4個4×4的棋盤構成,因此能擺放的騎士不超過32個。

留意到原棋盤上的騎士的吃子範圍都與所擺位置的格子顏色相異,
能夠推測出將32個騎士擺在同色格子能夠滿足條件,因此最多的確能擺32個。
下圖為其中一種擺法:
 

附錄:

在引言中,我們提到在8×8棋盤上擺放最多城堡、皇后並使彼此不在吃子範圍的擺法數,
那麼題目中的國王、主教以及騎士又是如何呢?

國王的話擺法數不難推測出58=390625為一個上界(即擺法數不超過390625)。

以解析第一張圖每個2×2的綠色或藍色區域為例,國王會擺在左邊2格或右邊2格,
就第一橫列的4塊區域從左往右來看,
若某個區域擺在右邊,則下一個區域的國王就不會擺在左邊,
因此可能的情況只有:左左左左、左左左右、左左右右、左右右右、右右右右5種,
總共有4橫列區域因此會有54種情況,
再加上考慮每一縱列國王擺在上面2格或下面2格,也會有54種情況,
因此將這些情況綜合考慮即為54×54=58種情況。

不過還要考慮斜向兩塊區域上的國王可能會彼此進入吃子範圍的問題,
例如國王分別擺在B2及C3可以滿足16個2×2區域內各1個國王且不與上面提及的情況衝突,
但這兩個國王會在彼此的吃子範圍,因此擺法數會比58還少。
因為計算實際數量會需要使用排容原理進行大量且繁瑣的計算,
處理上使用程式的窮舉計數計算效率可能還比較高。
而經過計算,16個國王彼此不在攻擊範圍的擺法共有281571種。

雖然實際擺法數與我們預估的上界58=390625有不小的差距,
但至少比每個2×2區域隨意各放一個國王的擺法數416≒43億小了很多。

主教的話因轉換為城堡模式的棋盤後,
必須放在滿足m+n=9的m×n矩形的其中一組對角,
(若m或n等於1則為兩格中其中一格)
如果擺在其他地方可以簡單推測出會無法擺滿14個主教,
因此14個主教彼此不再攻擊範圍的擺法共有28=256種。
 
騎士的話可以由4×4的棋盤推論出可能擺出8個騎士的盤面,
再延伸將4個盤面拼湊確認拼湊後騎士是否會互相衝突,
得到擺法只有將騎士站在原棋盤同一顏色的32個格子上的2種。
269
上一道數學謎題
下一道數學謎題