N Queens

Leetcode 51.

version 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    public List<List<String>> solveNQueens(int n) {
      List<List<String>> ans = new ArrayList<>();
      if(n == 3){
         return ans;
      }
      char[][] chessBoard = new char[n][n];
      for(char[] c: chessBoard){
         Arrays.fill(c,'.');
      }
      backtricking(ans,chessBoard,n,0);
      return ans;
    }
    public void backtricking(List<List<String>> ans,char[][] chessBoard,int n,int row){
      //backtricking stop condition 
      if(row == n){
        //collect the data        
       ans.add(transfer(chessBoard));
       return; 
      }
      
      //for loop for this layer 
      for(int col = 0; col < n;col++){
          //process the nodes
         if(isValid(row,col,chessBoard,n)){
             chessBoard[row][col] = 'Q';
             //recursion
             backtricking(ans,chessBoard,n,row+1);
             //undo the previous operations 
             chessBoard[row][col] = '.';
         }          
      }    
    }
    public boolean isValid(int row, int col,char[][] chessBoard,int n){
       //check the column 
       for(int i = 0; i < n;i++){
           if(chessBoard[i][col] == 'Q'){
             return false;
           }
       }
       //check the 45° diagonal
       for(int i = row - 1, j =col - 1;i>=0 && j>=0;i--,j--){
           if(chessBoard[i][j] == 'Q')
             return false;
       }
       //check the 135° diagonal
       for(int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--,j++){
           if(chessBoard[i][j] == 'Q')
             return false; 
       }
      return true; 
    }
    public List<String> transfer(char[][] chessBoard){
        List<String> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for(char[] value: chessBoard){
            for(char c: value){
                sb.append(c);
            }
          list.add(sb.toString());
          sb = new StringBuilder();
        }
        return list;  
    }
}

version 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    public List<List<String>> solveNQueens(int n) {
      List<String> list = new ArrayList<>();
      List<List<String>> ans = new ArrayList<>();
      if(n == 3){
         return ans;
      }
      char[][] chessBoard = new char[n][n];
      for(char[] c: chessBoard){
         Arrays.fill(c,'.');
      }
      backtricking(ans,list,chessBoard,n,0);
      return ans;
    }
    public void backtricking(List<List<String>> ans,List<String> list,char[][] chessBoard,int n,int row){
      //backtricking stop condition 
      if(row == n){
        //collect the data
        StringBuilder sb = new StringBuilder();
        //clean the list 
        list = new ArrayList<>();
        for(char[] value: chessBoard){
            for(char c: value){
                sb.append(c);
            }
          list.add(sb.toString());
          //clean the sb
          sb = new StringBuilder();
        } 
       ans.add(new ArrayList<>(list));
       return; 
      }
      
      //for loop for this layer 
      for(int col = 0; col < n;col++){
         if(isValid(row,col,chessBoard,n)){
             chessBoard[row][col] = 'Q';
             //backtricking
             backtricking(ans,list,chessBoard,n,row+1);
             //undo the previous operations 
             chessBoard[row][col] = '.';
         }          
      }
      
    }
    public boolean isValid(int row, int col,char[][] chessBoard,int n){
       //check the column 
       for(int i = 0; i < n;i++){
           if(chessBoard[i][col] == 'Q'){
             return false;
           }
       }
       //check the 45° diagonal
       for(int i = row - 1, j =col - 1;i>=0 && j>=0;i--,j--){
           if(chessBoard[i][j] == 'Q')
             return false;
       }
       //check the 135° diagonal
       for(int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--,j++){
           if(chessBoard[i][j] == 'Q')
             return false; 
       }
      return true; 
    }
}