30 lines concise java solution, only needs one array to save column number


  • 0
    F

    The trick is to use an integer array to record column number. Then A[i] = 1 means there is a queen on row i, col 1. Note that the col number starts from 1 instead of 0.

    public class Solution {
        public int totalNQueens(int n) {
            int[] res = {0};
            int[] A = new int[n];
            
            helper(n, 0, A, res);
            return (res[0]);
        }
        
        boolean valid(int r, int c, int[] A) {
            for (int i = 0; i < r; i++) {
                if (A[i] == c || Math.abs(A[i] - c) == r - i) {
                    return (false);
                }
            }
            
            return (true);
        }
        
        void helper(int n, int cur, int[] A, int[] res) {
            if (n == cur) {
                res[0]++;
            }
            
            for (int i = 1; i <= n; i++) {
                if (valid(cur, i, A)) {
                    A[cur] = i;
                    helper(n, cur + 1, A, res);
                    A[cur] = 0;
                }
            }
        }
    }
    

Log in to reply
 

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