LeetCode---N皇后问题---(困难)

文章目录

题目描述

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

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

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

LeetCode---N皇后问题---(困难)

解题思路—dfs:

遍历每一层存放棋子的位置情况,当一个棋子被放在棋盘上的时候,将这层以下不允许存放棋子的情况保存,当遍历到下一层时,若下一层全部不允许放置棋子则返回,当遍历到最深深度并且放置了棋子时,这种情况则是可以作为N皇后的其中一个解,将这个解保存到List中。
LeetCode---N皇后问题---(困难)
建议结合图片和下面带有main函数的代码一同食用,或者将下面的main函数代码复制到自己电脑进行调试查看(n = 4这个有两组解),主要关注notAllow数组和map数组的变化

通过代码:

我这个时间和空间复杂度可能有点高(毕竟是暴力破解嘛,但个人觉得还是比较好理解的)

class Solution {
     List<List<String>> list = new ArrayList<>();
     List<boolean[][]> status = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
		//init map -> .
        char [][]map = new char[n][n];
        for(int i = 0;i < n;i++){
            Arrays.fill(map[i],'.');
        }
        dfs(new boolean[n][n], map,0);
        return list;
    }
    /**
    * @Params notAllow 标记位,标记该map对应位置是否可以放置棋子
    * @Params map 棋盘,未放置标记为'.',放置后标记为'Q'
    * @Params level 表示层数,遍历到哪个深度位置
    */
    private  void dfs(boolean[][] notAllow, char[][] map, int level) {

        if(level >= notAllow.length){
            //can reach the deepest
            //add the result(map) to list
            List<String> list1 = new ArrayList<>();
            for(int i = 0;i < map.length;i++){
                list1.add(new String(map[i]));
            }
            list.add(list1);
            return;
        }

        for (int i = 0; i < map.length; i++) {

            // if the position is allowed to set a pieces
            // than set a pieces here and set notAllow[level][i] = true;
            // than some place is not allowed to set pieces
            // let this place be true (notAllow)
            if (!notAllow[level][i]) {
                map[level][i] = 'Q';    //set pieces
                notAllow[level][i] = true;
                setProhibit(notAllow,level,i);
                dfs(notAllow,map,level + 1);
                map[level][i] = '.';
                //将notAllow的状态返回
                notAllow = status.get(status.size() - 1);
                status.remove(status.size() - 1);
            }else {
                map[level][i] = '.';
            }

        }

    }

    //设置所有在(x,y)对角线和y下面的部分为true
     void setProhibit(boolean[][] notAllow, int x, int y) {
        int n = notAllow.length;
        boolean [][]notAllow_clone = new boolean[n][n];
        for(int i = 0; i < n; i++){
            notAllow_clone[i] = notAllow[i].clone();
        }
        status.add(notAllow_clone);
        for (int i = x; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(j == y || (Math.abs(i - x) == Math.abs(j - y))){
                    notAllow[i][j] = true;
                }
            }
        }
    }
}

带有main函数的可测试代码:

package LeetCode.December;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Solution51 {
    //N皇后问题 1 <= N <= 9
    static List<List<String>> list = new ArrayList<>();
    static List<boolean[][]> status = new ArrayList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        char [][]map = new char[n][n];
        for(int i = 0;i < n;i++){
            Arrays.fill(map[i],'.');
        }

        dfs(new boolean[n][n], map,0);
        for(List<String> l : list){
            for(String s : l){
                System.out.println(s);
            }
            System.out.println("-----------------");
        }
    }

    private static void dfs(boolean[][] notAllow, char[][] map, int level) {

        if(level >= notAllow.length){
            //can reach the deepest
            //add the result(map) to list
            List<String> list1 = new ArrayList<>();
            for(int i = 0;i < map.length;i++){
                list1.add(new String(map[i]));
            }
            list.add(list1);
            return;
        }

        for (int i = 0; i < map.length; i++) {
            // if the position is allowed to set a pieces
            // than set a pieces here and set notAllow[level][i] = true;
            // than some place is not allowed to set pieces
            // let this place be true (notAllow)
            if (!notAllow[level][i]) {
                map[level][i] = 'Q';    //set pieces
                notAllow[level][i] = true;
                setProhibit(notAllow,level,i);
                dfs(notAllow,map,level + 1);
                map[level][i] = '.';
                //将notAllow的状态返回
                notAllow = status.get(status.size() - 1);
                status.remove(status.size() - 1);
            }
        }

    }

    //设置所有在(x,y)对角线和y下面的部分为true
    static void setProhibit(boolean[][] notAllow, int x, int y) {
        int n = notAllow.length;
        boolean [][]notAllow_clone = new boolean[n][n];
        for(int i = 0; i < n; i++){
            notAllow_clone[i] = notAllow[i].clone();
        }
        status.add(notAllow_clone);
        for (int i = x; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(j == y || (Math.abs(i - x) == Math.abs(j - y))){
                    notAllow[i][j] = true;
                }
            }
        }
    }
}


运行截图

LeetCode---N皇后问题---(困难)

上一篇:PAT 1038 统计同成绩学生 Basic Level


下一篇:8,python 日志和异常