[Backtracking] N-Queens

1. Example

row         : two queens cannot be placed in the same row
column   : two queens cannot be placed in the same column
diagonal : two queens cannot be placed in the diagonal position


[
[".Q..", // Solution 1
 "...Q",
 "Q...",
 "..Q."],

 ["..Q.", // Solution 2
 "Q...",
 "...Q",
 ".Q.."]
]

Q1: '.' or 'Q'
A1: board => n^2 for time and space
Q1: how to check?
A1: valid (i,j) = > queenatcolumn[i] != -1 => OCCUPIED
                            any i make  j   == queenatcolumn[i], i =0-n-1 => OCCUPIED
|i-rowIndex |  == |column -queenatcolumn[rowIndex] |, for all queenatcolumn[i], i = 0~ n-1
Q
   Q     |1-0| == |1-0|
    Q
Q       | 1-0| =| 0-1|
like above case
row1   1
row2   3
row3   0
row4   2
Q1: how to iterate?

A1: 

2. Implementation
//NOTE

QueenAtColumn[row] = j; if ( isValid(row, QueenAtColumn) ) helper(n, row+1, QueenAtColumn, res);

// Time:O(n), Space:O(n) call stack 
public List solveNQueens(int n)
{
    


     List res = new ArrayList();
     if (n <= 0)
          return res;
    
    
     helper(n, 0,new int[]  ,res );



     return res;



}
//private void helper( int n, int start ,int[] QueenAtColumn, List res  )
private void helper( int n, int row ,int[] QueenAtColumn, List res  )
{




     if ( row == n)
     {
          String[] item = new String[n]; 
          for (int i =0 ; i < n;i++)
          {
              StringBuilder sb = new StirngBuilder(); 
              for (int j = 0; j < n; j++ )
              {     
                  if ( QueenAtColumn[i] == j)
                       sb.append('Q');
                  else 
                       sb.appned('.');
              }
              item[i] = sb.toStirng();   
          }
          res.add(item);
          return;
     }




     for (int j =0; j < n; j++)
     {
         QueenAtColumn[row] = j;
         if (  isValid(row, QueenAtColumn) ) 
               helper(n, row+1, QueenAtColumn, res);     
     }




}
//private boolean isValid (int row, int column ,int[] QueenAtColumn)
//private boolean isValid (int row,int[] QueenAtColumn)

{
        

    // check row
    //if ( QueenAtColumn[row] !=  )
    //     return false;


    // check column
    //for (int i = 0 ; i < n ; i++)
    //{
    //     //if ( QueenAtColumn[i] == column )
    //          return false;
    //}



    // check diagonal NOTE: AND COLUMN
    for (int i = 0; i < n; i++)
    {
         //if ( Math.abs(row-i) == Math.abs(QueenAtColumn[i] - column ))
         if ( Math.abs(row-i) == Math.abs(QueenAtColumn[i]-QueenAtColumn[row])  || QueenAtColumn[row] == QueenAtColumn[i] )
              return false;
    }



    return true;


  
}

3. Similar ones
N-Queens II
Sudoku solver