# How many different solutions to solve this problem?

• And what does backtracing mean?

I used recursion to solve this problem, is it same as backtracing method?

``````public class Solution {
ArrayList<int[]> getSolutions(int[] m, int n)
{
ArrayList<int[]> ret = new ArrayList<int[]>();
if(m.length>=n)
{
return ret;
}
for(int i=0; i<n; i++)
{
boolean conflict = false;
for(int j=0; j<m.length; j++)
{
if(i==m[j] || i-m[j]==m.length-j || m[j]-i==m.length-j)
{
conflict = true;
break;
}
}
if(!conflict)
{
int[] temp = new int[m.length+1];
System.arraycopy(m, 0, temp, 0, m.length);
temp[m.length] = i;
}
}
return ret;
}
public List<String[]> solveNQueens(int n) {
List<String[]> ret = new ArrayList<String[]>();
if(n<=0) return ret;
for(int[] matrix:getSolutions(new int[0], n))
{
String[] solve = new String[n];
for(int i=0; i<matrix.length; i++)
{
StringBuffer sb = new StringBuffer();
for(int j=0; j<matrix[i]; j++)
{
sb.append('.');
}
sb.append('Q');
for(int j=matrix[i]+1; j<n; j++)
{
sb.append('.');
}
solve[i] = sb.toString();
}
}
return ret;
}
``````

}

• An Iterative Solution. I am also doing the same thing only without recursion. I feel it was simpler then recursion.

``````bool ok(vector<int> &col, int c, int idx) {
// Validates last queen with all previous queens.
for (int i = 0; i < idx; i++)
if (col[i] == c || abs(col[i] - c) == abs(i - idx))
return false; // Clash!
return true;
}
vector<vector<string> > solveNQueens(int n) {
vector<int> col(n, 0);
vector<vector<string> > ans;
int row = 0;

while (1) {
if (row == n) {
// Generate string for this solution.
string str;
for (int i = 0; i < n; i++) str = str + ".";
vector<string> t(n, str);
for (int i = 0; i < n; i++) t[col[i]][i] = 'Q';
ans.push_back(t);

col[--row]++; // go back to previous row and increment that queen by 1 column.
}
else if (col[row] == n) {
col[row--] = 0;       // Reset this queen to column 0.
if (row == -1) break; // all cases checked! :)
col[row]++;           // go back to previous row and increment that queen by 1 column.
}
else if (!ok(col, col[row], row)) {
col[row]++; // problem at this column, so go to next column.
}
else row++;   // everything's perfect, lets go to queen in next row.
}
return ans;
} ``````

• This is an amusing code by Professer Song.

``````class Solution {
private:
int c, n;
vector<string> s;
vector<vector<string>> q;
public:
vector<vector<string> > solveNQueens(int n) {
q.clear();
this->n = n;
s.assign(n, string(n, '.'));
f(n, 0, 0, 0);
return q;
}
void f(int i, int l, int m, int r) {
if (! i)
q.push_back(s);
else
for (int x = (1<<n)-1&~(l|m|r); x; x &= x-1) {
int y = x & -x;
s[i-1][__builtin_ctz(y)] = 'Q';
f(i-1, (l|y)<<1, m|y, (r|y)>>1);
s[i-1][__builtin_ctz(y)] = '.';
}
}
};``````

• The Queen problem can be solved using permutations generation (http://en.wikipedia.org/wiki/Eight_queens_puzzle#Solution_construction) as well:

``````public class NQueens {
public List<String[]> solveNQueens(int n) {
//Initial permutation
int[] cols = new int[n];
for(int i = 0; i < n; i++) {
cols[i] = i;
}

//Iterate all permutations
List<String[]> out = new ArrayList<String[]>();
do{//n!
if(!isDiagonalThreat(cols)) {//O(n^2)
}
} while ((cols = perm(cols)) != null);

return out;
}

private String[] buildDisposition(int[] cols) {
String[] disposition = new String[cols.length];
for(int i = 0; i < disposition.length; i++) {
StringBuilder sb = new StringBuilder();
for(int j = 0; j < disposition.length; j++) {
sb.append(cols[i] == j ? 'Q' : '.');
}
disposition[i] = sb.toString();
}
return disposition;
}

//http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
private int[] perm(int[] cols) {
int i = cols.length-2;
while(i >=0 && cols[i] >= cols[i+1]) {
i--;
}
if(i == -1) {
return null;
}
int j = cols.length-1;
while(j>=0 && cols[i] >= cols[j]) {
j--;
}

//Swap
int tmp = cols[i];
cols[i] = cols[j];
cols[j] = tmp;

//Reverse
for(int k = 0;k < (cols.length-i-1)/2; k++) {
//Swap
tmp = cols[i+1+k];
cols[i+1+k] = cols[cols.length-1-k];
cols[cols.length-1-k] = tmp;
}
return cols;
}

//Check for diagonals attacks
private boolean isDiagonalThreat(int[] cols) {
for(int j = 0; j < cols.length; j++) {
for(int k = j+1; k < cols.length; k++) {
int delta = k-j;
if(cols[j]-delta == cols[k]
|| cols[j]+delta == cols[k]) {
return true;
}
}
}
return false;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.