Collection of solutions in Java


  • 3
    E

    This post is mainly for myself as I learnt a lot from all kinds of solutions posted under this question. The copyright goes to the original author :)

    Click on the title of each method and you can see the original author's explanations (if there is any).

    #Java accepted clean solutions, >98.73% by yunli2015#

    public class Solution {
        int count=0;
        public int totalNQueens(int n) {
            dfs(new int[n],0,n);
            return count;
        }
        public void dfs(int[] pos,int step,int n) {
            if(step==n) {
                count++;
                return;
            }
            for(int i=0;i<n;i++) {
                pos[step]=i;
                if(isvalid(pos,step)) dfs(pos,step+1,n);
            }
        }
        public boolean isvalid(int[] pos, int step) {
            for(int i=0;i<step;i++) {
                if(pos[i]==pos[step]||(Math.abs(pos[i]-pos[step]))==(step-i)) return false;
            }
            return true;
        } 
    }
    

    essentially the same one:
    #Share. Java, 3ms, recurrsion, backtracing, very easy to understand. by Yuan__Yuan#

    public class Solution {
        public int totalNQueens(int n) {
            if (n == 0)
                return 0;
            int[] q = new int[n];
            return track(q, 0);
        }
        
        private int track(int[] q, int row) {
            if (row == q.length)
                return 1;
            int solutions = 0;
            for (int i = 0; i < q.length; i++) {
                q[row] = i;
                if (isValid(q, row, i)) {
                    solutions += track(q, row + 1);
                }
            }
            return solutions;
        }
        
        private boolean isValid(int[] q, int row, int col) {
            for (int i = 0; i < row; i++) {
                if (q[i] == col || Math.abs(row - i) == Math.abs(col - q[i]))
                    return false;
            }
            return true;
        }
    }
    

    #My own tedious code#

    public class Solution {
        private int counter = 0;
        public int totalNQueens(int N) {
            for(int i=0; i<N; i++) {
                char[][] board = new char[N][N];
                board[i][0] = 'Q';
                solve(board, N, 1);
            }
            return counter;
        }
        private boolean isSafe(char[][] board, int N, int row, int col) {
            for(int i=0; i<N; i++) {
                if(board[i][col]!=0) return false;
                if(board[row][i]!=0) return false;
            }
        
            int step = 1;
            step = 1;
            while(row-step>=0 && col-step>=0) {
                if(board[row-step][col-step]!=0) return false;
                ++step;
            }
            step = 1;
            while(row+step<N && col-step>=0) {
                if(board[row+step][col-step]!=0) return false;
                ++step;
            }
            return true;
        }
        private boolean solve(char[][] board, int N, int col) {
            if(col==N) {
                ++counter; 
                return false;
            }
            for(int i=0; i<N; i++) {
                if(isSafe(board, N, i, col)) {
                    board[i][col] = 'Q';
                    if(solve(board, N, col+1)) return true;
                    else {
                        board[i][col] = 0;
                    }
                }
            }
            return false;
        }
    }
    

    #Pretty simple JAVA solution by EvelynGuo#

    public class Solution {
      Set<Integer> col = new HashSet<Integer>();
      Set<Integer> diag1 = new HashSet<Integer>();
      Set<Integer> diag2 = new HashSet<Integer>();
    
      public int totalNQueens(int n) {
        int[] res = new int[1];
        helper(res,n,0);
        return res[0];
      }
      public void helper(int[] res, int n, int row){
        if(row==n){
            res[0]++;
        }
        else{
            for(int i=0; i<n; i++){
                if(col.contains(i) || diag1.contains(i+row) || diag2.contains(row-i)) continue;
                else{
                    col.add(i);
                    diag1.add(i+row);
                    diag2.add(row-i);
                    helper(res,n,row+1);
                    col.remove(i);
                    diag1.remove(i+row);
                    diag2.remove(row-i);
                }
             }
          }
       }
    }
    

    Similar idea as above but better implementation:

    #Easiest Java Solution (1ms, 98.22%) by yavinci#

    public class Solution {
        int count = 0;
        public int totalNQueens(int n) {
            boolean[] cols = new boolean[n];     // columns   |
            boolean[] d1 = new boolean[2 * n];   // diagonals \
            boolean[] d2 = new boolean[2 * n];   // diagonals /
            backtracking(0, cols, d1, d2, n);
            return count;
        }
    
        public void backtracking(int row, boolean[] cols, boolean[] d1, boolean []d2, int n) {
            if(row == n) count++;
    
            for(int col = 0; col < n; col++) {
                int id1 = col - row + n;
                int id2 = col + row;
                if(cols[col] || d1[id1] || d2[id2]) continue;
    
                cols[col] = true; d1[id1] = true; d2[id2] = true;
                backtracking(row + 1, cols, d1, d2, n);
                cols[col] = false; d1[id1] = false; d2[id2] = false;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.