Share my iterative way of BFS


  • 0
    B
    public class Solution {
    class Position{
        public int row ;
        public int col;
        public Position(int r, int c){
            row = r;
            col = c;
        }
    }
      public List<List<String>> solveNQueens(int n)  {
        //bfs
        List<List<String>> res = new ArrayList<>();
        LinkedList<ArrayList<Position>> q = new LinkedList<>();
        for(int i = 0; i < n; i++){ ArrayList<Position> path = new ArrayList<Position>(); path.add(new Position(0,i)); q.add(path);}
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                ArrayList<Position> path = q.remove();
                if(path.size() == n)    {
                    List<String> result = new ArrayList<>();
                    for(Position p: path){
                        StringBuilder row = new StringBuilder();
                        for(int j = 0; j < n; j++){
                            if(j == p.col)  row.append("Q");
                            else    row.append(".");
                        }
                        result.add(row.toString());
                    }
                    res.add(result);
                    continue;
                }
                ArrayList<Position> successors = getSuccessors(path,n);
                for(Position successor : successors){
                    path.add(successor);
                    q.add((ArrayList<Position>)path.clone());
                    path.remove(path.size()-1);
                }
            }
        }
        return res;
    }
    public ArrayList<Position>  getSuccessors(ArrayList<Position> path,int n){
        ArrayList<Position>  successors = new ArrayList<Position> ();
        int row = path.size();
        ArrayList<Integer> set = new ArrayList<>();
        ArrayList<Integer> removed = new ArrayList<>();
        for(int i = 0; i < n ;i++){
            set.add(i);
        }
        for(Position pre : path)
            set.remove((Integer)pre.col);
        for(Position pre : path){
            for(int c : set){
                if(Math.abs(pre.row - row)==Math.abs(pre.col - c))
                    removed.add(c);
            }
        }
        for( int c : set)  if(!removed.contains(c)) successors.add(new Position(row,c));
        return successors;
    }
    

    }


Log in to reply
 

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