用排列组合的方法如何求八皇后问题先设定一列放一个,则第一个皇后有八种放法,第二个有七种,第三个有六种,以此类推全部有A（8,8）即8*7*6*5*4*3*2*1=40320种,再减去两个皇后在同一斜线上,三

Question

用排列组合的方法如何求八皇后问题
先设定一列放一个,则第一个皇后有八种放法,第二个有七种,第三个有六种,以此类推全部有A（8 ,8）即8*7*6*5*4*3*2*1=40320种,再减去两个皇后在同一斜线上,三个皇后同一斜线上至八个皇后在一条斜线上即C(8,2)+C(8,3)+C(8,4)+.+C(8,8),得数确实不对,我只想知道我的逻辑哪块错了.

Answer 1

错在两个地方：
1. 逻辑上应该用容斥原理,即减去2个皇后在同一斜线上,“加上“3个皇后同一斜线上,减去4个皇后同一斜线上,“加上“5个皇后同一斜线上,减去6个皇后同一斜线上,“加上“7个皇后同一斜线上,减去8个皇后同一斜线上.
2. k个皇后在同一斜线上的计数不是C(8,k),因为不知道在哪条斜线上.