# [C language] 6 ms, with explanation

1. Obviously, one and only one queen located in each row. Thus we create an array (1*n) to store the column index for the queens in each row.
E.g. in case of n = 4, pos[4] = {1,3,0,2} means the 4 queens located at [0,1][1,3][2,0][3,2].
2. Fix the positions of queen row-by-row, recursively.
3. For saving time, it is not necessary to check all the queens existed on the board. We can only check, if the new queen (k-th row) would attack pervious queens (0-th row ~ (k-1)-th row), due to the recursive solution.

int *pos;
// the position of n queens

bool checkValid(int *pos, int newRowIdx) //check if the new queen would attack others, after it join the gruop
{
int i;
int a,b,c;
a = pos[newRowIdx];
b = newRowIdx + pos[newRowIdx];
c = newRowIdx - pos[newRowIdx];
for(i=0; i<newRowIdx; i++)
{
if ((pos[i] == a)||((i+pos[i]) == b)||((i-pos[i]) == c))
return false;
}
return true;
}

void solution(int *pos, int n, int currRowIdx, char **res, int returnSize) //Recursive solution
{
int i,j,k;
for(i=0; i<n; i++)
{
pos[currRowIdx] = i;
if (checkValid(pos, currRowIdx))
{
if (currRowIdx == (n-1)) //n queens are all solved
{
res[returnSize] = (char
)malloc(sizeof(char
)n);
for(j=0;j<n;j++)
{
res[returnSize][j] = (char)malloc(sizeof(char)
(n+1));
for(k=0;k<n;k++)
{
if (pos[j] == k)
res[*returnSize][j][k] = 'Q';
else
res[*returnSize][j][k] = '.';
}
res[*returnSize][j][n] = '\0';
}
(*returnSize)++;
}
else // solve the next row
solution(pos, n, currRowIdx+1, res, returnSize);
}
}
}

char*** solveNQueens(int n, int* returnSize)
{
char res;
pos = (int
)malloc(sizeof(int)n);
memset(pos, 0, sizeof(int)n);
res = (char
)malloc(sizeof(char
*)*10000);
*returnSize = 0;
solution(pos, n, 0, res, returnSize);
free(pos);
return res;
}

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