zrlong 的个人博客

题目描述

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

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

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

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        //记录每行皇后摆放位置
        int[] arr = new int[n];
        queen(n,0,arr,ans);
        return ans;
    }
    //判断是否冲突
    public static boolean judge(int m,int[] arr){
        for(int i=0;i<m;i++){
            //判断是否在同一列或者在斜线上
            if(arr[i] == arr[m] || Math.abs(m-i) == Math.abs(arr[m] - arr[i])){
                return false;
            }
        }
        return true;
    }
    //递归回溯
    public static void queen(int max,int m,int[] arr,List<List<String>> ans){
        if(m == max){
            String str = "";
            List<String> list = new ArrayList<>();
            for(int i=0;i<max;i++){
                str = "";
                for(int j=0;j<max;j++){
                    if(j == arr[i]){
                        str+="Q";
                    }else{
                        str+=".";
                    }
                }
                list.add(str);
            }
            ans.add(list);
            return;
        }
        for(int i=0;i<max;i++){
            //八该皇后放到这一行的第一列
            arr[m] = i; 
            //判断是否冲突
            if(judge(m,arr)){
                //不冲突继续下一个皇后
                queen(max,m+1,arr,ans);
            }
        }
    }
}