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