My code : 40ms 1.Using row,column,diagonal bit map for fast check. 2. Using stack for DFS.


  • 3
    L
    class Solution {
    public:
        struct Point
        {
            int x; 
            int y; // row
            int state;
            // 0 push next level node or end
            // 1 try same level next node
            Point(int px, int py): 
               x(px),
               y(py)
            {
                state = 0;
            }
        };
        int m_n;
        std::vector<int> col;
        std::vector<int> row;
        std::vector<int> dia[2];
        // 0 y- x = n
        // 1 y + x = n
        void Set(const Point& p)
        {
            int x = p.x;
            int y = p.y;
            col[x] = 1;
            row[y] = 1;
            int d0 = y - x + m_n -1; 
            int d1 = x + y;
            dia[0][d0] = 1;
            dia[1][d1] = 1;
        }
        bool Check(const Point& p)
        {
            int x = p.x;
            int y = p.y;
            int d0 = y - x + m_n -1; 
            int d1 = x + y;
            if (col[x] == 0 && row[y] == 0 && dia[0][d0] == 0 && dia[1][d1] == 0)
            {
                return true;
            }
            return false;
        }
        void Remove(const Point& p)
        {
            int x = p.x;
            int y = p.y;
            int d0 = y - x + m_n -1; 
            int d1 = x + y;
            
            col[x] = 0;
            row[y] = 0;
            dia[0][d0] = 0;
            dia[1][d1] = 0;
        }
        void Add(vector<vector<string> >& res, std::stack<Point> S)
        {
            vector<string> vec1;
            res.push_back(vec1);
            vector<string>& vec = res[res.size() - 1];
            
            vector<Point> vp;
            while(!S.empty())
            {
                vp.push_back(S.top());
                S.pop();
            }
            vec.resize(m_n);
            for (int i = 0; i < vp.size(); i++)
            {
                
                
                string& s = vec[i];
                s.resize(m_n);
                for(int j = 0; j < m_n; j++)
                {
                    if (j == vp[i].x)
                    {
                        s[j] = 'Q';
                    }
                    else
                    {
                        s[j] = '.';
                    }
                }
                
            }
        }
        vector<vector<string> > solveNQueens(int n) {
            std::stack<Point> S;
            vector<vector<string> > res;
            m_n = n;
            if (n < 1)
            {
                return res;
            }
            if (n == 1)
            {
                vector<string> vec;
                vec.push_back("Q");
                res.push_back(vec);
                return res;
            }
            col.resize(n);
            row.resize(n);
            dia[0].resize(2*n);
            dia[1].resize(2*n);
            for (int i = 0; i < n; i++)
            {
                col[i] = 0;
                row[i] = 0;
                
            }
            for (int i = 0; i < 2*n; i++)
            {
                dia[0][i] = 0;
                dia[1][i] = 0;
            }
            
            S.push(Point(0,0));
            Set(S.top());
            while(!S.empty())
            {
                Point& p = S.top();
                if (p.state == 0)
                {
                    p.state = 1;
                    if (p.y == n - 1)
                    {
                        Add(res, S);
                    }
                    else
                    {
                        int y = p.y + 1;
                        for (int x = 0; x < n; x++)
                        {
                            if (Check(Point(x, y)))
                            {
                                S.push(Point(x, y));
                                Set(S.top());
                                break;
                            }
                        }
                    }
                }
                else if (p.state == 1)
                {
                    int y = p.y;
                    int x = p.x + 1;
                    Remove(p);
                    S.pop();
                    for (; x < n; x++)
                    {
                        if (Check(Point(x, y)))
                        {
                            S.push(Point(x, y));
                            Set(S.top());
                            break;
                        }
                    }
                }
            }
            return res;
        }
    };

  • 0
    L
    This post is deleted!

  • 1
    L

    Space complexity : Instead of using a 2D array to represent the chess board, i am using a 1D array , the index of which would represent the row number and the value of arr at row index will be the column number for the correct position of the queen.

    i.e

           Instead of doing  arr[row][col]=1
           i am using arr[row]=col ;               where queen is positioned at (row,col);
    

    Logic : DFS for every column number ,ranging from 0 to n-1, for all the rows from 0 to n-1 and check the validity of queen position for every row,col combination(using isSafe function)

    isSafe function : It checks whether the queen in current position(r,c) is being attacked by any of the r-1 queens positioned in row numbers 0 through r-1.

     class Solution {
        public:
            vector < vector <string> > sol;
            int limit;
            
            vector<string> toChessString(vector<int> arr) 
              {
                string s(arr.size(),'.');
                vector<string> ans(arr.size(),s);
        
                for(int i=0 ; i<arr.size() ; i++)
                  ans[i][arr[i]]='Q';
        
                  return ans;
              }
        
        
            bool isSafe(vector<int> arr, int r , int c )
             {
                int check;
                for(int row=r-1,ldia=c-1,rdia=c+1 ; row>=0 ; row--,ldia--,rdia++)
                {
                    check=arr[row];
        
                    if(check==c || check==ldia || check==rdia)
                     return false;
                }
                return true;
             }
        
            void solveNqueen(vector<int> arr , int r , int c)
            {
                if(r==limit)
                 sol.push_back(toChessString(arr));
                    
                else
                 {
                     for(int col=c ; col<limit ; col++)
                     {
                        arr[r]=col;
        
                        if(isSafe(arr,r,col))
                          solveNqueen(arr,r+1,0);
                     }
                 }
            }
        
        
            vector<vector<string> > solveNQueens(int n) {
                vector<int> arr(n,0);
                limit=n;
                solveNqueen(arr,0,0);
              
                return sol;
            }
        };

Log in to reply
 

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