要證明出某種棋子最多只能擺N個,需要說明:
- 不存在擺超過N個的情況
- 確實存在能擺N個的情況
而「確實存在能擺N個的情況」這條,
只要給出一個符合條件的擺法就足以說明「擺法確實存在」,
不用特別說明「為什麼這樣擺」。
國王:
考慮國王站在上圖16個區塊中任意一個藍色或紅色區塊中,
則該區塊均在那個國王的吃子範圍內,因此每個區塊最多只能擺放1個國王,
即可以擺放的數量不超過16個。
下圖為一種16個國王的擺法:
主教:
將棋盤順時針旋轉45度後,可以轉換為非矩形盤面的城堡問題,
而深色和淺色的版面是互不干涉的,所以可以分開處理,
且兩個版面僅為旋轉90度的差距,因此只需處理一個版面即可。
看淺色版面,因只有7行,因此可擺放的主教不超過7個,深色版面亦同,
將兩個盤面綜合起來即可得知原盤面可以擺放的主教不超過14個。
下圖為其中一種擺法:
騎士:
先看4×4的棋盤,上圖被分為4種不同顏色的區域,
而每種顏色的區域最多只能放2個騎士,因為每個騎士的吃子範圍會包含2個同色格子,
因此在這個這個棋盤上能擺放的騎士不超過8個,
而8×8的棋盤由4個4×4的棋盤構成,因此能擺放的騎士不超過32個。
留意到原棋盤上的騎士的吃子範圍都與所擺位置的格子顏色相異,
能夠推測出將32個騎士擺在同色格子能夠滿足條件,因此最多的確能擺32個。
下圖為其中一種擺法:
附錄:
在引言中,我們提到在8×8棋盤上擺放最多城堡、皇后並使彼此不在吃子範圍的擺法數,
那麼題目中的國王、主教以及騎士又是如何呢?
國王的話擺法數不難推測出5
8=390625為一個上界(即擺法數不超過390625)。
以解析第一張圖的分區來看,每個2×2的區域都會擺一個國王,
因此可以把國王的分布以左右,或者上下來做區分。
先以一橫列的4塊區域從左往右來看,
若某個區域擺在右邊,則下一個區域的國王就不會擺在左邊,否則兩者會在彼此的吃子範圍內。
因此該橫列從左往右四個區域國王的分布,
可能的情況只有:左左左左、左左左右、左左右右、左右右右、右右右右5種,
總共有4橫列區域因此會有5
4種情況,
再加上考慮每一縱列國王擺在上或下的情形,也會有5
4種情況,
因此將這些情況綜合考慮即為5
4×5
4=5
8種情況。
不過還要考慮斜向兩塊區域上的國王可能會彼此進入吃子範圍的問題,
例如國王分別擺在B2及C3可以滿足16個2×2區域內各1個國王且不與上面提及的情況衝突,
但這兩個國王會在彼此的吃子範圍,因此擺法數會比5
8還少。
因為計算實際數量會需要使用排容原理進行大量且繁瑣的計算,
處理上使用程式的窮舉計數計算效率可能還比較高。
而經過計算,16個國王彼此不在攻擊範圍的擺法共有281571種。
雖然實際擺法數與我們預估的上界58=390625有不小的差距,
但至少比每個2×2區域隨意各放一個國王的擺法數416≒43億小了很多。
主教的話因先查看轉換為城堡模式的淺色棋盤,
上圖標示數字的位置中,顏色相同的位置只能在①或②其中一個標示的位置擺上主教,
藍色擺1個,其他顏色各擺2個,這樣才能擺滿7個主教。
在沒有標示的位置擺主教,會因為對應直橫排的標示位置都不能擺主教,導致無法擺滿7個。
因此每種顏色都可以選擇擺在①的位置或②的位置,共有24種可能。
淺色棋盤旋轉90度的深色棋盤能擺的位置同理,也有24種可能,
所以擺滿14個主教並使彼此不在攻擊範圍的擺法共有28=256種。
騎士的話可以由4×4的棋盤推論出可能擺出8個騎士的盤面共有以下6種,
扣除旋轉、鏡射後相同的擺法則只有3種。
將盤面延伸查看各個盤面的騎士的吃子範圍,確認拼湊後騎士是否會互相衝突,
最後可以得到擺法只有將騎士站在同一顏色的2種4×4盤面可以向外拼湊棋盤,且只能和自己拼湊,
因此可以得到擺法只有與原棋盤同一顏色的32個格子上的2種。