# 4MS recursion solution

• ``````bool check(int x, int y, int n, char ** plane)
{
for (int i=x+1; i<n; ++i)
{
if(plane[i][y] == 'Q')
return false;
}
for (int i=1; x+i<n && y+i<n; ++i)
{
if(plane[x+i][y+i] == 'Q')
return false;
}
for (int i=1; x+i<n && y-i>=0; ++i)
{
if(plane[x+i][y-i] == 'Q')
return false;
}
return true;
}
void out_plane(char**** rlt, int returnSize, char** plane, int n)
{
*rlt = (char***)realloc(*rlt, returnSize * sizeof(char**));
(*rlt)[returnSize - 1] = (char**)malloc(sizeof(char*) * n);
for (int j=0; j<n; ++j)
{
(*rlt)[returnSize - 1][j] = (char*)malloc((n+1)*sizeof(char));
for (int k=0; k<n; ++k)
{
(*rlt)[returnSize - 1][j][k] = plane[j][k];
}
(*rlt)[returnSize - 1][j][n] = '\0';
}
}
void set_a_quene(int row, int n, int * returnSize, char**** rlt, char** plane)
{
for (int i=0; i<n; i++)
{
if(check(row, i, n, plane))
{
memset(plane[row], '.', n);
plane[row][i] = 'Q';

if(row == 0)
{
(*returnSize)++;

out_plane(rlt, *returnSize, plane, n);
}
else
{
set_a_quene(row-1, n, returnSize, rlt, plane);
}
}
}
}
char*** solveNQueens(int n, int* returnSize) {
*returnSize = 0;
char *** rlt = (char ***)malloc(sizeof(char **));
char **plane = (char **)malloc(sizeof(char*) * n);
for (int i=0; i<n; ++i)
{
plane[i] = (char*)malloc(n+1);
memset(plane[i], '.', n);
plane[n] = '\0';
}
set_a_quene(n-1, n, returnSize,&rlt, plane);
return *returnSize?rlt:NULL;
}``````

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