如果理解递归算法,八皇后问题还是很简单的。现总结递归基本模型:
function (n){
1、递归出口
2、递归体
}
GO down to business!
八皇后问题还有个小小的难点就是皇后冲突问题的解决
//判断皇后(n,j)与(k,a[k])是否冲突
//其中(n,j)为当前放下的皇后,(k,a[k])为以前放下的皇后
for (int k=1;k<n;k++){
if (a[k]==j){
flag = false;//竖线攻击
break;
}else if (k+a[k] == n+j){
flag = false;//正对角线相加相等,攻击
break;
}else if (k-a[k] == n-j) {
flag = false;//反对角线相减相等,攻击
break;
}
}
下面是java源码,直接运行即出结果:
package mana;
public class Digui {
private int a[] = new int[9]; //正对角线相加相等,反对角线相减相等
private int sum = 0;
public static void main(String arg[]){
Digui digui = new Digui();
digui.eightQueen();
}
public void setQueen(int n){
//输出结果
if (n==9){
sum++;
System.out.print(sum+": ");
for (int k=1;k<=8;k++){System.out.print(a[k]+",");}
System.out.println();
}
//否则
for (int j=1;j<=8;j++) {
boolean flag = true;
//判断皇后(n,j)与(k,a[k])是否冲突
for (int k=1;k<n;k++){
if (a[k]==j){
flag = false;//竖线攻击
break;
}else if (k+a[k] == n+j){
flag = false;//正对角线相加相等,攻击
break;
}else if (k-a[k] == n-j) {
flag = false;//反对角线相减相等,攻击
break;
}
}
//如果不冲突
if (flag){
a[n] = j;
setQueen(n+1);
}
//否则继续;
}
}
public void eightQueen(){
sum=0;
for (int i=1;i<=8;i++){ a[i]=-100; }
setQueen(1);
}
}
分享到:
相关推荐
两者的内核差不多,主要是皇后类成员的设计以及回溯算法的实现。可视化模式可以将结果直观地显示在Form上,包括解的个数,棋盘和皇后的摆放,上一个解的显示,下一个解的显示等。注意采用可视化模式观看运行结果的...
八皇后问题 递归算法 可以输入皇后的值 输出排列的结果
这道题可以用递归循环来做,分别一一测试每一种摆法,直到得出正确的答案。主要解决以下几个问题: 1、冲突。包括行、列、两条对角线: (1)列:规定每一列放一个皇后,不会造成列上的冲突; (2)行:当第I行被...
用递归解决八皇后 蛮简单的 用递归解决八皇后 蛮简单的用递归解决八皇后 蛮简单的用递归解决八皇后 蛮简单的用递归解决八皇后 蛮简单的用递归解决八皇后 蛮简单的
八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。这里提供一个C++语言的递归法的实现,代码已在VS2008下编译通过。相关博文地址: http://blog.csdn.net/jocodeoe/article/details/7067955
八皇后问题 递归(回溯法求解),很简洁,欢迎下载交流。
八皇后问题:在8*8的国际象棋盘上放置8个皇后,使其不能互相攻击(即任意两个皇后不能在同一行、同一列、同一斜线上)。试用递归法求出所有符合条件的布局。
int Correct (int row, int col) //判断第row行的皇后是否会和第0行到第row-1行的皇后冲突 { for (int i = 0; i ; i++) { if (col == A[i] || row + col == i + A[i] || (row - i == col - A[i]))//判断两皇后是否...
对经典算法八皇后问题的说明,以及代码示例,代码中有详尽的注释,有助于读者充分理解其递归调用的逻辑!
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或...
c语言实现的八皇后,采用的是递归回溯法 int main() { short int queen[MAX+1][MAX+1]; memset(queen,0,sizeof(queen)); eightqueen(1,queen); printf("共有%d种棋盘的摆放方式\n",count); return 0; }
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放... 该程序是用C语言编写的用于解决经典的八皇后问题的程序,本程序采用的是回溯法。
C++课程设计八皇后,递归法、回溯算法求八皇后
此文档包含八皇后问题解法的两种方式---递归法和回溯法
通过对题意的分析与计算,八皇后问题总体来说可以有三种求解方式,分别为穷举法、递归法、回溯法,而本题中因为皇后的数量较多,因此本课程设计中只采用了递归法和回溯法来解决八皇后问题。递归是一种比较简单且比较...
八皇后问题,增加了如何判断重复的解,回溯法非递归法,新手之作
递 归 算 法 举 例——八皇后问题详解,和大家分享~
八皇后问题:在一个8X8的国际象棋棋盘中,每行放1个皇后,共放8个皇后,且互不攻击。 研究共有多少种不同的放法,称为八皇后问题
简洁高效的八皇后问题C++实现,其中主要运用递归的方法。八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其...
用c++中的回溯法解决八皇后问题,其中有递归等编程方法