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