# From 4ms to 0ms solution in C, well-commented

• ``````//Used to test whether the column of the next row conflicts with the current arrangement;
//the stack storing the column index for each row;
//top is a pointer pointing to the top of the stack also a row index;
//n is the size of the board;
//col is the column of the next row;
bool conflict(int* stack, int top, int n, int col)
{
double slope;
int d = 1; // the distance between two different rows - compared to the new row;
while(top > -1)
{
slope = (col-stack[top--]) / (double)(d++);
if(slope == 0 || slope == 1 || slope == -1)
return true;
}
return false;
}

//Used to find the next new row and corresponding column that is
//suitable for the arrangement and then return its new row index
//and the new suitable column which will be stored in stack;
int backtrack(int* stack, int top, int n)
{
while(true)
{
while(top > -1 && stack[top]+1 == n) top--; // if the current row reached its final column, search for its previous row;
if(top == -1) //if row index reaches its end, return -1;
int col = stack[top] + 1; // test next column for the suitable row;
while(col < n) // test all the remained columns of the row until it's okay with the current arrangement, if not go back to select another row in the previous section;
{
stack[top] = col;
if(conflict(stack, top-1, n, col))
col++;
else
}
}
}

//AC - 4ms;
int totalNQueens(int n)
{
//handle special cases;
if(n == 1)
return 1;
if(n < 4)
return 0;
// stack is used to store the column index for each row - the row index is indicated by the stack index for example stack[0]=1 means the first row takes the second column;
int* stack = (int*)malloc(sizeof(int)*n);
int top; //the index pointing to the top of the stack;
int count = 0; //used to count the viable arrangement;
int pre = 0; //record the previous viable row index;
int start = 0; //used to record the beginning row index for the next round;
for(int i = 0; i < n; i++)
{
if(start > i)
i = start;
top = -1;
stack[++top] = i;
while(top < n)
{
for(int j = 0; j < n; j++)
{
if(conflict(stack, top, n, j))
continue;
else
{
stack[++top] = j;
break;
}
}
if(pre == top || top == n-1) //ensure the previous loop will increase top;
{//backtracking until there is an valid row and column arrangement;
if(top == n-1)
count++;
while((top=backtrack(stack, top, n)) == n-1)
count++;
if(top == -1)
return count;
if(top == 0) //record the start column for next round;
start = stack[top]+1;
}
pre = top;
}
}
return count;
}
``````

``````void traverse(int row, int size, bool* col, bool* fslash, bool* bslash, int* count)
{
if(row == size)
{
(*count)++;
return;
}
for(int j = 0; j < size; j++)
{
if(col[j] && fslash[row+j] && bslash[row+size-j])
{
col[j] = fslash[row+j] = bslash[row+size-j] = false;
traverse(row+1, size, col, fslash, bslash, count);
col[j] = fslash[row+j] = bslash[row+size-j] = true;
}
}
}

//AC - 0ms;
int totalNQueens(int n)
{
bool* col=(bool*)malloc(sizeof(bool)*n);
for(int i = 0; i < n; i++)
col[i] = true;
bool* fslash=(bool*)malloc(sizeof(bool)*(2*n));
bool* bslash=(bool*)malloc(sizeof(bool)*(2*n));
for(int i = 0; i < 2*n; i++)
{
fslash[i] = true;
bslash[i] = true;
}
int count = 0;
traverse(0, n, col, fslash, bslash, &count);
return count;
}``````

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