希望我解释的你能明白:
成都网络公司-成都网站建设公司成都创新互联公司十年经验成就非凡,专业从事成都网站制作、网站建设、外贸网站建设,成都网页设计,成都网页制作,软文平台,广告投放等。十年来已成功提供全面的成都网站建设方案,打造行业特色的成都网站建设案例,建站热线:13518219792,我们期待您的来电!
把棋盘看成二维方阵,行从上到下编号0-7(就是i),列从左到右编号0-7(就是j),这样棋盘上每个点都可以表示为(i,j)
从键盘的右上角(0,7)到左下角(7,0)的对角线,以及这条线的平行线,就是反对角线,也就是这个程序里的undiagonal。显然这个反对角线上任意2点(i1,j1)和(i2,j2)都满足i1+j1=i2+j2.因为i+j可能的取值范围是从0到14,所以把这个数组的长度定义为16(事实上15就可以了)
从键盘的左上角(0,0)到右下角(7,7)的对角线以及平行线,就是对角线,就是diagonal。同理,这个对角线及其平行线上任意2点都满足i1-i2=j1-j2.i-j的范围是-7到7,为了避免出现负数,程序里在这里+7,也是一个长度为16的数组(还是15就够了)
程序一开始的时候,i=j=0,所有的安全标识都是true,所以(0,0)这个点会被输出。这时,把diagonal【7】置为false。因为(1,1),(2,2)等等这些点都和(0,0)在一条对角线上(因为0-0+7=1-1+7=2-2+7),所以把这些点的对应的diagonal都置为false,也就是把diagonal【7】置为false
并且把undiagonal【0】也置为false,但是因为undiagonal【0】对应的元素只有(0,0)(因为只有0+0=0),所以这个对这一步没什么影响。
然后一点点递推,回溯,步骤就是这样。希望你看得懂,如果不明白的话给我发消息吧
boolean[] diagonal = new boolean[16]; // 对角线安全标志
boolean[] undiagonal = new boolean[16]; // 反对角线安全标志
用上两个判断是否能放置棋子
在 n 行 n 列的国际象棋棋盘上,最多可布n个皇后。
若两个皇后位于同一行、同一列、同一对角线上,
则称为它们为互相攻击。
n皇后问题是指找到这 n 个皇后的互不攻击的布局。
n 行 n 列的棋盘上,主次对角线各有2n-1条。
利用行号i和列号j计算
主对角线编号k的方法是k = n+i-j-1;
计算次对角线编号k的方法是k = i+j
你主要是算法有些模糊罢了,现在我怕我说的不好将你弄的越来越混乱所以给你个叫形象的若是还不明白,call me
package 百度;
//演示程序:n个皇后问题
import java.io.*;
/*
在 n 行 n 列的国际象棋棋盘上,最多可布n个皇后。
若两个皇后位于同一行、同一列、同一对角线上,
则称为它们为互相攻击。
n皇后问题是指找到这 n 个皇后的互不攻击的布局。
n 行 n 列的棋盘上,主次对角线各有2n-1条。
利用行号i和列号j计算
主对角线编号k的方法是k = n+i-j-1;
计算次对角线编号k的方法是k = i+j
*/
//"n个皇后问题"之类定义
public class cQueen {
int n; //皇后问题的大小
int col[]; //数组,各列上有无皇后(0,1)
int md[]; //数组,各主对角线有无皇后(0,1)
int sd[]; //数组,各次对角线有无皇后(0,1)
int q[]; //数组,第i行上皇后在第几列(0,n-1)
int Q; //已布皇后数,计数
int r; //n皇后问题的解的组数
//构造函数 n皇后问题的初始化
public cQueen(int m) {
n=m;Q=0;r=0;
col=new int[n];
md=new int[2*n-1]; //初始化0
sd=new int[2*n-1];
q=new int[n];
}
//函数:打印棋盘
public void showBoard() {
int i,j;
for(i=0;in;i++) {
for(j=0;jn;j++)
if(q[i]==j) System.out.print("1 ");
else System.out.print("0 ");
System.out.println();
}
r++; //解的组数
System.out.println("---------------");
}
//求解n皇后问题
/*
此函数试图在n*n的棋盘的第i行上放一个皇后,
若找到可以放的位置,就递归调用自身试图在i+1行
放另一个皇后,若第i行是最后一行,则打印棋盘。
*/
public void resolve(int i) {
int j;
// 在第i行给定后检查棋盘上的每一列
for(j=0;jn;j++) {
//如果在第i行的第j列可以布放皇后
if(col[j]==0md[n+i-j-1]==0sd[i+j]==0){
Q++;q[i]=j; //布放皇后,第i行皇后在第几列
// 标记新布皇后的攻击范围
col[j]=md[n+i-j-1]=sd[i+j]=1;
// 如果已经布了n个皇后(得到了一组解),
// 把棋盘(解)打印出来。
if(Q==n) showBoard();
// 否则,递归。在第i行第j列布放皇后的前提下,
//试探下一行(i+1行)在哪一列布皇后?
else if(in-1) resolve(i+1);
else resolve(0); //因为约定起始行可以任选
//移除在第i行的第j列新布的皇后,
//并消除所标记的攻击范围,为回溯作准备。
Q--; q[i]=0;
col[j]=md[n+i-j-1]=sd[i+j]=0;
//试探在第i行的第j+1列新布皇后的方案(新解)
}
} //下一列,j循环
//对于给定的行,列扫描完毕后,从这里回溯。
}
//输出解的个数
public void HowMany() {
System.out.println(n+"皇后问题共有解"+r+"组。");
}
//主方法main()
public static void main(String []args) {
//定义一个8皇后问题(有92组解)
cQueen Q1=new cQueen(8); //大于10,你的微机可能要死机!
//第一个皇后可以在任意一行布放
Q1.resolve(0); //参数在0到n-1之间任选
Q1.HowMany();
}
} //类Queen定义结束
关于看代码的人人都知道的小技巧,最小试探法来输出结果进行比较和分析
public class demo {
public static int N = 0;
public static int ROW = 8;
public int[][] chase = new int[demo.ROW][demo.ROW];
public demo() {
for (int i = 0; i demo.ROW; i++)
for (int j = 0; j demo.ROW; j++)
chase[i][j] = 0;
}
public void copy(int[][] k, int[][] l) {
for (int i = 0; i demo.ROW; i++)
for (int j = 0; j demo.ROW; j++)
l[i][j] = k[i][j];
}
public void changeChase(int[][] chase, int row, int i) {
for (int j = 1; j demo.ROW; j++) {
chase[row][j] = 1;
chase[j][i] = 1;
}
for (int j = 1; j demo.ROW; j++) {
if (row - j = 0 i - j = 0)
chase[row - j][i - j] = 1;
if (row + j = 7 i - j = 0)
chase[row + j][i - j] = 1;
if (row - j = 0 i + j = 7)
chase[row - j][i + j] = 1;
if (row + j = 7 i + j = 7)
chase[row + j][i + j] = 1;
}
chase[row][i] = 2;
}
public void putout(int[][] chase) {
for (int i = 0; i demo.ROW; i++) {
for (int j = 0; j demo.ROW; j++)
System.out.print(chase[i][j] + " ");
System.out.println();
}
}
public void putQueen(int row, int[][] m) {
if (row == 8) {
System.out.println("this is the" + demo.N++ + "个答案:");
putout(m);
} else {
for (int i = 0; i 8; i++) {
if (m[row][i] == 0) {
int[][] l = new int[demo.ROW][demo.ROW];
copy(m, l);
changeChase(l, row, i);
putQueen(row + 1, l);
}
}
}
}
public static void main(String[] Args) {
demo Q = new demo();
Q.putQueen(0, Q.chase);
}
}
[cpp] view plaincopyprint?
//--------------------------------------
//利用函数递归,解决八皇后问题
//
// zssure 2014-03-12
//--------------------------------------
#include stdio.h
#include cmath
int count=0;//全局计数变量
/*--------------------四个皇后----------------------*/
//#define QUEEN_NUM 4
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,
// 0,0,0,0,
// 0,0,0,0,
// 0,0,0,0 };
/*--------------------五个皇后----------------------*/
//#define QUEEN_NUM 5
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,
// 0,0,0,0,0,
// 0,0,0,0,0,
// 0,0,0,0,0,
// 0,0,0,0,0 };
/*--------------------六个皇后----------------------*/
//#define QUEEN_NUM 6
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0
// };
/*--------------------七个皇后----------------------*/
//#define QUEEN_NUM 7
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0
// };
/*--------------------八个皇后----------------------*/
#define QUEEN_NUM 8
int label[QUEEN_NUM][QUEEN_NUM]={0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0};
void FillChessbox(int m,int n,int num)
{
for(int i=0;iQUEEN_NUM;++i)
for(int j=0;jQUEEN_NUM;++j)
if(abs(i-m)==abs(j-n))//对角区域填充
{
if(label[i][j]==0)
label[i][j]=num;
}
int i=0,j=0;
while(iQUEEN_NUM)//行填充
{
if(label[i][n]==0)
label[i][n]=num;
++i;
}
while(jQUEEN_NUM)//列填充
{
if(label[m][j]==0)
label[m][j]=num;
++j;
}
}
void ClearChessBox(int m,int n,int num)
{
for(int i=0;iQUEEN_NUM;++i)
for(int j=0;jQUEEN_NUM;++j)
if(abs(i-m)==abs(j-n) label[i][j]==num)
label[i][j]=0;
int i=0,j=0;
while(iQUEEN_NUM)
{
if(label[i][n]==num)
label[i][n]=0;
++i;
}
while(jQUEEN_NUM)
{
if(label[m][j]==num)
label[m][j]=0;
++j;
}
}
void AllClear()
{
for(int i=0;iQUEEN_NUM;++i)
for(int j=0;jQUEEN_NUM;++j)
label[i][j]=0;
}
void PrintResult()
{
for(int i=0;iQUEEN_NUM;++i)
{
for(int j=0;jQUEEN_NUM;++j)
printf("%d ",label[i][j]);
printf("\n");
}
}
bool EightQueen(int n/*皇后个数*/,int c/*已经放置的皇后个数*/)
{
//static int count=0;
//小于3x3的棋盘是无解的
if(n4)
return false;
for(int i=0;in;++i)
{
if(label[c-1][i]==0)//存在可以放置第c个皇后的位置
{
label[c-1][i]=c+1;
if(c==n)/*已经放置完毕所有的皇后*/
{
++count;
PrintResult();
printf("**************************\n");
ClearChessBox(c-1,i,c+1);
//AllClear();
return true;
}
FillChessbox(c-1,i,c+1);
EightQueen(n,c+1);
ClearChessBox(c-1,i,c+1);
/*-------------------------------------------------------------------------------------------------------------------------
// 现场恢复,无论下一个皇后是否顺利放置,都应该恢复现场。原因是
//
// 如果下一个皇后放置失败,那么自然应该将本次放置的皇后去除,重新放置,所以需要进行现场恢复(即回溯);
// 如果下一个皇后放置成功,意味着本次放置已经满足条件,是一个解,此时需要恢复现场,进行下一次的重新放置,寻找下一个解。
//
//------------------------------------------------------------------------------------------------------------------------*/
//if(!EightQueen(n,c+1))
// ClearChessBox(c-1,i,c+1);
}
}
return false;
}
int main()
{
EightQueen(QUEEN_NUM,1);
printf("%d\n",count);
return 0;
}