N皇后问题java

❶ java八皇后问题

希望我解释的你能明白：
把棋盘看成二维方阵，行从上到下编号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），所以这个对这一步没什么影响。
然后一点点递推，回溯，步骤就是这样。希望你看得懂，如果不明白的话给我发消息吧

❷ JAVA中八皇后问题算法和流程图。要求用回溯法，求大神解答，在线等如果有代码就完美了

[cpp] view plainprint?
//--------------------------------------
//利用函数递归，解决八皇后问题
//
// 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;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
if(abs(i-m)==abs(j-n))//对角区域填充
{
if(label[i][j]==0)
label[i][j]=num;
}

int i=0,j=0;
while(i<QUEEN_NUM)//行填充
{
if(label[i][n]==0)
label[i][n]=num;
++i;
}
while(j<QUEEN_NUM)//列填充
{
if(label[m][j]==0)
label[m][j]=num;
++j;
}

}
void ClearChessBox(int m,int n,int num)
{
for(int i=0;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
if(abs(i-m)==abs(j-n) && label[i][j]==num)
label[i][j]=0;
int i=0,j=0;
while(i<QUEEN_NUM)
{
if(label[i][n]==num)
label[i][n]=0;
++i;
}
while(j<QUEEN_NUM)
{
if(label[m][j]==num)
label[m][j]=0;
++j;
}
}
void AllClear()
{
for(int i=0;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
label[i][j]=0;

}
void PrintResult()
{
for(int i=0;i<QUEEN_NUM;++i)
{
for(int j=0;j<QUEEN_NUM;++j)
printf("%d ",label[i][j]);
printf("\n");

}
}
bool EightQueen(int n/*皇后个数*/,int c/*已经放置的皇后个数*/)
{
//static int count=0;
//小于3x3的棋盘是无解的
if(n<4)
return false;

for(int i=0;i<n;++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;
}

❸ java：八皇后问题解题思路

递归：
首先每一行放置均会循环，也就是每一行的皇后都会被依次放置在8个位置上；
1）第一行在第一个位置上放置1枚皇后；
2）第二行在第一个位置上放置皇后，如果与已有的皇后不在一条直线上，则进入下一行，否则位置+1;
3）余下几行均依照步骤2）的方法进行放置，当最后一行放置好，打印输出；
可以写个函数，EightQueen（int
n,
int
*Pos）,其中n表示第几行，Pos指向一个数组，Pos[i]=j表示第i行的位置是j；EightQueen（int
n,
int
*Pos）从n=1开始递归，到n=8递归结束。
代码就不写了，没写过java，写不来

❹ Java 八皇后问题解释

public class Queen{//同栏是否有皇后，1表示有private int[] column;//右上至左下是否有皇后private int[] rup;//左上至右下是否有皇后private int[] lup;//解答private int[] queen;//解答编号private int num;public Queen(){column=new int[8+1];rup=new int[(2*8)+1];lup=new int[(2*8)+1];for(int i=1;i<=8;i++)column[i]=0;for(int i=1;i<=(2*8);i++)rup[i]=lup[i]=0; //初始定义全部无皇后 queen=new int[8+1];} public void backtrack(int i){if(i>8){showAnswer();}else{for(int j=1;j<=8;j++){if((column[j]==0)&&(rup[i+j]==0)&&(lup[i-j+8]==0)){//若无皇后queen[i]=j;//设定为占用column[j]=rup[i+j]=lup[i-j+8]=1;backtrack(i+1); //循环调用column[j]=rup[i+j]=lup[i-j+8]=0;}}}} protected void showAnswer(){num++;System.out.println("\n解答"+num); for(int y=1;y<=8;y++){for(int x=1;x<=8;x++){if(queen[y]==x){System.out.print("Q");}else{System.out.print(".");}} System.out.println();}} public static void main(String[]args){Queen queen=new Queen();queen.backtrack(1);}}

❺ 八皇后问题的java代码。

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;i<n;i++) {
for(j=0;j<n;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;j<n;j++) {
//如果在第i行的第j列可以布放皇后
if(col[j]==0&&md[n+i-j-1]==0&&sd[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(i<n-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定义结束
关于看代码的人人都知道的小技巧，最小试探法来输出结果进行比较和分析

❻ 请教JAVA大神，八皇后问题代码

publicclassQueen{
//同栏是否有皇后，1表示有
privateint[]column;

//右上至左下是否有皇后
privateint[]rup;

//左上至右下是否有皇后
privateint[]lup;

//解答
privateint[]queen;

//解答编号
privateintnum;

publicQueen(){
column=newint[8+1];
rup=newint[(2*8)+1];
lup=newint[(2*8)+1];

for(inti=1;i<=8;i++)
column[i]=1;

for(inti=1;i<=(2*8);i++)
rup[i]=lup[i]=1;

queen=newint[8+1];
}

publicvoidbacktrack(inti){
if(i>8){
showAnswer();
}else{
for(intj=1;j<=8;j++){
if((column[j]==1)&&(rup[i+j]==1)&&
(lup[i-j+8]==1)){
queen[i]=j;
//设定为占用
column[j]=rup[i+j]=lup[i-j+8]=0;
backtrack(i+1);
column[j]=rup[i+j]=lup[i-j+8]=1;
}
}
}
}

protectedvoidshowAnswer(){
num++;
System.out.println("
解答"+num);

for(inty=1;y<=8;y++){
for(intx=1;x<=8;x++){
if(queen[y]==x){
System.out.print("Q");
}else{
System.out.print(".");
}
}

System.out.println();
}
}

publicstaticvoidmain(String[]args){
Queenqueen=newQueen();
queen.backtrack(1);
}
}

❼ 求：N皇后问题的JAVA代码

这是我刚写的程序
程序如下:
import java.util.*;
import java.io.*;

public class NQueens {

public static void print(int a[]){//输出解
//int b[]=a;
for(int i=1,j=a.length-1;i<a.length;i++,j--){
System.out.print(a[i]+"--");
//b[j]=a[i];//记录对称解
}
a[0]++;
System.out.println();
/*for(int i=1;i<b.length;i++){
System.out.print(b[i]+"--");
}
a[0]++;
System.out.println();*/
}//print

public static void main (String[] args) throws IOException{

BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
System.out.print("Please input the number of queens:");
int n=Integer.parseInt(bf.readLine());
System.out.println("n="+n);
System.out.println("start...");
long start=new Date().getTime();
int a[]=new int[n+1];
for(int i=0;i<n+1;i++) a[i]=0;//初始化棋盘

for(int cTemp=1,rTemp=1,j=1;cTemp<=n;cTemp++){//(n+1)/2
a[1]=cTemp;//第一个皇后依次放在每一列上面

for(rTemp=1,j=1;rTemp+1<=n;){

if(j>n&&j!=1) {j=a[rTemp]+1;rTemp--;continue;}//
a[rTemp+1]=j;//第rTemp+1个皇后试着放在第j列
if(a[1]==n&&a[2]==n) break;//全部访问完毕
//System.out.println("Aa[rTemp+1]"+(rTemp+1)+":"+a[rTemp+1]);//
int i;

for(i=1;i<rTemp+1;i++){//检测是否与已放的皇后有冲突
if(a[i]==a[rTemp+1]||Math.abs(rTemp+1-i)==Math.abs(a[rTemp+1]-a[i])) {
//两个皇后在同一列上或在同一对角线上，不行
//System.out.println("Ba[rTemp+1]"+(rTemp+1)+":"+a[rTemp+1]);//
//System.out.println("j:"+j);//
//System.out.println("i:"+i);//
break;
}
//System.out.println("break1");break;
}//for

if(i==rTemp+1) {//第rTemp+1个皇后可以放
rTemp++;
j=1;
//System.out.println("continue");//
if(rTemp==n) {NQueens.print(a);j=a[rTemp-1]+1;rTemp=rTemp-2;}//找到一个可行解
continue;
}
else if(j==n) {rTemp--;j=a[rTemp+1]+1;if(rTemp==1&&a[rTemp+1]>=n) break;else continue;}

//放完了，无解，回溯到上一个皇后
else if(j<n){j++;continue;}//还没放完，继续
else if(a[rTemp+1]==n) break;//
//if(j>n) {System.out.println("j>n,break2");break; }
//System.out.println("Ca[rTemp+1]:"+(rTemp+1)+":"+a[rTemp+1]);//
if(rTemp+1==n) break;
//System.out.println("break2");break;
}//for

if(rTemp==cTemp) continue;
//System.out.println("break3");break;
}//for

long end=new Date().getTime();
System.out.println("System runtime is "+(end-start)+" ms.");
System.out.println("The "+n+" queen problem's solution number is:"+a[0]);
System.out.println("end...");
}

}

❽ java八皇后问题的实验报告

http://blog.itweb2.com/article.asp?id=140
*
* 8皇后问题：
*
* 问题描述：
* 在一个8×8的棋盘里放置8个皇后，要求每个皇后两两之间不相冲突
*（在每一横列，竖列，斜列只有一个皇后）。
*
* 数据表示：
* 用一个 8 位的 8 进制数表示棋盘上皇后的位置：
* 比如：45615353 表示：
* 第0列皇后在第4个位置
* 第1列皇后在第5个位置
* 第2列皇后在第6个位置
* 。。。
* 第7列皇后在第3个位置
*
* 循环变量从 00000000 加到 77777777 （8进制数）的过程，就遍历了皇后所有的情况
* 程序中用八进制数用一个一维数组 data[] 表示
*
* 检测冲突：
* 横列冲突：data == data[j]
* 斜列冲突：(data+i) == (data[j]+j) 或者 (data-i) == (data[j]-j)
*
* 好处：
* 采用循环，而不是递规，系统资源占有少
* 可计算 n 皇后问题
* 把问题线性化处理，可以把问题分块，在分布式环境下用多台计算机一起算。
*
* ToDo：
* 枚举部分还可以进行优化，多加些判断条件速度可以更快。
* 输出部分可以修改成棋盘形式的输出
*
* @author cinc 2002-09-11
*
*/

public class Queen {
int size;
int resultCount;

public void compute ( int size ) {
this.size = size;
resultCount = 0;
int data[] = new int[size];
int count; // 所有可能的情况个数
int i,j;

// 计算所有可能的情况的个数
count = 1;
for ( i=0 ; i<size ; i++ ) {
count = count * size;
}
// 对每一个可能的情况
for ( i=0 ; i<count ; i++ ) {
// 计算这种情况下的棋盘上皇后的摆放位置，用 8 进制数表示
// 此处可优化
int temp = i;
for ( j=0 ; j<size ; j++ ) {
data [j] = temp % size;
temp = temp / size;
}
// 测试这种情况是否可行，如果可以，输出
if ( test(data) )
output( data );
}
}

/*
* 测试这种情况皇后的排列是否可行
*
*/
public boolean test( int[] data ) {
int i,j;
for ( i=0 ; i<size ; i++ ) {
for ( j=i+1 ; j<size ; j++ ) {
// 测试是否在同一排
if ( data == data[j] )
return false;
// 测试是否在一斜线
if ( (data+i) == (data[j]+j) )
return false;
// 测试是否在一反斜线
if ( (data-i) == (data[j]-j) )
return false;
}
}
return true;
}

/*
* 输出某种情况下皇后的坐标
*
*/
public void output ( int[] data ) {
int i;
System.out.print ( ++resultCount + ": " );
for ( i=0 ; i<size ; i++ ) {
System.out.print ( "(" + i + "," + data + ") " );
}
System.out.println ();
}
public static void main(String args[]) {
(new Queen()).compute( 8 );
}
}