Java Solution Using Backtrace


  • 0
    D

    private static List<List<String>> resultList=new ArrayList<List<String>>();

    public static  List<List<String>> solveNQueens(int n) {
         resultList=new ArrayList<List<String>>();
        if (n<=0)
            return  null;
        int[][] chess=new int[n][n];
        int[] positions=new int[n];
        solve(0,n,chess,positions);
        return resultList;
    }
    
    public static void solve(int row,int n,int[][]chess,int[] position) {
        for (int col = 0; col < n; col++){
            if (chess[row][col]==0){
                fillInSymbol(chess,row,col,n);
                position[row]=col;
                if(row < n - 1)
                    solve( row+1, n,chess,position);
                else
                    addToList(position,n);
                removeSymbol(chess,row,col,n);
            }
        }
    
    }
    public static void fillInSymbol(int[][] chess,int row,int col,int n){
            chess[row][col]=-1;
            int seq=row+1;
            for (int i = row+1; i <n ; i++) {
                if(chess[i][col]==0)
                  chess[i][col]=seq;
                for (int j = 0; j <n ; j++) {
                    if ((i+j==row+col)&chess[i][j]==0){
                        chess[i][j]=seq;
                    }
                    if ((i-row==j-col)&chess[i][j]==0){
                        chess[i][j]=seq;
                    }
                }
            }
    }
    
    public static void removeSymbol(int[][] chess,int row,int col,int n){
        chess[row][col]=0;
        int seq=row+1;
        for (int i = row+1; i <n ; i++) {
           if(chess[i][col]==seq)
               chess[i][col]=0;
            for (int j = 0; j <n ; j++) {
                if ((i+j==row+col)&chess[i][j]==seq){
                    chess[i][j]=0;
                }
                if ((i-row==j-col)&chess[i][j]==seq){
                    chess[i][j]=0;
                }
            }
        }
    }
    
    
    
    public static void addToList(int[] positions,int n){
        List<String> list = new ArrayList<>();
        for(int row = 0; row < n; row++) {
            char[] charArray = new char[n];
            for (int col = 0; col < n; col++) {
               if (positions[row]==col)
                   charArray[col] = 'Q';
               else
                   charArray[col] = '.';
            }
            list.add(new String(charArray));
        }
        resultList.add(list);
    }

Log in to reply
 

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