Output Limit Exceed Can you help me?


  • 0
    L
    class Solution {
    public:
        bool check(vector<int> cols, int i, int j)
        {
            if(i == 0)
            {
                return true;
            }
           if(cols[j] >= 0)
           {
               return false;
           }
           if(j != 0 && cols[j-1] == i-1 )
           {
               return false;
           }
           if(j !=  cols.size() - 1 && cols[j-1] == i-1)
           {
               return false;
           }
           return true;
        }
        void subQ(vector<vector<string>>&ret, vector<string> result,vector<int> cols,int i, int n)
        {
            if(i == n)
            {
                ret.push_back(result);
                return;
            }
            for(int j = 0; j < n; j++)
            {
                if(check(cols,i,j))
                {
                    cols[j] = i;
                    result[i][j] = 'Q';
                    subQ(ret,result,cols,i+1,n);
                    cols[j] = INT_MIN;
                    result[i][j] = '.';
                }
            }
        }
        vector<vector<string> > solveNQueens(int n) {
            vector<vector<string>> ret;
            if(n == 1)
            {
                vector<string>result;
                result.push_back("Q");
                ret.push_back(result);
                return ret;
            }
            if(n <4)
            {
                return ret;
            }
            string str = "";
            for(int i = 0; i < n; i++)
            {
                str += ".";
            }
            vector<string> result;
            for(int i = 0; i < n; i++)
            {
                result.push_back(str);
            }
            vector<int> cols(n,INT_MIN);
            subQ(ret,result,cols,0,n);
            return ret;
        }
    };

  • 0
    O

    You got this error simply because your result was wrong. More solutions than the correct answer were generated. You can simply output the number of solutions for each n-queen problems to check with that.
    (The correct answer could be found in wiki.)


  • 0

    In the N-queens problem, any two queens can not be on the same row, the same column or the same diagonal, but you have no check on if they are on the same diagonal.

    Here is my code:

    Directly verify the validity of each position, 12ms:

    class Solution {
    public:
        std::vector<std::vector<std::string> > solveNQueens(int n) {
            std::vector<std::vector<std::string> > res;
            size = n;
            std::vector<std::string> nQueens(size, std::string(size, '.'));
            solveNQueens(res, nQueens, 0);
            return res;
        }
    private:
        int size;
        void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, int row) {
            if (row == size) {
                res.push_back(nQueens);
                return;
            }
            for (int col = 0; col != size; ++col)
                if (isValid(nQueens, row, col)) {
                    nQueens[row][col] = 'Q';
                    solveNQueens(res, nQueens, row + 1);
                    nQueens[row][col] = '.';
                }
        }
        bool isValid(std::vector<std::string> &nQueens, int row, int col) {
            for (int i = 0; i != row; ++i)
                if (nQueens[i][col] == 'Q')
                    return false;
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
                if (nQueens[i][j] == 'Q')
                    return false;
            for (int i = row - 1, j = col + 1; i >= 0 && j < size; --i, ++j)
                if (nQueens[i][j] == 'Q')
                    return false;
            return true;
        }
    };
    

    or use a flag vector as bitmask, 4ms:

    class Solution {
    public:
        std::vector<std::vector<std::string> > solveNQueens(int n) {
            std::vector<std::vector<std::string> > res;
            size = n;
            std::vector<std::string> nQueens(size, std::string(size, '.'));
            /*
            A total of N columns, index 0 to N-1 to mask if this column had a Queen.
            A total of 2*N-1 45° diagonals, index N to 3*N-2 to mask if this diagonal had a Queen.
            A total of 2*N-1 135° diagonals, index 3*N-1 to 5*N-3 to mask if this diagonal had a Queen.
            */
            std::vector<int> flag(5 * size - 2, 1);
            solveNQueens(res, nQueens, flag, 0);
            return res;
        }
    private:
        int size;
        void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, std::vector<int> &flag, int row) {
            if (row == size) {
                res.push_back(nQueens);
                return;
            }
            for (int col = 0; col != size; ++col)
                if (flag[col] && flag[col + row + size] && flag[col - row + 4 * size - 2]) {
                    flag[col] = flag[col + row + size] = flag[col - row + 4 * size - 2] = 0;
                    nQueens[row][col] = 'Q';
                    solveNQueens(res, nQueens, flag, row + 1);
                    nQueens[row][col] = '.';
                    flag[col] = flag[col + row + size] = flag[col - row + 4 * size - 2] = 1;
                }
        }
    };

Log in to reply
 

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