Accepted Java Solution


  • 94
    A
    /**
     * don't need to actually place the queen,
     * instead, for each row, try to place without violation on
     * col/ diagonal1/ diagnol2.
     * trick: to detect whether 2 positions sit on the same diagnol:
     * if delta(col, row) equals, same diagnol1;
     * if sum(col, row) equals, same diagnal2.
     */
    private final Set<Integer> occupiedCols = new HashSet<Integer>();
    private final Set<Integer> occupiedDiag1s = new HashSet<Integer>();
    private final Set<Integer> occupiedDiag2s = new HashSet<Integer>();
    public int totalNQueens(int n) {
        return totalNQueensHelper(0, 0, n);
    }
    
    private int totalNQueensHelper(int row, int count, int n) {
        for (int col = 0; col < n; col++) {
            if (occupiedCols.contains(col))
                continue;
            int diag1 = row - col;
            if (occupiedDiag1s.contains(diag1))
                continue;
            int diag2 = row + col;
            if (occupiedDiag2s.contains(diag2))
                continue;
            // we can now place a queen here
            if (row == n-1)
                count++;
            else {
                occupiedCols.add(col);
                occupiedDiag1s.add(diag1);
                occupiedDiag2s.add(diag2);
                count = totalNQueensHelper(row+1, count, n);
                // recover
                occupiedCols.remove(col);
                occupiedDiag1s.remove(diag1);
                occupiedDiag2s.remove(diag2);
            }
        }
        
        return count;
    }

  • 0
    S

    Smart solution. The way to classify diagonal cells is impressive! And also votes for your good code.


  • 0
    A
    This post is deleted!

  • 0
    K

    Thanks for solution-sharing. very impressive solution, especially the notation of diagonal1 and diagonal2.


  • 0
    E

    Why does this function stop when ( row > = n)


  • 3
    E

    Thanks for sharing. Here is a similar idea but shorter and slightly different version.

    public class Solution {
        int result = 0;
        public int totalNQueens(int n) {
            boolean[] column = new boolean[n];
            boolean[] dia45 = new boolean[2 * n - 1];
            boolean[] dia135 = new boolean[2 * n - 1];
            helper(0, n, column, dia45, dia135);
            return result;
        }
        private void helper(int row, int n, boolean[] column, boolean[] dia45, boolean[] dia135) {
            if (row == n) {
                result++;
                return;
            }
            for (int col = 0; col < n; col++) {
                if (!column[col] && !dia45[col + row] && !dia135[n - 1- row + col]) {
                    column[col] = dia45[col + row] = dia135[n - 1- row + col] = true;
                    helper(row + 1, n, column, dia45, dia135);
                    column[col] = dia45[col + row] = dia135[n - 1- row + col] = false;
                }
            }
        }
    }

  • 0
    D

    vote for your comment, and the solution is very smart, we needn't place indeed. thanks.
    for a explanation , in the 45 diag lines col - row are always same , and in 135 drag lines col + row are always same , so we can put then in a set.

    Also I have a question, in c++ , I should pass count in the form int &count, so the recursive function can influence the count, how can you pass the count in the form int count, in java, the count should not be stored in stack?


  • 0
    B

    Could you please explain why you use two set for diagonal points? why one store r+c and r-c doesn't work


  • 1
    A

    @brookc : thanks for the advice. 1 set will work for sure. using 2 sets will just make it clearer that we are dealing with 2 diagonals.


  • 1

    Using three boolean arrays
    Proceed row by row

        int res = 0;
        public int totalNQueens(int n) {
          //int[] horizonal = new int[n];
          boolean[] vertical = new boolean[n];
          boolean[] leftfall = new boolean[2 * n - 1];
          boolean[] rightfall = new boolean[2 * n - 1];
          helper(n, vertical, leftfall, rightfall, 0);
          return res;
        }
        
        void helper(int n, boolean[] v, boolean[] l, boolean[] r, int row){
          
          if(row == n){
            res++;
            return;
          }
          
          for(int col = 0; col < n; col++){
             if(v[col] || l[row - col + n - 1] || r[row + col]) continue;
             v[col] = true;
             l[row - col + n - 1] = true;
             r[row + col] = true;
             
             helper(n, v, l, r, row + 1);
             
             v[col] = false;
             l[row - col + n - 1] = false;
             r[row + col] = false;
          }    
        }

  • 0
    T

    @EdickCoding you's idea is very smalier.


  • 0
    X
    This post is deleted!

Log in to reply
 

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