Clean DFS solution


  • 0
    C

    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];
            result=0;
            dfs(board,0);
            return result;
        }
        public void dfs(int[] board,int index)
        {
            if(index>=board.length-1) result++;
            for(int i=1;i<=board.length-1;i++)
            {
                board[index]=i;
                if(isValid(board)) dfs(board,index+1);
                board[index]=0;
            }
        }
        
        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.