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矩阵中，每行放一个棋子，使得棋子所在的列和两条斜线上没有其他棋子，枚举所有可能。

 

dfs去遍历，考虑所有可能，row中记录每一行棋子的位置，col记录当前列是否有棋子，对角线的判断就是两点行差值和列差值是否相同。

当dfs深度达到n时，就表示存在满足条件的解，把当前状态图存到结果中。

temp（n, '.'）先把字符串全部赋值成 ‘ . ' ，在吧存在棋子的位置改成’Q‘

 

 

经典的8皇后，递归回溯可解。同时还学了StringBuilder里面一个setCharAt()很方便的方法 

ref:http://www.2cto.com/kf/201311/256634.html

 

public class Solution{    public ArrayList
     
       solveNQueens(int n) {          ArrayList
      
        result = new ArrayList
       
        ();          int[] queenList = new int[n];          placeQueen(queenList, 0, n, result);          return result;      }             // 递归回溯8皇后，关键记录下到达了哪一行了      public void placeQueen(int[] queenList, int row, int n, ArrayList
        
          result){          // Base Case, 已经完成任务了          if(row == n){              StringBuilder[] sol = new StringBuilder[n];                             // 对数组内每一个对象都要new出其对象, 并将其全设为'.'             for(int i=0; i