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皇后问题，有一个经典的回溯法。具体请参考：N-Queens 在这个问题中需要用List来记录sum个解矩阵，并返回。 代码：
public class Solution {
public int[] x; //当前解
public int sum; //解的个数
public int n; //皇后个数
public List<List<String>> resList;
public List<List<String>> solveNQueens(int n) {
this.resList = new ArrayList<List<String>>();
for(int i=0; i<n; i++) {
}
this.x = new int[n + 1];
for(int i=0; i<=n; i++) {
this.x[i] = 0;
}
this.sum = 0;
this.n = n;
backTrack(1);
return resList;
}
public void backTrack(int t) {
if(t > n) {
List<String> pRes = new ArrayList<String>();
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<k; j++) {
if(Math.abs(j-k) == Math.abs(this.x[j]-this.x[k]) ||
this.x[j] == this.x[k]) {
return false;
}
}
return true;
}
}