JZTXT

n皇后问题的分析和实现

发布时间 2023-07-08 21:27:38作者: pretty_spider

N皇后问题的分析和实现

1.实现要求
2.代码实现

1.实现要求

在n*n的方格棋中，放置n个皇后，要求每个皇后不同行，不同列，不同对角线
以行为依据，遍历行，判断行对应的列是否符合要求
判定要求：
1.当列被占用，返回false

if(next==clo.get(i)) return false;
//next表示传入的列，col.get(i)表示当前行对应的列，两者相等表示同列，返回false

2.当对角线被占用，返回false

if (Math.abs(i - row) == Math.abs(next - col.get(i))) return false;
//对角线分为两类，左上和左下

获取对应n*n方格棋符合要求的集合，运用遍历，获取方格棋的排列

2.代码实现

运用集合存储数据

package com.prettyspider.Action;

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

public class NQueens {
    public static void main(String[] args) {
        /**
         * n皇后问题
         * 在同一行，同一列，对角线上不能有超过一个的元素
         *
         * 需要随机的添加元素，因此要使用集合，每次产生的结果是对应列所在行的值相等
         */
        //1.获取键盘录入对象
        Scanner scanner = new Scanner(System.in);
        //2.录入数据
        int n = scanner.nextInt();
        //3.调用函数
        List<List<String>> listList = solveNqueen(n);
        System.out.println(listList.size());

    }
    private static List<List<String>> solveNqueen(int n) {
        //3.1创建结果对象
        List<List<String>> result = new ArrayList<>();
        //3.2对输入值进行判断
        if (n <= 0) {
            return result;
        }
        //4调用搜索函数
        search(n, new ArrayList<Integer>(), result);
        return result;
    }
	private static void search(int n, ArrayList<Integer> col, List<List<String>> result) {
        //4.1判断是否搜索完
        if (n == col.size()) {
            //6. 调用绘制结果函数
            result.add(drawChessBoard(col));
            return;
        }
        //4.2遍历获取符合标准的集合
        for (int i = 0; i < n; i++) {  //比较行
            //5.判断是否符合要求
            if (!isValid(col, i)) {
                continue;
            }
            //4.3 不满足要求，向col中添加数据
            col.add(i);
            //4.4 递归调用search，查找下一个不符合要求的位点
            search(n, col, result);
            //4.5 在每次执行4.1后会进行回溯，此时要将添加的数据删除，便于下一个符合中体要求的集合的添加 要从最后添加的数据开始删除数据
            col.remove(col.size() - 1);
        }
    }
    private static boolean isValid(ArrayList<Integer> col, int next) {
        //5.1获取行数
        int row = col.size();
        //排除错误情况
        for (int i = 0; i < row; i++) {
            //5.2判断col存储行所对应的列与输入的next是否相等    比较列
            if (next == col.get(i)) {
                return false;
            }
            if (Math.abs(i - row) == Math.abs(next - col.get(i))) {
                return false;
            }
            //5.3判断当输入的数据小于col对应的列 与i和col相减对应的数据相等，即左上角
            // if (i - row == next - col.get(i)) {
            //     return false;
            // }
            // //5.4 判断当输入的数据大于col对应的列 与i和col相减对应的数据相等，即右上角
            // if (i - row == col.get(i) - next) {
            //     return false;
            // }
        }
        return true;
    }
    private static ArrayList<String> drawChessBoard(ArrayList<Integer> col) {
        //6.1创建绘图集合duixaing
        ArrayList<String> chessBoard = new ArrayList<>();
        //列
        for (int i = 0; i < col.size(); i++) {
            String row = "";
            //行
            for (int j = 0; j < col.size(); j++) {
                if (col.get(j) == i) {
                    row += "q";
                } else {
                    row += ",";
                }
            }
            chessBoard.add(row);
        }
        return chessBoard;
    }
}

如果想要更好的展示每一次的结果，可以使用字符串拼接或使用StringBuilder类，将每次的结果输出