N-Queens -- LeetCode

原題鏈接: http://oj.leetcode.com/problems/n-queens/
N皇後問題是非常經典的問題了，記得當時搞競賽第一道遞歸的題目就是N皇後。因為這個問題是典型的NP問題，所以在時間復雜度上就不用糾結了，肯定是指數量級的。下面我們來介紹這個題的基本思路。
主要思想就是一句話：用一個循環遞歸處理子問題。這個問題中，在每一層遞歸函數中，我們用一個循環把一個皇後填入對應行的某一列中，如果當前棋盤合法，我們就遞歸處理先一行，找到正確的棋盤我們就存儲到結果集裡面。
這種題目都是使用這個套路，就是用一個循環去枚舉當前所有情況，然後把元素加入，遞歸，再把元素移除，這道題目中不用移除的原因是我們用一個一維數組去存皇後在對應行的哪一列，因為一行只能有一個皇後，如果二維數組，那麼就需要把那一行那一列在遞歸結束後設回沒有皇後，所以道理是一樣的。

這道題最後一個細節就是怎麼實現檢查當前棋盤合法性的問題，因為除了剛加進來的那個皇後，前面都是合法的，我們只需要檢查當前行和前面行是否沖突即可。檢查是否同列很簡單，檢查對角線就是行的差和列的差的絕對值不要相等就可以。代碼如下：

public ArrayList solveNQueens(int n) {
    ArrayList res = new ArrayList();
    helper(n,0,new int[n], res);
    return res;
}
private void helper(int n, int row, int[] columnForRow, ArrayList res)
{
    if(row == n)
    {
        String[] item = new String[n];
        for(int i=0;i這道題實現的方法是一個非常典型的套路，有許多題都會用到，基本上大部分NP問題的求解都是用這個方式，比如Sudoku
 Solver，Combination
 Sum，Combinations等，所以大家只要把這個套路掌握熟練，那些題就都不在話下哈。