[問題] 複合型Ｎ皇后問題(已解決)

[fatcat8127 (胖胖貓)]

附上原題目出處 (https://zerojudge.tw/ShowProblem?problemid=b941)

這題是在棋盤上擺上皇后、城堡、主教，在不發生衝突的情況下問方法數？

題目保證三種棋類的數量總和最大不會超過8個(若單一種則不會超過10個)。

核心解法：ZJ-a682 + ZJ-b510

以下先各自分析這兩題的作法後再描述怎麼搭配到這題：

ZJ-a862的題目(UVa-861)則是在棋盤上只放主教問不衝突的方法數，

作法是將棋盤轉45度後將整個棋盤拆分成黑白兩個區塊計算方法數時，

兩個區塊放置的主教不會相互干擾，視為相互獨立的事件，之後做動態規劃累加。

ZJ-b510(出自於清華大學MOOC期末題目)

在棋盤上放上皇后和城堡的方法數，不過棋盤不大(邊長最大=10)，所以可以暴力解，

不過有比較漂亮的解法處理放置皇后和城堡兩者的方式。

回到ZJ-b941的題目，一開始先仿效ZJ-b510在棋盤放上 Queen 和 Rook，所以選出

從0~N-1的號碼選擇 Qcnt+Rcnt 個#Row，同時用兩個陣列紀錄斜向方程式是否被佔走。

若順利完成上述步驟後再接著仿效ZJ-a682放入主教。

將棋盤拆成黑白兩個獨立的區域，掃描整個棋盤仍舊合法的空格存在Slash_pick

這邊需要解釋一下儲存的方式：Slash_pick[0][0] = K

代表在斜線方程式x+y=0的這條線上有一個合法的空格且這個空格也落在x-y=K的斜線上

之後各自對黑白區域暴力法遞迴嘗試所有的可以放的主教數量的方法數後相乘累加。

這邊附上在邊長是N的棋盤上放N個主教的方法數(N=1~10)

1, 4, 26, 260, 3368, 53744, 1022320, 22522960, 565532992, 15915225216

可以發現當N=10時，若是(1)暴力法枚舉每格能不能放入主教或是

(2)不區分黑白區域暴力法枚舉x+y=K的所有狀態時是會TLE(理論上)。

附上實作的程式碼和下面極限測資的結果：

(不拆暴力枚舉的作法)https://ideone.com/EmgZnB

(拆成獨立區域的做法)https://ideone.com/Cx6f5T

至於ZJ的實測時間對於Bishop部分，不管是採用暴力法去填還是拆分成獨立區域都是0.2s

所以猜測Bishop數量應該不會超過6個以上，如果依照題意輸入極限測資

0 0 9 或是0 0 10時必須仿效ZJ-a682的獨立區域作法否則會TLE。

以下感謝cutecpu的討論和想法提供實現進一步的加速，以下假設棋盤最大是10x10。

(1)枚舉完Queen和Rook後計算Bishop時盤面可能會重複計算，

   可以利用 Zobrist HashTable，紀錄目前的盤面(10x10的每個棋子只有放或不放)，

   之後計算盤面前就查表看看有沒有算過。

(2)對於棋類盤面有鏡像和旋轉後產生相同盤面的情況

   將相同的想法套用在紀錄 Bishop 的盤面上

   紀錄某個未算過的一個盤面時同時記錄該盤面鏡像/旋轉後的等價情況

   如同維基的八皇后問題說明(https://en.wikipedia.org/wiki/Eight_queens_puzzle)

   和相關的網頁討論(http://penguin.ewu.edu/~trolfe/Queens/OptQueen.html)

(3)狀態壓縮

   放置 Queen 和 Rook 時枚舉每個沒放置棋子的 Column 可以用位元計算O(1)

最後附上根據討論後的加速版本：https://ideone.com/oBJDdQ

對於測資(2,2,6),(1,3,6),(3,1,6)的時間總共需要7.98s，

但是測資(2,3,5),(3,3,4)這類 Queen+Rook 數量較多的情況時，

因為作法在處理 Queen 和 Rook 是用DFS枚舉每個Row而造成TLE的，

也許(不確定)能把鏡像和旋轉的加速方式套用在這裡再進一步加速。

對於相關作法或是疑惑的部分歡迎大家在下面的留言討論分享。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.136.218
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1556474805.A.DC8.html
※ 編輯: fatcat8127 (140.113.136.218), 04/29/2019 02:11:34
→ oToToT: 有點好奇這些題目都怎麼挑的@@
→ fatcat8127: 是指復旦的程式檢定題目嗎?
※ 編輯: fatcat8127 (180.204.139.221), 05/02/2019 16:09:09
→ allem40306: 如果是我，會開4個array，分別維護直線、橫線
→ allem40306: 和兩種對角線有沒有棋子已經在上面，然後用枚舉+剪枝
→ allem40306: 下去，大概是這樣，但這題我沒做過，時限不知道多少，
→ allem40306: 加上題目沒寫清楚棋盤的範圍，所以不知道會不會過
推 cutekid: 最大情況: Q = 10, R = 10, B = 10, 棋盤: 30x30
→ cutekid: 照上面的case，用您的算法，就可以知道用時多少
→ fatcat8127: 恐怕不會通過 只要做過八皇后就知道當棋盤長度大於20
→ fatcat8127: 格是無法在2s內跑完，何況這題棋盤長度高達30格 時限
→ fatcat8127: 是3s
推 oToToT: 幫原出題者表示一下：已修正測資範圍(?
→ fatcat8127: 哦哦 這樣應該是可以暴力法解題
※ 編輯: fatcat8127 (61.231.100.27), 05/15/2019 11:27:47
※ 編輯: fatcat8127 (61.231.100.27), 05/15/2019 12:05:34
※ 編輯: fatcat8127 (61.231.100.27), 05/15/2019 12:07:58
※ 編輯: fatcat8127 (36.227.0.120), 05/18/2019 12:17:00
※ 編輯: fatcat8127 (140.113.208.181), 05/20/2019 17:16:15