1. class Solution {
  2.     /**
  3.     1. create a board matrix [n][n], assign every cell with character '.'
  4.     2. take boolean[][] visited matrix to keep track of current cell
  5.     3. call function placeQueens() by passing, board, visited, column index as 0 in params
  6.     4. In placeQueens() :
  7.         - iteratre over a row one by one to fill the valid positions with Queen 'Q'
  8.         - before filling check if current cell is valid cell or not by calling another function isValid()
  9.         - if it's valid cell, then assign Queen 'Q' at that position and call placeQueens() again by increment column++
  10.         - to backtrack asisgn cell with character '.'
  11.         - base condition will be when you reach last column of the board, then add construct result in format of string and add to list
  12.     5. in isValid() :
  13.         - checking for top-left diagonal attack:
  14.             - run a loop until row >=0 and col >=0
  15.             - if any cell [row][col] has Queen already placed, return false
  16.             - else decrement row-- and col--
  17.         
  18.         - checking for left attack:
  19.             - run a loop until col >=0
  20.             - if any cell [row][col] has Queen already placed, return false
  21.             - else decrement col--
  22.  
  23.         - checking for bottom-left diagonal attack:
  24.             - run a loop until row <n and col >=0
  25.             - if any cell [row][col] has Queen already placed, return false
  26.             - else decrement col-- and row++
  27.         - else return true
  28.     */
  29.     public boolean isValid(int row,int col,char[][] board)
  30.     {
  31.         int dup_row=row,dup_col=col;
  32.         // checking for top-left diagonal attack
  33.         while(row>=0 && col>=0)
  34.         {
  35.             if(board[row][col]=='Q')
  36.                 return false;
  37.             row--;
  38.             col--;
  39.         }
  40.         // checking for left attack
  41.         row=dup_row;
  42.         col=dup_col;
  43.         while(col>=0)
  44.         {
  45.             if(board[row][col]=='Q')
  46.                 return false;
  47.             col--;
  48.         }
  49.         // checking for bottom-left diagonal attack
  50.         row=dup_row;
  51.         col=dup_col;
  52.         while(row<board.length && col>=0)
  53.         {
  54.             if(board[row][col]=='Q')
  55.                 return false;
  56.             row++;
  57.             col--;
  58.         }
  59.         return true;
  60.     }
  61.     public List<String> construct(char[][] board)
  62.     {
  63.         List<String> ans=new ArrayList<String>();
  64.         for(int i=0;i<board.length;i++)
  65.         {
  66.             String s=new String(board[i]);
  67.             ans.add(s);
  68.         }
  69.         return ans;
  70.     }
  71.  
  72.     public void placeQueen(int col,char[][] board,List<List<String>> ans)
  73.     {
  74.         if(col==board.length)
  75.         {
  76.             ans.add(construct(board));
  77.             return;
  78.         }
  79.         for(int row=0;row<board.length;row++)
  80.         {
  81.             if(isValid(row,col,board))
  82.             {
  83.                 board[row][col]='Q';
  84.                 placeQueen(col+1,board,ans);
  85.                 board[row][col]='.';
  86.             }
  87.         }
  88.     }
  89.  
  90.     public List<List<String>> solveNQueens(int n) 
  91.     {
  92.         List<List<String>> ans=new ArrayList<>();
  93.         char[][] board=new char[n][n];
  94.         for(int i=0;i<n;i++)
  95.         {
  96.             for(int j=0;j<n;j++)
  97.             {
  98.                 board[i][j]='.';
  99.             }
  100.         }
  101.         int[][] visited=new int[n][n];
  102.         placeQueen(0,board,ans);
  103.         return ans;
  104.     }
  105. }