/*
* ８情人问题
*
* 问题描述
* 在一个８×８的棋盘里放置８个情人要求每个情人两两之间不相沖突
*（在每一横列竖列斜列只有一个情人）
*
* 数据表示
* 用一个 位的 进制数表示棋盘上情人的位置
* 比如 表示
* 第列情人在第个位置
* 第列情人在第个位置
* 第列情人在第个位置
*
* 第列情人在第个位置
*
* 循环变量从 加到 （进制数）的过程就遍历了情人所有的情况
* 程序中用八进制数用一个一维数组 data[] 表示
*
* 检测沖突
* 横列沖突data[i] == data[j]
* 斜列沖突(data[i]+i) == (data[j]+j) 或者 (data[i]i) == (data[j]j)
*
* 好处
* 采用循环而不是递规系统资源占有少
* 可计算 n 情人问题
* 把问题线性化处理可以把问题分块在分布式环境下用多台计算机一起算
*
* ToDo
* 枚举部分还可以进行优化多加些判断条件速度可以更快
* 输出部分可以修改成棋盘形式的输出
*
* @author cinc
*
*/
public class Queen {
int size;
int resultCount;
public void compute ( int size ) {
thissize = size;
resultCount = ;
int data[] = new int[size];
int count; // 所有可能的情况个数
int ij;
// 计算所有可能的情况的个数
count = ;
for ( i= ; i<size ; i++ ) {
count = count * size;
}
// 对每一个可能的情况
for ( i= ; i<count ; i++ ) {
// 计算这种情况下的棋盘上情人的摆放位置用 进制数表示
// 此处可优化
int temp = i;
for ( j= ; j<size ; j++ ) {
data [j] = temp % size;
temp = temp / size;
}
// 测试这种情况是否可行如果可以输出
if ( test(data) )
output( data );
}
}
/*
* 测试这种情况情人的排列是否可行
*
*/
public boolean test( int[] data ) {
int ij;
for ( i= ; i<size ; i++ ) {
for ( j=i+ ; 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;
Systemoutprint ( ++resultCount + : );
for ( i= ; i<size ; i++ ) {
Systemoutprint ( ( + i + + data[i] + );
}
Systemoutprintln ();
}
//main()就是在这里
public static void main(String args[]) {
(new Queen()pute( );
}
}
