8皇后问题描述：是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。
此处以8皇后进行测试。
/**
* N皇后问题（回溯法）
*
* @author yundixiaoduo(4080509)
* @version 2.00
*/
public class NQueen {
int standard = 8;
// 棋盘格局保存变量，采用一维数组来保存。
// 其中索引为行号，值为列号。
// 均从0开始排。
private int[] broad = new int[standard];
NQueen(int standard) {
this.standard = standard;
for (int i = 0; i < standard; i++) {
broad[i] = -1;
}
}
// 记录输出棋盘格局的个数，方便打印函数调用。
private int num = 0;
/**
* 回溯自测试函数
*
* @param row
* 当前递归所在行，从0开始。
*/
public void test(int row) {
// 当row溢出（row的范围为[0,standard-1]），表明找出一个解。
// 进行打印，并返回上一行（回溯）。
if (row == standard) {
print();
return;
}
// 遍历一行，先将皇后放到该行某一列上，然后进行检验。
// 若通过检验，则进入下一行（递归）。
// 若未通过，则返回到上一行（回溯）。
for (int i = 0; i < standard; i++) {
broad[row] = i;
if (check(row)) {
test(row + 1);
}
}
}
/**
* 打印函数 将每种可能的棋盘布局打印输出。 其中0代表空，1代表皇后。
*/
public void print() {
num++;
System.out.println("-------第" + num + " 种------");
for (int column : broad) {
for (int i = 0; i < standard; i++) {
if (column == i) {
System.out.print(1 + " ");
} else {
System.out.print(0 + " ");
}
}
System.out.println();
}
System.out.println();
}
/**
* 检验函数 检验是否符合N皇后的规则。
*
* @param row
* 所在行。
* @return boolean
* 若符合规则则返回true，若不符合则返回false。
*
*/
public boolean check(int row) {
// 遍历所有已下子，通过与已下子对比，查看该新位置是否符合规则。
// 因为是一行一行的下子，且每行只下一子，故不用考虑是否会有行冲突。
// 此处 i 可以当做已下子所在行来理解。
for (int i = 0; i < row; i++) {
// 检验是否有列冲突。
// 其中broad[i]表示遍历已下皇后中的某行皇后所在列。
// broad[row]表示刚刚下的皇后所在列。
if (broad[i] == broad[row])
return false;
// 检验是否有斜线冲突。
// 假设将皇后放入坐标系中，则处于同一斜线上的皇后所构成的直线斜率为1，
// 即横坐标差的绝对值与纵坐标差的绝对值相等。
if (Math.abs(broad[row] - broad[i]) == row - i)
return false;
}
return true;
}
public static void main(String[] args) {
NQueen queen = new NQueen(8);
queen.test(0);
}
}
运行结果：
没有评论:
发表评论