溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
【題目描述】
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的棋盤上，皇后彼此之間不能相互***。給定一個整數n，返回所有不同的n皇后問題的解決方案。每個解決方案包含一個明確的n皇后放置布局，其中“Q”和“.”分別表示一個女王和一個空位置。
【題目鏈接】
http://www.lintcode.com/en/problem/n-queens/
【題目解析】
經典的DFS遞歸回溯解法，大體思路就是對每一行，按每一列挨個去試，試到了就保存結果沒試到就回溯。
難點大概就是用1個一維數組存皇后所在的坐標值。對于一個棋盤來說，每個點都有橫縱坐標，用橫縱坐標可以表示一個點。
而這道題巧就巧在，每一行只能有一個皇后，也就是說，對于一行只能有一個縱坐標值，所以用1維數組能提前幫助解決皇后不能在同一行的問題。
那么用一維數組表示的話，方法是：一維數組的下標表示橫坐標（哪一行），而數組的值表示縱坐標（哪一列）。
這樣一來，皇后所在的坐標值就能用一維數組表示了。而正是這個一維數組，在回溯找結果的時候不需要進行remove重置操作了，因為回溯的話正好就回到上一行了，就可以再重新找下一個合法列坐標了。
因為是按照每一行去搜索的，當行坐標值等于行數時，說明棋盤上所有行都放好皇后了，這時就把有皇后的位置標為Q，沒有的地方標為0。
按照上面講的那個一維數組，我們就可以遍歷整個棋盤，當坐標為（row，columnVal[row]）的時候，就說明這是皇后的位置，標Q就行了。
【參考答案】
http://www.jiuzhang.com/solutions/n-queens/
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
