Easy to understand Java backtracking


  • 0
    F

    public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<List<String>>();
    boolean[][] used = new boolean[n][n];
    for(int i = 0; i <n;i++){
    for(int j = 0; j< n;j++){
    used[i][j] = false;
    }
    }
    place(0,n,used,res);
    return res;
    }
    // place the queen raw by raw
    public void place(int raw, int n, boolean[][] used, List<List<String>> res) {
    for(int col = 0; col < n; col++){
    if(isvalid(n,raw,col,used)){
    used[raw][col] = true;
    if(raw == n - 1){
    addres(n,used,res);
    } else if(raw < n - 1) {
    place(raw+1,n,used,res);
    }
    used[raw][col] = false;
    }
    }
    }
    // add result
    public void addres(int n,boolean[][] used, List<List<String>> res) {
    List<String> list = new ArrayList<String>();
    for(int i =0;i<n;i++) {
    StringBuilder sb =new StringBuilder();
    for(int j = 0;j<n;j++){
    if(used[i][j]){
    sb.append('Q');
    } else{
    sb.append('.');
    }
    }
    list.add(sb.toString());
    }
    res.add(list);
    }

    public boolean isvalid(int n,int i,int j,boolean[][] used){
        for(int raw = 0; raw < n; raw++){
            if(used[raw][j]){
                return false;
            }
        }
        int raw = i;
        int col =j;
        while(col>=1 && raw >=1){
            if(used[--raw][--col]){
                return false;
            }
        }
        raw = i;
        col =j;
        while(col< n-1 && raw >=1){
            if(used[--raw][++col]){
                return false;
            }
        }
        return true;
    }

Log in to reply
 

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