【題目描述】

成都創(chuàng)新互聯(lián)成立以來(lái)不斷整合自身及行業(yè)資源、不斷突破觀念以使企業(yè)策略得到完善和成熟，建立了一套“以技術(shù)為基點(diǎn)，以客戶(hù)需求中心、市場(chǎng)為導(dǎo)向”的快速反應(yīng)體系。對(duì)公司的主營(yíng)項(xiàng)目，如中高端企業(yè)網(wǎng)站企劃 / 設(shè)計(jì)、行業(yè) / 企業(yè)門(mén)戶(hù)設(shè)計(jì)推廣、行業(yè)門(mén)戶(hù)平臺(tái)運(yùn)營(yíng)、app開(kāi)發(fā)定制、手機(jī)網(wǎng)站制作設(shè)計(jì)、微信網(wǎng)站制作、軟件開(kāi)發(fā)、四川主機(jī)托管等實(shí)行標(biāo)準(zhǔn)化操作，讓客戶(hù)可以直觀的預(yù)知到從成都創(chuàng)新互聯(lián)可以獲得的服務(wù)效果。

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皇后問(wèn)題是將n個(gè)皇后放置在n*n的棋盤(pán)上，皇后彼此之間不能相互***。給定一個(gè)整數(shù)n，返回所有不同的n皇后問(wèn)題的解決方案。每個(gè)解決方案包含一個(gè)明確的n皇后放置布局，其中“Q”和“.”分別表示一個(gè)女王和一個(gè)空位置。

【題目鏈接】

http://www.lintcode.com/en/problem/n-queens/

【題目解析】

經(jīng)典的DFS遞歸回溯解法，大體思路就是對(duì)每一行，按每一列挨個(gè)去試，試到了就保存結(jié)果沒(méi)試到就回溯。

難點(diǎn)大概就是用1個(gè)一維數(shù)組存皇后所在的坐標(biāo)值。對(duì)于一個(gè)棋盤(pán)來(lái)說(shuō)，每個(gè)點(diǎn)都有橫縱坐標(biāo)，用橫縱坐標(biāo)可以表示一個(gè)點(diǎn)。

而這道題巧就巧在，每一行只能有一個(gè)皇后，也就是說(shuō)，對(duì)于一行只能有一個(gè)縱坐標(biāo)值，所以用1維數(shù)組能提前幫助解決皇后不能在同一行的問(wèn)題。

那么用一維數(shù)組表示的話(huà)，方法是：一維數(shù)組的下標(biāo)表示橫坐標(biāo)（哪一行），而數(shù)組的值表示縱坐標(biāo)（哪一列）。

這樣一來(lái)，皇后所在的坐標(biāo)值就能用一維數(shù)組表示了。而正是這個(gè)一維數(shù)組，在回溯找結(jié)果的時(shí)候不需要進(jìn)行remove重置操作了，因?yàn)榛厮莸脑?huà)正好就回到上一行了，就可以再重新找下一個(gè)合法列坐標(biāo)了。

因?yàn)槭前凑彰恳恍腥ニ阉鞯模?dāng)行坐標(biāo)值等于行數(shù)時(shí)，說(shuō)明棋盤(pán)上所有行都放好皇后了，這時(shí)就把有皇后的位置標(biāo)為Q，沒(méi)有的地方標(biāo)為0。

按照上面講的那個(gè)一維數(shù)組，我們就可以遍歷整個(gè)棋盤(pán)，當(dāng)坐標(biāo)為（row，columnVal[row]）的時(shí)候，就說(shuō)明這是皇后的位置，標(biāo)Q就行了。

【參考答案】

http://www.jiuzhang.com/solutions/n-queens/

網(wǎng)站題目：Lintcode33N-Queenssolution題解
網(wǎng)站網(wǎng)址：http://chinadenli.net/article18/gieggp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動(dòng)網(wǎng)站建設(shè)、外貿(mào)建站、、網(wǎng)站收錄、域名注冊(cè)、服務(wù)器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)