[C language] 6 ms, with explanation

  • 0
    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
    res[returnSize][j] = (char)malloc(sizeof(char)
    if (pos[j] == k)
    res[*returnSize][j][k] = 'Q';
    res[*returnSize][j][k] = '.';
    res[*returnSize][j][n] = '\0';
    else // solve the next row
    solution(pos, n, currRowIdx+1, res, returnSize);

    char*** solveNQueens(int n, int* returnSize)
    char res;
    pos = (int
    memset(pos, 0, sizeof(int)n);
    res = (char
    *returnSize = 0;
    solution(pos, n, 0, res, returnSize);
    return res;

Log in to reply

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