问题描述:在n*n的二维表格,把n个皇后在表格上,要求同一行、同一列或同一斜线上不能有2个以上的皇后。
例如八皇后有92种解决方案,五皇后有10种解决方案。
public class TestQueen {
int n; //皇后的个数
int num = 0; // 记录方案数
int[] queenCol; // 记录n个皇后所占用的列号
boolean[] col; // 列安全标志
boolean[] diagonal; // 对角线安全标志
boolean[] undiagonal; // 反对角线安全标志
public TestQueen(int n) {
this.n = n;
queenCol = new int[n];
col = new boolean[n];
diagonal = new boolean[2 * n - 1];
undiagonal = new boolean[2 * n - 1];
for (int i = 0; i < n; i++)
// 置所有列为安全
col[i] = true;
for (int t = 0; t < (2 * n - 1); t++)
// 置所有对角线为安全
diagonal[t] = undiagonal[t] = true;
}
public void run() {
solve(0);
if (num == 0) {
System.out.println(n + "皇后无解!");
}
}
// 从i行开始,把之后的皇后放好
private void solve(int i) {
for (int j = 0; j < n; j++) {
if (col[j] && diagonal[i - j + n - 1] && undiagonal[i + j]) {
// 表示第i行第j列是安全的可以放皇后(i,j从0开始)
queenCol[i] = j;
col[j] = false; // 修改安全标志
diagonal[i - j + n - 1] = false;
undiagonal[i + j] = false;
if (i < n - 1) // 判断是否放完n个皇后
{
solve(i + 1); // 未放完n个皇后则继续放后面的
} else // 已经放完n个皇后
{
num++;
System.out.println("皇后摆放第" + num + "种方案:");
System.out.print("行分别为");
for (int k = 0; k < n; k++)
System.out.print(k + " ");
System.out.print("\n");
System.out.print("列分别为");
for (int k = 0; k < n; k++)
System.out.print(queenCol[k] + " ");
System.out.print("\n");
}
col[j] = true; // 修改安全标志,回溯
diagonal[i - j + n - 1] = true;
undiagonal[i + j] = true;
}
}
}
public static void main(String[] args) {
TestQueen q = new TestQueen(5);
q.run();
}
}
输出结果:
皇后摆放第1种方案:
行分别为0 1 2 3 4
列分别为0 2 4 1 3
皇后摆放第2种方案:
行分别为0 1 2 3 4
列分别为0 3 1 4 2
皇后摆放第3种方案:
行分别为0 1 2 3 4
列分别为1 3 0 2 4
皇后摆放第4种方案:
行分别为0 1 2 3 4
列分别为1 4 2 0 3
皇后摆放第5种方案:
行分别为0 1 2 3 4
列分别为2 0 3 1 4
皇后摆放第6种方案:
行分别为0 1 2 3 4
列分别为2 4 1 3 0
皇后摆放第7种方案:
行分别为0 1 2 3 4
列分别为3 0 2 4 1
皇后摆放第8种方案:
行分别为0 1 2 3 4
列分别为3 1 4 2 0
皇后摆放第9种方案:
行分别为0 1 2 3 4
列分别为4 1 3 0 2
皇后摆放第10种方案:
行分别为0 1 2 3 4
列分别为4 2 0 3 1
分享到:
相关推荐
N皇后问题(n-queen problem)是一个经典的组合优化问题,也是一个使用回溯法(backtracking)的典型例子。回溯法是一种系统地搜索问题解的方法。 此文档包含算法分析、代码实现、演示程序、演示界面。
Java编写的N皇后问题,可以任意设置皇后的数量,可以运行
N皇后(java代码).docx
这是一个用Java实现的关于N皇后问题的算法 其中包括回溯和迭代两种算法
算法作业,2011年4月份写的。希望帮助一些需要的人,代码就不给了,需要的使用反编译工具看吧
遗传算法实现N皇后-java代码
一段关于皇后问题的代码 这是我能写出来的最简单的了! 希望大家能够喜欢!
编译、运行均没问题,只要输入N的值,便可得到符合条件的所有坐标,采用矩阵算法,通过改变布尔值,利用堆栈技术,算法很容易理解。
N皇后问题,带界面的,java版。
正因为这门课程难,所以除了相关方面的书籍,网络资源少的可怜,尤其是java代码简直如大海捞针。因此,做完这次课程设计,我决定把这些资源传到广大学生钟爱的CSDN上供大家分享学习,希望能真正帮到大家!
八皇后 java源码,可以任意改变变量来实现n皇后问题
java代码-N皇后问题-----
N皇后随机算法
此代码主要解决的是N皇后问题,用JAVA编写的,相信对大家会有用
本资源包含了八皇后算法分析文档、流程图和Java源代码,解决方案具有很强的通用性,可以根据需要实现N个皇后的摆放,eclipse环境中编译通过,运行正确。
Java和C语言实现各种经典算法(含代码图例) 老掉牙 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) 骑士走棋盘 八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包...
1)可以用C++或者Java撰写,不需要写界面; 2)要求在通用开发平台上可以调试并无误运行; 3)代码长度没有要求; 4)除了所需的头文件、库文件之外,要求代码放在一个文件中; 5)代码需要给出必要的注释,书写风格...
N个N个皇后问题 N比N的皇后问题最古老的基于国际象棋的问题之一是在棋盘上放置8个皇后,而皇后不会互相攻击。 (如果您不熟悉国际象棋,则女王可以攻击同一行上的任何正方形,同一列上的任何正方形或同一对角线上的...