情人碰面的问题.java代码.txt

情人碰面的算法问题． JAVA编写的

情人碰面的问题.JAVA代码 
 
/* 
* ８情人问题： 
* 
* 问题描述： 
* 在一个８×８的棋盘里放置８个情人，要求每个情人两两之间不相冲突 
*（在每一横列，竖列，斜列只有一个情人）。 
* 
* 数据表示： 
* 用一个 8 位的 8 进制数表示棋盘上情人的位置： 
* 比如：45615353 表示： 
* 第0列情人在第4个位置 
* 第1列情人在第5个位置 
* 第2列情人在第6个位置 
* 。。。 
* 第7列情人在第3个位置 
* 
* 循环变量从 00000000 加到 77777777 （8进制数）的过程，就遍历了情人所有的情况 
* 程序中用八进制数用一个一维数组 data[] 表示 
* 
* 检测冲突： 
* 横列冲突：data[i] == data[j] 
* 斜列冲突：(data[i]+i) == (data[j]+j) 或者 (data[i]-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[i] == data[j]) 
return false; 
// 测试是否在一斜线 
if ( (data[i]+i) == (data[j]+j) ) 
return false; 
// 测试是否在一反斜线 
if ( (data[i]-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[i] + " " ); 
} 
System.out.println (); 
} 

//main()就是在这里. 
public static void main(String args[]) { 
(new Queen()).compute( 8 ); 
} 
}