[Leetcode][Backtracking] N-Queens [Sanpchat]

1. What
-NxN board
- Queen is expressed as 'Q' on the board and Empty is expressed as '.'
Play Rules:
-Rule1: Cannot place in the same row
-Rule2: Cannot place in the same column
-Rule3: Cannot place in diagonal

2. How
   2-1. So every time you place an Queen(called a move), you need a function to check if it is complied with all the rules.
   2-2. Then how to start the first move?
NOTE: start from row 0
   2-3 Space:O(NxN) to store all the characters in the board
   Improve?
   Space:O(N) since what we care is that for each column or row, does it have any Queen in there.     Thus,  we can just use an array called columnWithQueenForRow to record which column have Queen, e.g., columnWithQueenForRow[0] = 5 means in row 0, column 5 has a queen
   2-4. Time:O(n^n) Exponential ?
every row has N options N*N*N..*N = N^N
   2.5 return a List<String[]>, to make String[], we can use StringBuilder to append empty or Queen and then add each String[] into List for each row iteration
NOTE: when it's at the end of the row, create a String array to record current solution and put onto List

/*
Parameter: n, the size of board 
Return: List, whole board character 
*/
public class Solution
{
    public List solveNQueens(int n)
    {
         List res = new ArrayList();
         /*validate the input */
         if ( n == 0 )
         {
              return res;
         }
         helper(n, 0, new int[n], res);
         return res;
    }
    /* recursive function to keep placing move by going over column by column*/
    private void helper(int n, int row, int[] columnWithQueenForRow, List res )
    {
           // NOTE: return whole board String 
           if ( row == n )
           { 
                // NOTE: String[] to store current solution of all rows
                String[] item = new String[n]; 
                for (int i = 0 ; i < n; i++)
                {   
                    StringBuilder sb =new StringBuilder();
                    for (int j = 0; j < n ; j++ )
                    {
                         if ( columnWithQueenForRow[i] == j )
                         {
                              sb.append('Q');
                         }
                         else 
                         {
                              sb.append('.');
                         }
                    }
                    item[i] = sb.toString();
                }
                res.add(item);
                return;
           }
           for ( int j = 0 ; j  < n; j++ )
           {
                // NOTE: no need to clean value since if false, it goes to next iteration and will assign a new value to override it
                columnWithQueenForRow[row] = j;
                if ( check(row, columnWithQueenForRow) )
                {
                      helper(n, row+1, columnWithQueenForRow, res);
                }

           }

    }
    /* check legal move or not by checking if there any queen along that column */
    private boolean check (int row, int[] columnWithQueenForRow)
    {    

         // NOTE: avoid default column index 0 check, only compare with previous rows which are already being marked
         for (int i = 0 ; i < row;i++)
         {
             if ( columnWithQueenForRow[row] ==  columnWithQueenFor[i] || Math.abs( columnWithQueenForRow[row] - columnWithQueenForRow[i]) == Math.abs(row - i) )
             {
                   return false;
             }
         }
         return true;
    }
}