如果你在第一章最后一題Checker卡住了,請看這里.
Chapter1最后一題Checker,即"n皇后".
DFS+位運算+剪枝.
即用位運算來進行狀態判斷.比如,在N=8時,要在某行的第4個位置放一個棋子,則可以表達為:00010000,也就是1<<4.這樣的話,再加上適當的剪枝來搜索,就可以大大提高搜得效率.
那么又如何剪枝呢?我們可以考慮只枚舉某些情況,其他情況可以通過枚舉出來的情況通過對稱,旋轉等變換得到.
先看N為偶數的情況.為偶數的話,第一排只用枚舉一半(1~N/2),剩下的一半可以由枚舉出來的情況可以由前面的情況對稱得到.
那么N為奇數的時候呢,就應該枚舉中間列(第N div 2 +1 列)以及中間行(N div 3 + 1行)的前半部分(1~N div 2),并且,枚舉時,中間列的枚舉數應當大于中間行的枚舉數,或者小于之.這樣確定了后,就可以通過4種旋轉*2種對稱得到8種圖形,并且是不重復的.剩下最后一種情況就是,剛好枚舉點在最中心時,再全部枚舉一遍.這樣就找出所有方案數了.
方案數問題解決了后,就再寫個裸搜,把前3種情況搜出來,便可以通過此題了.
經實驗,通過N=13時,只需要0.2s.