作者fatcat8127 (胖胖猫)
看板Prob_Solve
标题[问题] 复合型Ｎ皇后问题(已解决)
时间Mon Apr 29 02:06:43 2019
附上原题目出处 (
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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1556474805.A.DC8.html
※ 编辑: fatcat8127 (140.113.136.218), 04/29/2019 02:11:34
1F：→ oToToT: 有点好奇这些题目都怎麽挑的@@04/29 08:52
2F：→ fatcat8127: 是指复旦的程式检定题目吗?04/29 19:23
※ 编辑: fatcat8127 (180.204.139.221), 05/02/2019 16:09:09
3F：→ allem40306: 如果是我，会开4个array，分别维护直线、横线 05/08 13:06
4F：→ allem40306: 和两种对角线有没有棋子已经在上面，然後用枚举+剪枝 05/08 13:11
5F：→ allem40306: 下去，大概是这样，但这题我没做过，时限不知道多少， 05/08 13:14
6F：→ allem40306: 加上题目没写清楚棋盘的范围，所以不知道会不会过 05/08 13:15
7F：推 cutekid: 最大情况: Q = 10, R = 10, B = 10, 棋盘: 30x30 05/08 13:32
8F：→ cutekid: 照上面的case，用您的算法，就可以知道用时多少 05/08 13:34
9F：→ fatcat8127: 恐怕不会通过 只要做过八皇后就知道当棋盘长度大於20 05/08 19:37
10F：→ fatcat8127: 格是无法在2s内跑完，何况这题棋盘长度高达30格 时限 05/08 19:37
11F：→ fatcat8127: 是3s 05/08 19:37
12F：推 oToToT: 帮原出题者表示一下：已修正测资范围(? 05/10 19:46
13F：→ fatcat8127: 哦哦 这样应该是可以暴力法解题 05/11 02:59
※ 编辑: 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