导语：算法系列之-八皇后问题（排列方式实现）

题目思路和来源 剑指offer

01 题目描述

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

02 解题

首先说明，如下图皇后1和皇后3属于一条斜线上，皇后2皇后4皇后5皇后5也在同一条斜线上。所以需要正确理解斜线，是只要用一条斜线可以串到都算同一斜线。

不是像皇后4皇后5相邻斜线才是同一斜线。

在之前的文章里面写了排列算法。字符串排列八皇后也可以用排列算法来解决int[] result = new int[8]，

下标代表行，对数组某个未知的数的赋值代表列，如 result[0]=1 .说明第一个皇后在第0行的第1列里面。

初始化赋值 result= {0,1,2,3,4,5,6,7}

由于数组下标是0-8，排列算法是数值之间的交换，不存在重复的情况。所以八皇后不会坐落在同一行同一列中。

因此我们只需要判断一下各个皇后是否在同一个对斜线上。

Math.abs(j - i) == Math.abs(result[j] - result[i]) 即在同一个斜线上。横竖组成了等边三角形

然后判断从第一个皇后i=0 到递归的第row个皇后，他们是否在同一个斜线上。

for (int i = 0; i < row; i++) {//检查 for (int j = i + 1; j <= row; j ++) { if (Math.abs(j - i) == Math.abs(result[j] - result[i])) { return false; } } }

03 代码总结

1.用排列的想法实现八皇后。

2.检查是否在同一个斜线上。

public static int queenResolvedCount = 0;public static boolean checkNotFight(int[] result, int row) { for (int i = 0; i < row; i++) {//检查 for (int j = i + 1; j <= row; j ++) { if (Math.abs(j - i) == Math.abs(result[j] - result[i])) { return false; } } } return true;}public static void eightQueenProblem(int[] result, int startIndex) { if (startIndex == result.length) { System.out.println(Arrays.toString(result)); queenResolvedCount++; } for (int i = startIndex; i < result.length; i++) { int tmp = result[startIndex]; result[startIndex] = result[i]; result[i] = tmp; if (checkNotFight(result, startIndex)) {// 判断到目前为止是否在同一个斜线上 eightQueenProblem(result, startIndex + 1); } tmp = result[startIndex]; result[startIndex] = result[i]; result[i] = tmp; }}//8皇后调用的地方public static void eightQueenProblem() { int[] result = new int[8]; for (int i = 0; i < 8; i ++) { result[i] = i; } eightQueenProblem(result, 0);}// 调用输出public static void main(String[] args) { eightQueenProblem(); System.out.println(queenResolvedCount);}

本文内容由小涵整理编辑！