Description：

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皇后问题，有一个经典的回溯法。具体请参考： 在这个问题中需要用List来记录sum个解矩阵，并返回。 代码：

public class Solution {        public int[] x; //当前解    public int sum; //解的个数    public int n; //皇后个数    public List
     
      
       > resList;        public List
       
        
         > solveNQueens(int n) {        this.resList = new ArrayList
         
          
           >(); for(int i=0; i
           
             n) { List
            
              pRes = new ArrayList
             
              (); for(int i=1; i<=n; i++) { StringBuilder row = new StringBuilder(); for(int j=1; j<=n; j++) { if(this.x[i] == j) { row.append("Q"); } else { row.append("."); } } pRes.add(row.toString()); } resList.add(pRes); sum ++; } else { for(int i=1; i<=n; i++) { this.x[t] = i; if(place(t)) { backTrack(t + 1); //回溯 } } } } /** * 判断当前位置是否合法 */ public boolean place(int k) { for(int j=1; j