Leetcode 51 N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

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

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

Solution 1: DFS, each row can have only one 'Q', use this condition will simplify the result a lot;

 public class Solution {  
   public List<List<String>> solveNQueens(int n) {  
     char[][] matrix=new char[n][n];  
     for (int i=0; i<n; i++) Arrays.fill(matrix[i],'.');  
     List<List<String>> res=new ArrayList<>();  
     dfs(0,n,matrix,res);  
     return res;  
   }  
   private void dfs(int row, int n, char[][] matrix, List<List<String>> res) {  
     if (row==n) {  
       List<String> one=new ArrayList<>();  
       for (int i=0; i<n; i++) one.add(new String(matrix[i]));  
       res.add(one);  
     }  
     else {  
       for (int i=0; i<n; i++) {  
         if (validate(matrix,row,i,n)) {  
           matrix[row][i]='Q';  
           dfs(row+1,n,matrix,res);  
           matrix[row][i]='.';  
         }  
       }  
     }  
   }  
   private boolean validate(char[][] matrix, int i, int j, int n) {  
     for (int k=1; i-k>=0; k++) //check top  
       if (matrix[i-k][j]=='Q') return false;  
     for (int k=1; i-k>=0 && j-k>=0; k++) //check top left  
       if (matrix[i-k][j-k]=='Q') return false;  
     for (int k=1; i-k>=0 && j+k<n; k++) //check top right  
       if (matrix[i-k][j+k]=='Q') return false;  
     return true;  
   }  
 }