N-Queens II (LeetCode Backtracking)

Question: Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.


Idea: Backtracking depth-first search. Since we can only place one queen in each row, we place the queens row by row. For each row, we try to place the queen in each column, if the placement is safe, then place the queen and go to the next row. When we reach row==n (out of boundary), that means the rows from 0=>n-1 is valid, add 1 to the result

Time: O(n^n) Space: O(n^2)

Code:

 public class Solution {  
   int counter;  
   public int totalNQueens(int n) {  
     if(n==0)  
       return 0;  
     counter=0;  
     char[][] board=new char[n][n];  
     for(int i=0;i<n;i++)  
       Arrays.fill(board[i],'.');  
     dfs(board,0);  
     return counter;  
   }  
   public void dfs(char[][] board,int curRow)  
   {  
     int n=board.length;  
     if(curRow==n)  
     {  
       counter+=1;  
       return;  
     }  
     for(int j=0;j<n;j++)  
     {  
       board[curRow][j]='Q';  
       if(isValid(board,curRow,j))  
       {  
         dfs(board,curRow+1);  
       }  
       board[curRow][j]='.';  
     }  
   }  
   public boolean isValid(char[][] board,int x,int y)  
   {  
     int n=board.length;  
     for(int i=0;i<n;i++)  
     {  
       for(int j=0;j<n;j++)  
       {  
         if(i!=x||j!=y)  
         {  
           if(i==x&&board[i][j]=='Q')  
             return false;  
           if(j==y&&board[i][j]=='Q')  
             return false;  
           if((i+j==x+y||i-j==x-y)&&(board[i][j]=='Q'))  
             return false;  
         }  
       }  
     }  
     return true;  
   }  
 }