8ms c++ iterative solution using a stack


  • 0
    A
    class Solution {
    private:
        //returns false whenever there is a queen on a line or a diagonal that contains the current cell (row,col)
    	bool checkOk(int row, int col, const vector<int>& grid)
    	{
    		for (int i = 0; i<row; ++i)
        		if (grid[i] == col || grid[i] == col - (row - i) || grid[i] == col + (row - i))
        			return false;
    		return true;
    	}
    	
    	//creates the table as a vector of strings
    	vector<string> exportGridToString(const vector<int>& grid)
    	{
    		int n = grid.size();
    		vector<string> stringifiedGrid(n,string(n, '.'));
    		for (int i = 0; i < n; ++i)
    		    stringifiedGrid[i][grid[i]] = 'Q';
    		return stringifiedGrid;
    	}
    
    public:
    	vector<vector<string>> solveNQueens(int n) {
    		stack<int> cols;   //keeps track of the columns used to get the current position
    		int row = 0, col = 0; 
    		vector<int> grid(n, 0); //1D array where each index is a row, and the associated value is the column number
    		vector<vector<string>> result;
    		while (col < n || row != 0) 
    		{
    			if (checkOk(row, col, grid) && row<n) //if the queen can be placed at the current position
    			{
    				grid[row] = col;  //update the current grid
    				cols.push(col);  //keep track of the current column value before going to the next row
    				col = 0;
    				++row;  //go to the next row
    				if (row == n)  //end of the grid
    					result.push_back(exportGridToString(grid));
    			}
    			else //if row=n we need to keep on going as if the previous grid was not right
    			{
    				++col;
    				while (col >= n && !cols.empty() || row >= n)
    				{
    					col = cols.top() + 1;
    					cols.pop();
    					--row;
    				}
    			}
    		}
    		return result;
    	}
    

    };


Log in to reply
 

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