1. 云栖社区>
  2. >
  3. 正文

数据结构经典算法学习之八皇后01

作者:用户 来源:互联网 时间:2018-09-15 17:34:41

算法数据结构八皇后

数据结构经典算法学习之八皇后01 - 摘要: 本文讲的是数据结构经典算法学习之八皇后01, 八皇后 故事背景: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜

八皇后


故事背景: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。而且仅当 n = 1 或 n ≥ 4 时问题有解。 八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究,其中包括高斯和康托,并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年,S.冈德尔提出了一个通过行列式来求解的方法,这个方法后来又被J.W.L.格莱舍加以改进。 艾兹格·迪杰斯特拉在1972年用这个问题为例来说明他所谓结构性编程的能力。 八皇后问题出现在1990年代初期的著名电子游戏第七访客中。


问题思考:

这里首先采用的是一种效率并不高的迭代递归判定的方法。如果一个皇后的一行,一竖,俩对角线都没有其他皇后,则标记该位置为1,该皇后充当障碍物。迭代每一个棋盘的位置(这里很明显效率低下,因为一旦确定了一个皇后之后,那么他的行,竖,对角线其实都不需要再判定了)


代码实现(可能代码写的不够完整,没时间,但核心实现了):

package wj.arithmatic;

public class EQueen {

	int now = 0;
	public int row;
	public int col;
	public int equeen[];

	// 八皇后图样初始化
	public void init() {
		for (int i = 1; i < 9; i++) {
			for (int j = 1; j < 9; j++) {
				if (((i % 2 != 0) && (j % 2 == 0)) || ((i % 2 == 0) && (j % 2 != 0))) {
					System.out.print(" ■");
				} else {
					System.out.print(" □");
				}
			}
			System.out.println();
		}
	}

	// 判定是否被攻击
	public boolean isKilled(int row, int col, int[] equeen) {
		if (equeen.length != 0) {
			// 其实equeen中只存行号,因为每一个正确位置的皇后必然是在紧邻不同列,顾列号可以用i来代替
			for (int i = 0; i < equeen.length; i++) {
				// 是否同行
				if (row == equeen[i]) {
					return false;
				}
				// 是否同列
				if (col == i) {
					return false;
				}
				// 是否对角线
				if ((row - col) == (equeen[i] - col) || (row + col) == (equeen[i] + col)) {
					return false;
				}
			}
			return true;
		}
		return true;
	}

	public boolean equeen(int row, int col, int[] equeen) {
		boolean b = this.isKilled(row, col, equeen);
		if (b) {
			equeen[col] = 1;
			return true;
		}
		return false;
	}

	public void start() {
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				boolean b = this.equeen(row, col, equeen);
				if (b) {
					equeen(i, j, equeen);
				}
			}
		}
	}

	public static void main(String args[]) {
		new EQueen().init();
	}
}



以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索算法 , 数据结构 八皇后 ,以便于您获取更多的相关知识。

弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率

40+云计算产品,6个月免费体验

现在注册,免费体验40+云产品,及域名优惠!

云服务器9.9元/月,大学必备