[leetcode] 51 N皇后（路径打印＋DFS+回溯）

分手后的思念是犯贱 2021-10-03 02:34 342阅读 0赞

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

![format_png][]

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4  
输出: \[  
 \[".Q..",  // 解法 1  
  "...Q",  
  "Q...",  
  "..Q."\],

\["..Q.",  // 解法 2  
  "Q...",  
  "...Q",  
  ".Q.."\]  
\]  
解释: 4 皇后问题存在两个不同的解法。

class Pair{
        public int x;
        public int y;
        public Pair(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
    class Solution {
    //深搜过程
        public void dfs(List<List<Pair>> listList,List<Pair> list,int curRow,int n){
            if(curRow == n){
                List<Pair> newP = new ArrayList<>();
                for(Pair p:list){
                    newP.add(p);
                }
                listList.add(newP);
                return;
            }
            for(int i = 0;i<n;i++){
                if(isValid(list,i,curRow)){
                    list.add(new Pair(curRow,i));
                    dfs(listList,list,curRow+1,n);
                    list.remove(list.size()-1);
                }
            }
        }
        //判断是否符合规则
        private boolean isValid(List<Pair> list, int i, int curRow) {
            for(Pair pair:list){
                if(pair.y == i || i+curRow == pair.y+pair.x || curRow-i == pair.x-pair.y)
                    return false;
            }
            return true;
        }
    //打印图形
        public List<List<String>> toStringQueue(List<List<Pair>> solutions,int n){
            List<List<String>> ret = new ArrayList<>();
            List<String> tmp = new ArrayList<>();
            for(List<Pair> solution:solutions){
                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){
                    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;
        }
        public List<List<String>> solveNQueens(int n) {
            List<List<Pair>> lists = new ArrayList<>();
            List<Pair> list = new ArrayList<>();
            dfs(lists,list,0,n);
            return toStringQueue(lists,n);
        }
    }

测试

n = 4

![20200621093843240.png][]

[format_png]: /images/20211003/fb439b5dccc3457682827909f3d50094.png
[20200621093843240.png]: /images/20211003/9f329aecb40c479ab23e401adafd07b5.png