本文共 1826 字，大约阅读时间需要 6 分钟。

1.问题描述

八皇后问题，一个古老而著名的问题，是回溯算法的典型案例。该问题由国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有 76 种方案。1854 年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，后来有人用图论的方法解出 92 种结果。计算机发明后，有多种计算机语言可以编程解决此问题。

2.思路分析

1. 第一个皇后先放第一行第一列
2. 第二个皇后放在第二行第一-列、然后判断是否OK，如果不0K， 继续放在第二列、第三列、依次把所有列都放完，找到一-个合适
3. 继续第三个皇后，还是第一列、第二列…直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
4. 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一-列的所有正确解，全部得到.
5. 然后回头继续第一-个皇后放第二列，后面继续循环执行1,2,3,4的步骤

说明 :理论上应该创建-一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8]={0,4,7,5,2, 6,1,3} //对应arr下标表示第几行，即第几个皇后，arr[i]=val, val表示第i+1个皇后，放在第i+1行的牛第val+1列

3.代码实现

首先将变量进行定义

// 定义max 表示有多少个皇后	int max = 8;	// 定义数组,放置位置	int[] arr = new int[max];	// 用于统计一共有多少种方法	static int count = 0;	// 统计冲突的次数,用于测试性能	static int Ccount = 0;

方法定义：将所有摆放后的一维数组进行输出，以及使用count++统计输出的次数，也就是八皇后问题一共有多少种摆法。

private void print() {
   		count++;		for (int i = 0; i < arr.length; i++) {
   			System.out.print(arr[i] + " ");		}		System.out.println(" ");	}

方法定义：判断放置皇后的位置是否有冲突。Ccount++; 同理，就是一共回溯的次数，间接的反映代码的性能。

private boolean conflict(int n) {
    // n 表示放置第n个皇后		Ccount++;		for (int i = 0; i < n; i++) {
   			if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {
   				return false;			}		}		return true;	}

方法定义，放置皇后，对位置判断是否冲突之后，冲突就将皇后的位置在这一行上进行后移，不冲突即再一次调用这个方法进行递归。

private void cheek(int n) {
   		if (n == max) {
    // 这个时候8个皇后已经放好了			print();			return;		}		// 依次放入皇后,判断是否有冲突		for (int i = 0; i < max; i++) {
   			// 先把当前皇后放在第1列			arr[n] = i;			// 在判断是否冲突			if (conflict(n)) {
   				// 不冲突,接着放n+1个皇后,开始递归				cheek(n + 1);			}		}		// 冲突之后,进行后移位置 i++	}

定义测试：调用方法，并且对统计的变量进行输出，效果图如下所示：

Queue8 q = new Queue8();	q.cheek(0);	System.out.println("一共有多少种摆法：" + count);	System.out.println("一共冲突了多少次：" + Ccount);

转载地址：http://qemzi.baihongyu.com/