class Solution {
    /**
    1. create a board matrix [n][n], assign every cell with character '.'
    2. take boolean[][] visited matrix to keep track of current cell
    3. call function placeQueens() by passing, board, visited, column index as 0 in params
    4. In placeQueens() :
        - iteratre over a row one by one to fill the valid positions with Queen 'Q'
        - before filling check if current cell is valid cell or not by calling another function isValid()
        - if it's valid cell, then assign Queen 'Q' at that position and call placeQueens() again by increment column++
        - to backtrack asisgn cell with character '.'
        - base condition will be when you reach last column of the board, then add construct result in format of string and add to list
    5. in isValid() :
        - checking for top-left diagonal attack:
            - run a loop until row >=0 and col >=0
            - if any cell [row][col] has Queen already placed, return false
            - else decrement row-- and col--
        
        - checking for left attack:
            - run a loop until col >=0
            - if any cell [row][col] has Queen already placed, return false
            - else decrement col--

        - checking for bottom-left diagonal attack:
            - run a loop until row <n and col >=0
            - if any cell [row][col] has Queen already placed, return false
            - else decrement col-- and row++
        - else return true
    */
    public boolean isValid(int row,int col,char[][] board)
    {
        int dup_row=row,dup_col=col;
        // checking for top-left diagonal attack
        while(row>=0 && col>=0)
        {
            if(board[row][col]=='Q')
                return false;
            row--;
            col--;
        }
        // checking for left attack
        row=dup_row;
        col=dup_col;
        while(col>=0)
        {
            if(board[row][col]=='Q')
                return false;
            col--;
        }
        // checking for bottom-left diagonal attack
        row=dup_row;
        col=dup_col;
        while(row<board.length && col>=0)
        {
            if(board[row][col]=='Q')
                return false;
            row++;
            col--;
        }
        return true;
    }
    public List<String> construct(char[][] board)
    {
        List<String> ans=new ArrayList<String>();
        for(int i=0;i<board.length;i++)
        {
            String s=new String(board[i]);
            ans.add(s);
        }
        return ans;
    }

    public void placeQueen(int col,char[][] board,List<List<String>> ans)
    {
        if(col==board.length)
        {
            ans.add(construct(board));
            return;
        }
        for(int row=0;row<board.length;row++)
        {
            if(isValid(row,col,board))
            {
                board[row][col]='Q';
                placeQueen(col+1,board,ans);
                board[row][col]='.';
            }
        }
    }
    
    public List<List<String>> solveNQueens(int n) 
    {
        List<List<String>> ans=new ArrayList<>();
        char[][] board=new char[n][n];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                board[i][j]='.';
            }
        }
        int[][] visited=new int[n][n];
        placeQueen(0,board,ans);
        return ans;
    }
}