情人碰面的问题：JAVA代码概述

核心提示：/** ８情人问题：** 问题描述：* 在一个８×８的棋盘里放置８个情人，要求每个情人两两之间不相冲突*（在每一横列，情人碰面的问题：JAVA代码概述，竖列，斜列只有一个情人），* 输出部分可以修改成棋盘形式的输出** @author cinc 2002-09-11**/public class Queen {int

　　/*
　　* ８情人问题：
　　*
　　* 问题描述：
　　* 在一个８×８的棋盘里放置８个情人，要求每个情人两两之间不相冲突
　　*（在每一横列，竖列，斜列只有一个情人）。
　　*
　　* 数据表示：
　　* 用一个 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 );
　　}
　　}