【題目描述】
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.Given an integer n, return all distinct solutions to the n-queens puzzle.Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
n皇后問題是將n個(gè)皇后放置在n*n的棋盤上，皇后彼此之間不能相互***。給定一個(gè)整數(shù)n，返回所有不同的n皇后問題的解決方案。每個(gè)解決方案包含一個(gè)明確的n皇后放置布局，其中“Q”和“.”分別表示一個(gè)女王和一個(gè)空位置。
【題目鏈接】
http://www.lintcode.com/en/problem/n-queens/
【題目解析】
經(jīng)典的DFS遞歸回溯解法，大體思路就是對(duì)每一行，按每一列挨個(gè)去試，試到了就保存結(jié)果沒試到就回溯。
難點(diǎn)大概就是用1個(gè)一維數(shù)組存皇后所在的坐標(biāo)值。對(duì)于一個(gè)棋盤來說，每個(gè)點(diǎn)都有橫縱坐標(biāo)，用橫縱坐標(biāo)可以表示一個(gè)點(diǎn)。
而這道題巧就巧在，每一行只能有一個(gè)皇后，也就是說，對(duì)于一行只能有一個(gè)縱坐標(biāo)值，所以用1維數(shù)組能提前幫助解決皇后不能在同一行的問題。
那么用一維數(shù)組表示的話，方法是：一維數(shù)組的下標(biāo)表示橫坐標(biāo)（哪一行），而數(shù)組的值表示縱坐標(biāo)（哪一列）。
這樣一來，皇后所在的坐標(biāo)值就能用一維數(shù)組表示了。而正是這個(gè)一維數(shù)組，在回溯找結(jié)果的時(shí)候不需要進(jìn)行remove重置操作了，因?yàn)榛厮莸脑捳镁突氐缴弦恍辛?，就可以再重新找下一個(gè)合法列坐標(biāo)了。
因?yàn)槭前凑彰恳恍腥ニ阉鞯?，?dāng)行坐標(biāo)值等于行數(shù)時(shí)，說明棋盤上所有行都放好皇后了，這時(shí)就把有皇后的位置標(biāo)為Q，沒有的地方標(biāo)為0。
按照上面講的那個(gè)一維數(shù)組，我們就可以遍歷整個(gè)棋盤，當(dāng)坐標(biāo)為（row，columnVal[row]）的時(shí)候，就說明這是皇后的位置，標(biāo)Q就行了。
【參考答案】
http://www.jiuzhang.com/solutions/n-queens/
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
重慶分公司
重慶分公司
