C++ straightforward dfs + backtracking, no bitmask


  • 0
    // construct a solution with column numbers
    void addSolution(vector<vector<string>>& ans, vector<int>& queenCols, int n) {
    	vector<string> sol(n, string(n, '.'));
    	for (int i = 0; i < n; i++) {
    		if (queenCols[i] != -1)
    			sol[i][queenCols[i]] = 'Q';
    	}
    	ans.push_back(sol);
    }
    
    void dfs(int row, vector<int>& queenCols, int n, vector<vector<string>>& ans) {
    	if (row == n)
    		addSolution(ans, queenCols, n);
    	// try each position
    	for (int i = 0; i < n; i++) {
    		bool validCol = true;
    		for (int j = 0; j < row; j++) {
    			// if ith column has been chosen before or if it is in the same diagonal with one of the previous
    			// column numbers, j-th column isn't valid
    			if (queenCols[j] == i || row - j == abs(i - queenCols[j])) {
    				validCol = false;
    				break;
    			}
    		}
    		// if valid, do dfs with backtracking
    		if (validCol) {
    			queenCols[row] = i;
    			dfs(row + 1, queenCols, n, ans);
    			queenCols[row] = -1;
    		}
    	}
    }
    
    vector<vector<string>> solveNQueens(int n) {
    	if (n < 1)
    		return vector<vector<string>>();
    	vector<vector<string>> ans;
    	// queenCols[i] is the column number of the Queen we place on the i-th row
    	vector<int> queenCols(n, -1);
    	dfs(0, queenCols, n, ans);
    	return ans;
    }
    

Log in to reply
 

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