八皇后有多少种摆法

八皇后有多少种摆法

文章目录

• 八皇后有多少种摆法
• 八皇后问题描述
• 前言
• 代码
• 返回结果

---

八皇后问题描述

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行同一列或同一斜线上，问有多少种摆法？

前言

Point类是jdk自带 ，在java.awt包下。这里用Point,是为了记录皇后的位置.point.x，point.y表示二维数组 int [x][y]的两索引。

代码

可以直接复制运行。
代码实现，保存所有的摆法，以及遍历展示这些摆法

/**
 * 在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行
 * 、同一列或同一斜线上，问有多少种摆法。
 */
public class EightQueens {
    static int[][] chessBoard = new int[8][8];//棋盘
    static ArrayList<int[][]> boards = new ArrayList<>();//以二维数组存放所有摆法

    public static void main(String[] args) {
        putQueen(1);
        System.out.println("八皇后共有摆法："+boards.size()+"种");//92
		//展示所有的摆法
        for (int[][] board : boards) {
            showChessBoard(board);
            System.out.println("=============================================");
        }
    }

    //核心：放置皇后的动作，递归调用
    public static void putQueen(int num) {//num为放置第几个皇后，也表示”“第”几行，注意索引表示为num-1行
        for (int i = 0; i < chessBoard.length; i++) {//遍历第num行的列。
            if (!isAttack(new Point(num-1,i))){//不会互相攻击，可以摆放
                chessBoard[num-1][i]=1;//摆放
                if (num<8){//不是第八个皇后，继续往下一行摆
                    putQueen(num+1);//递归摆法下一个
                }else {//是第8个此时已经摆完
                    int[][] newChess = copyArr(chessBoard);//复制出棋盘保留
                    boards.add(newChess);//复制出的棋盘放入集合保持
                }
            }
            chessBoard[num-1][i]=0;//结果已经保存，棋盘该位置清零，从而不影响下一次的递归。
        }
    }

    //是否与其它皇后可互相攻击
    public static boolean isAttack(Point p) {
        ArrayList<Point> queens = getQueens();
        if (queens.size() == 0) {//当前棋盘没有皇后，可以放
            return false;
        }
        for (Point queen : queens) {
            if (isAttack(p, queen)) {//如果有任何一个可以碰撞直接返回fale,此地不能放
                return true;
            }
        }
        return false;
    }

    //两皇后是否可互相攻击
    public static boolean isAttack(Point p1, Point p2) {
        //判断两皇后是否在同一行，同一列同一斜线上
        if (p1.x == p2.x || p1.y == p2.y || (Math.abs(p1.x - p2.x) == Math.abs(p1.y-p2.y))) {
            return true;
        }
        return false;
    }

    //获取当前棋盘上的所有皇后
    public static ArrayList<Point> getQueens() {
        ArrayList<Point> ps = new ArrayList<>();
        for (int i = 0; i < chessBoard.length; i++) {
            for (int j = 0; j < chessBoard[i].length; j++) {
                if (chessBoard[i][j] == 1) {
                    ps.add(new Point(i, j));
                }
            }
        }
        return ps;
    }

    //展示棋盘
    public static void showChessBoard(int[][] chessBoard) {
        for (int i = 0; i < chessBoard.length; i++) {
            for (int j = 0; j < chessBoard[i].length; j++) {
                System.out.print(chessBoard[i][j] + "\t");
            }
            System.out.println();
        }
    }

    //复制二维数组
    public static int[][] copyArr(int[][] arr) {
        int[][] newArr = new int[arr.length][];
        for (int i = 0; i < arr.length; i++) {
            newArr[i] = new int[arr[i].length];
            for (int j = 0; j < arr[i].length; j++) {
                newArr[i][j] = arr[i][j];
            }
        }
        return newArr;
    }
}

返回结果