n皇后

n 皇后

n皇后

class pair{//用pair存放位置信息!
    public int x;
    public int y;
    public pair(int x, int y){
    this.x = x;
    this.y = y;
    }
}
class Solution {
    public List<List<String>> solveNQueens(int n) {
        //按坐标位置存放所有解决方案
        List<List<pair>> solutions = new ArrayList<>();
        //存放一种解决方案中的所有皇后的位置
        List<pair> solution = new ArrayList<>();
        nQueensBacktrack(solutions, solution, 0, n);
        //把坐标位置转成string
        return transResult(solutions, n);
    }
    void nQueensBacktrack(List<List<pair>> solutions,List<pair> solution, int curRow, int n) {
        if (curRow == n){//递归出口,保存一组解!
        List<pair> newS = new ArrayList<>();
        for(pair p : solution)
        newS.add(p);//拷贝到 newS,不能直接添加引用!
        solutions.add(newS); //添加newS
       }
        //尝试当前行的每一个位置是否可以放置一个皇后
        for (int col = 0; col < n; ++col) {
            if (isValid(solution, curRow, col)) {
            //如果可以，在保存当前位置，继续确定下一行皇后的位置
            //直接调用构造函数，内部构造pair, 或者调用make_pair
            solution.add(new pair(curRow, col));
            nQueensBacktrack(solutions, solution, curRow + 1, n);
            //回溯，删除当前位置，尝试当前行的其它位置
            solution.remove(solution.size() - 1);
            }
        }
    }
    // solution: 一个解决方案，从第一行开始到当前行的上一行每一行已经放置皇后的点
    boolean isValid(List<pair> solution, int row, int col) {
        // 判断当前行尝试的皇后位置是否和前面几行的皇后位置有冲突
        // i.second == col: 第i个皇后与当前这个点在同一列
        // i.first + i.second == row + col: 第i个皇后与当前点在撇上，横坐标+纵坐标值相同
        // i.first - i.second == row - col：第i个皇后与当前点在捺上, 横坐标-纵坐标值相同
        for (pair i : solution)
        if (i.y == col || i.x + i.y == row + col 
        || i.x - i.y == row - col)
        return false;
    return true;
    }
    List<List<String>> transResult(List<List<pair>> solutions, int n) {
        List<String> tmp = new ArrayList<>();
        //把每一种解决方案都转换为string形式，最终结果
        List<List<String>> ret = new ArrayList<>();
        for (List<pair> solution : solutions) {
        //n*n char: 每行有n个元素，把皇后的位置修改为Q
        List<StringBuilder> solutionString = new ArrayList<>();
        for(int i = 0; i < n; ++i){
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < n; ++j)
            sb.append('.');
          solutionString.add(sb);
        }
        for (pair i : solution) {//修改成Q
        solutionString.get(i.x).setCharAt(i.y, 'Q');
        }
        List<String> curRet = new ArrayList<>();
          for(StringBuilder sb : solutionString)
          curRet.add(sb.toString());
        ret.add(curRet);
        }
    return ret;
    }
}

n皇后II

class pair{//保存皇后位置!
    public int i;
    public int j;
    public pair (int i,int j){
        this.i = i;
        this.j = j;
    }
}
class Solution {
    public boolean isnoQueen(int row,int col,ArrayList<pair> tmp){
        //同一列 x.j = col
        //同一斜线 j + i = row + col || i - j = row - col
        for(pair x:tmp){
            if(x.j==col||x.i+x.j==row+col||x.i-x.j==row-col){
                return false;
            }
        }
        return true;
    }
    public int DFS(int curR,int n,ArrayList<pair> tmp){
        int count = 0;
        if(curR==n){//得到一组解!
         count++;
        }
        for(int i = 0;i < n;i++){//得到当前行皇后位置!
            if(isnoQueen(curR,i,tmp)){//判断该位置是否符号题意!
                tmp.add(new pair(curR,i));//将该位置保存!
                //处理下一行
                count += DFS(curR+1,n,tmp);
                //回退
                tmp.remove(tmp.size()-1);
            }
        }
        return count;
    }
    public int totalNQueens(int n) {
        //保存一组解坐标!
        ArrayList<pair> tmp = new ArrayList<>(); 
        return DFS(0,n,tmp);
    }
}