首页 > 试题广场 >

11-4 n皇后问题:要求在一个nXn的棋盘上放置n个皇后

[问答题]
11-4  n皇后问题:要求在一个nXn的棋盘上放置n个皇后,要求放置的n个皇后不会互相吃掉;皇后棋子可以吃掉任何它所在的那一行、那一列，以及那两条对角线上的任何棋子。
添加回答
温暖的秋裤头像 温暖的秋裤
class Solution {
    LinkedList<List<String>> res=new LinkedList();
    public List<List<String>> solveNQueens(int n) {
        if(n==0)return res;
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<n;i++){
            sb.append(".");
        }
        String[] str=new String[n];
        for(int i=0;i<n;i++){
            str[i]=sb.toString();
        }
        backTrack(str,0);
        return res;
    }
    //在第i行放值，回溯
    public void backTrack(String[] str,int i){
        int n=str.length;
        if(i==n){
            ArrayList<String> list=new ArrayList();
            for(String s:str){
                list.add(s);
            }
            res.add(list);
            return;
        }
        for(int j=0;j<n;j++){
            if(valid(str,i,j)){
                //改变
                String old=str[i];
                StringBuilder sb=new StringBuilder(old);
                sb.setCharAt(j,'Q');
                str[i]=sb.toString();
                backTrack(str,i+1);
                str[i]=old;
            }
        }
    }

    public boolean valid(String[] str,int i,int j){
        int len=str.length;
        //检查列
        for(int a=0;a<i;a++){
            if(str[a].charAt(j)=='Q')return false;
        }
        //检查左上
        for(int dis=1;dis<=i&&j>=dis;dis++){
            if(str[i-dis].charAt(j-dis)=='Q')return false;
        }
        //检查右上
        for(int dis=1;dis<=i&&j+dis<len;dis++){
            if(str[i-dis].charAt(j+dis)=='Q')return false;
        }

        return true;

    }
}
发表于 2021-03-10 01:58:21 回复(0)
提交观点

问题信息

上传者：小小
难度：
1条回答 1591浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号