simple C++ backtrack solution


  • 0
    J
    class Solution {
    public:
        int totalNQueens(int n) {
            vector<vector<string>>board;
            string s;
            for(int i = 0;i<n;i++) s+=".";
            vector<string>res;
            for(int i = 0;i<n;i++) res.push_back(s);
            backtrack(0,n,res,board);
            return board.size();
        }
    private:    
        void backtrack(int m,int n,vector<string>&res,vector<vector<string>>&board)
        {
            if(m==n)
            {
                board.push_back(res);
                return;
            }
            for(int i = 0;i<n;i++)
            {
                if(canPlace(m,i,res))
                {
                   res[m][i]='Q';
                   backtrack(m+1,n,res,board);
                   res[m][i]='.';
                }
            }
        }
        bool canPlace(int m, int pos,vector<string> res)
        {
            for(int i = 0;i<m;i++)
            {
                string curr = res[i];
                int j = curr.find("Q");
                if(pos==j || abs(m-i)==abs(pos-j)) return false;
            }
            return true;
        }  
    };
    

Log in to reply
 

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