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..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."] ]
public class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> rec = new ArrayList<List<String>>();
if(n<=0)
return rec;
int[] num = new int[n];
for(int i=0;i<n;i++)
num[i] = i;
DFS(0,n,rec,num);
return rec;
}
public void DFS(int start,int N,List<List<String>> result,int[] num)
{
if(start == N)
{
List<String> t = new ArrayList<String>();
if(isValid(num))
{
for(int i = 0; i < N; i++){
StringBuilder s = new StringBuilder();
for(int j = 0; j < N; j++){
if(j==num[i])
s.append("Q");
else
s.append(".");
// System.out.println(s);
}
t.add(s.toString());
}
result.add(t);
}
}
else
{
for(int i=start;i<N;i++)
{
int temp1=num[start];
num[start]=num[i];
num[i]=temp1;
DFS(start+1,N,result,num);
int temp2=num[start];
num[start]=num[i];
num[i]=temp2;
}
}
}
public boolean isValid(int[] num)
{
for(int i=0;i<num.length;i++)
for(int j=i+1;j<num.length;j++)
if(Math.abs(num[i]-num[j])==Math.abs(i-j))
return false;
return true;
}
}
