首页 > 代码库 > 八皇后问题之我的理解
八皇后问题之我的理解
问题概述
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n1×n1，而皇后个数也变成n2。而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解。
八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。
艾兹格·迪杰斯特拉在1972年用这个问题为例来说明他所谓结构性编程的能力。
八皇后问题出现在1990年代初期的著名电子游戏第七访客中
从题目可以得知，在8行8列的棋盘上，每行没列都I必须有一个皇后，此题的核心就是判断判断行列或斜线上是否已经有皇后
/**
* Created by wolf on 2016/3/16.
*/
public class test1 {
/**
* 一共有多少个皇后（此时设置为8皇后在8X8棋盘，可以修改此值来设置N皇后问题）
*/
int max = 8;
/**
* 该数组保存结果，第一个皇后摆在array[0]列，第二个摆在array[1]列
*/
int[] array = new int[max];
public static void main(String[] args) {
new test1().check(0);
System.out.println(count);
}
/**
* n代表当前是第几个皇后
* @param n
* 皇后n在array[n]列
*/
static int count=0;
private void check(int n) {
//终止条件是最后一行已经摆完，由于每摆一步都会校验是否有冲突，所以只要最后一行摆完，说明已经得到了一个正确解
if (n == max) {
count++;
return;
}
//从第一列开始放值，然后判断是否和本行本列本斜线有冲突，如果OK，就进入下一行的逻辑
for (int i = 0; i < max; i++) {
array[n] = i;
if (judge(n)) {
check(n + 1);
}
}
}
private boolean judge(int n) {
for (int i = 0; i < n; i++) {
//此题的关键：用行差和列差的绝对值去判断斜线上是否已经出现过皇后
if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
return false;
}
}
return true;
}
}
八皇后问题之我的理解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。