Lintcode33 N-Queens solution 題解

【題目描述】

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

【題目鏈接】

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

【題目解析】

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

難點大概就是用1個一維數(shù)組存皇后所在的坐標(biāo)值。對于一個棋盤來說，每個點都有橫縱坐標(biāo)，用橫縱坐標(biāo)可以表示一個點。

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

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

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

因為是按照每一行去搜索的，當(dāng)行坐標(biāo)值等于行數(shù)時，說明棋盤上所有行都放好皇后了，這時就把有皇后的位置標(biāo)為Q，沒有的地方標(biāo)為0。

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

【參考答案】

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