建站
咨詢
售后
建站咨詢
新聞中心
【題目描述】
成都創(chuàng)新互聯(lián)成立以來不斷整合自身及行業(yè)資源、不斷突破觀念以使企業(yè)策略得到完善和成熟，建立了一套“以技術(shù)為基點(diǎn)，以客戶需求中心、市場(chǎng)為導(dǎo)向”的快速反應(yīng)體系。對(duì)公司的主營(yíng)項(xiàng)目，如中高端企業(yè)網(wǎng)站企劃 / 設(shè)計(jì)、行業(yè) / 企業(yè)門戶設(shè)計(jì)推廣、行業(yè)門戶平臺(tái)運(yùn)營(yíng)、app開發(fā)定制、手機(jī)網(wǎng)站制作設(shè)計(jì)、微信網(wǎng)站制作、軟件開發(fā)、四川主機(jī)托管等實(shí)行標(biāo)準(zhǔn)化操作，讓客戶可以直觀的預(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皇后問題是將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/
標(biāo)題名稱：Lintcode33N-Queenssolution題解
轉(zhuǎn)載源于：http://www.ef60e0e.cn/article/gieggp.html
