Clean DFS solution

  • 0

    use a one-dimensional array to save the column position for each row.

    public class Solution {
        int result;
        public int totalNQueens(int n) {
            int[] board=new int[n+1];
            return result;
        public void dfs(int[] board,int index)
            if(index>=board.length-1) result++;
            for(int i=1;i<=board.length-1;i++)
                if(isValid(board)) dfs(board,index+1);
        public boolean isValid(int[] board)
            boolean[] map=new boolean[board.length];
            Set<Integer> plusSet=new HashSet<Integer>();
            Set<Integer> minusSet=new HashSet<Integer>();
            for(int i=0;i<board.length;i++)
                if(board[i]==0) continue;
                if(map[board[i]]) return false;
                else map[board[i]]=true;
                int plus=i+(board[i]-1);
                int minus=i-(board[i]-1);
                if(!plusSet.contains(plus)) plusSet.add(plus);
                else return false;
                if(!minusSet.contains(minus)) minusSet.add(minus);
                else return false;            
            return true;

Log in to reply

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