C++ easy backtracking solution.


  • 0
    S
    struct rowCol {
    	int row;
    	int col;
    	rowCol(int r, int c) {
    		row = r;
    		col = c;
    	}
    };
    class Solution {
    public:
    	bool check(int row, int col, vector<rowCol*>& history) {
    		//check diagonals
    		for (auto i : history) {
    			if (abs(i->row - row) == abs(i->col - col))
    				return 0;
    		}
    		//check columns
    		for (auto i : history) {
    			if (i->col == col)
    				return 0;
    		}
    		return 1;
    	}
    	void recurse(vector<rowCol*>& history, int row, int n,vector<string>& res,vector<vector<string>>& result) {
    		if (row < n) {
    			for (int j = 0; j < n; j++) {
    				if (check(row, j, history)) {
    					std::string x(n, '.');
    					history.push_back(new rowCol(row, j));
    					x[j] = 'Q';
    					res.push_back(x);
    					if (res.size() == n) {
    						result.push_back(res);
    					}
    					recurse(history, row+1, n, res,result);
    					res.pop_back();
    					history.pop_back();
    				}
    			}
    
    		}
    	}
    	vector<vector<string>> solveNQueens(int n) {
    		vector<vector<string>> result;
    		vector<rowCol*> history;
    		vector<string> res;
    		recurse(history, 0, n,res,result);
    		return result;
    	}
    };
    
    

Log in to reply
 

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