摘要：題目要求這里的王后相當于國際圍棋的王后，該王后一共有三種移動方式水平垂直，對角線。并將當前的臨時結果作為下一輪的輸入進行下一輪的預判。這里我們進行了進一步的優化，將轉化為，其中數組用來記錄該列是否被占領，數組用來記錄該行占領了那一列。

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.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

這里的王后相當于國際圍棋的王后，該王后一共有三種移動方式：水平、垂直，對角線。問要如何將n個王后布局在n*n的棋盤中保證她們不會互相傷害捏？

利用動態編程的思想。只要當前列，以及左對角線和右對角線都沒有被占用的話，就可以在當前位置上暫時填上一個值。并將當前的臨時結果作為下一輪的輸入進行下一輪的預判。
在這里我們用Map存儲每一行填入Q的列數，用Set存儲占據的對角線。

    public List> solveNQueens(int n) {
        List> result = new ArrayList>();
        if(n==0){
            return result;
        }
        //記錄左右對角線情況
        Set leftCordinal = new HashSet(), rightCordinal = new HashSet();
        Map current = new HashMap();
        solveNQueens(result, current, leftCordinal, rightCordinal, n);
        return result;
    }
    
    public void solveNQueens(List> result, Map current, Set leftCordinal, Set rightCordinal, int n){
        if(current.size() == n){
            List currentResult = new ArrayList();
            StringBuilder s = new StringBuilder();
            for(int i = 0 ; i
在這里其實可以用boolean[]代替Set，用簡單值類型的數組代替復雜的數據結構往往可以提高性能。
    public List> solveNQueens2(int n) {
        List> result = new ArrayList>();
        if(n==0){
            return result;
        }
        //記錄左右對角線情況
        boolean[] leftCordinal = new boolean[n*2-1], rightCordinal = new boolean[n*2-1];
        Map current = new HashMap();
        solveNQueens2(result, current, leftCordinal, rightCordinal, n);
        return result;
    }
    
    public void solveNQueens2(List> result, Map current, boolean[] leftCordinal, boolean[] rightCordinal, int n){
        if(current.size() == n){
            List currentResult = new ArrayList();
            StringBuilder s = new StringBuilder();
            for(int i = 0 ; i
將Map類型也轉化一下？
我們發現，每一次得到一個結果時，都需要將相應的值轉化為String然后添加的數組再添加到結果集中。但是其實這些String 的值都是重復利用的。畢竟Q可能位于0~n-1的任何位置上，也就是說有n個固定的互異字符串，但是一個結果上一定會包含所有這些字符串。這里我們進行了進一步的優化，將Map轉化為boolean[]+int[]，其中bool數組用來記錄該列是否被占領，int數組用來記錄該行占領了那一列。
public class NQueens_51 {
    //將map數據結構int[]+boolean[]+lines[]+
    List> res;
    boolean[] col, lslash, rslash;
    int[] p;
    int n;
    String[] lines;
    private void dfs(int i) {
        if(i == n) {
            List board = new ArrayList();
            for(int j = 0; j < n; j++) {
                board.add(lines[p[j]]);
            }
            res.add(board);
            return;
        }
        
        for(int j = 0; j < n; j++) {
            if(!col[j] && !lslash[i+j] && !rslash[j-i+n-1]) {
                col[j] = true;
                lslash[i+j] = true;
                rslash[j-i+n-1] = true;
                p[i] = j;
                dfs(i+1);
                col[j] = false;
                lslash[i+j] = false;
                rslash[j-i+n-1] = false;
            }
        }
    }
    public List> solveNQueens3(int n) {
        this.n = n;
        res = new ArrayList>();
        col = new boolean[n];
        lslash = new boolean[2*n-1];
        rslash = new boolean[2*n-1];
        p = new int[n];
        char[] line = new char[n];
        lines = new String[n];
        for(int i = 0; i < n; i++) {
            line[i] = ".";
        }
        for(int i = 0; i < n; i++) {
            line[i] = "Q";
            lines[i] = String.copyValueOf(line);
            line[i] = ".";
        }
        dfs(0);
        return res;
    }

}

N-Queens II 題目和實現
Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

相比于I，這里不要去獲得具體的答案，只需要返回解答的數量即可。其實比I要簡單。思路還是相同的，利用迭代實現自頂向下的動態編程
代碼如下：
    public int totalNQueens(int n) {
        boolean[] leftCordinal = new boolean[n*2-1], 
                  rightCordinal= new boolean[n*2-1], 
                  vertical = new boolean[n];
        int result = 0;
        return totalNQueens(0, n, result, vertical, leftCordinal, rightCordinal);
    }
    
    public int totalNQueens(int current, int n, int result, boolean[] vertical, boolean[] leftCordinal, boolean[] rightCordinal){
        if(current == n){
            return ++result;
        }
        
        for(int i = 0 ; i

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~