NQueen DFS Java 13 ms runtime


  • 0
    A
    
    public List<List<String>> solveNQueens(int n) {
    
      Stack<Position> queenPositions = new Stack<>();  
      List<List<String>> result = new ArrayList<>();
      solveNQueensInner(0, n, queenPositions,result);
      return result;
    }
    
    private void solveNQueensInner(int row, int n, Stack<Position> queenPositions, List<List<String>> result){
    
       if (row == n){
          addResult(queenPositions, result, n);
          return;
       }
        	
        for (int col = 0; col < n; col++){
        
           boolean foundSafe = validate(queenPositions, row, col);
           if (foundSafe){
        	  queenPositions.add(new Position(row, col));
        	  solveNQueensInner(row+1, n, queenPositions, result);	
        	  queenPositions.pop();    
        	}
        }
    }
        
    private boolean validate(Stack<Position> queenPositions, int row, int col){
        	for (Position queenPos : queenPositions){
        		if (queenPos.row == row || queenPos.col == col || //same row or col
        			queenPos.row- queenPos.col == row - col || //or diagonally across
        			queenPos.row+queenPos.col == row+col){
        			
        			return false; //under attack from that queen
        		}	
        	}
        	
        	return true;
    }
    
    private void addResult(Stack<Position> queenPositions,  List<List<String>> result, int n){
        	List<String> list = new ArrayList<>();
        	for (Position p: queenPositions){
    			int colPos = p.col;
    			
    			StringBuilder sb = new StringBuilder();
    			for (int i = 0; i < n; i++){
    				if (i == colPos){
    					sb.append("Q");
    					continue;
    				}
    				sb.append(".");
    			}
    			list.add(sb.toString());
    		 }	
        	
        	result.add(list);
        }
        
        class Position{
    	   int row;
    	   int col;
    	   
    	   public Position(int row, int col){
    		   this.row=row;
    		   this.col = col;
    	   }
       } 
    }```

Log in to reply
 

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