[C language] 6 ms, with explanation


  • 0
    X
    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;
    }


Log in to reply
 

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