queen.java

一个八皇后问题的解决方案

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 ();
   }
   public static void main(String args[]) {
       (new Queen()).compute( 8 );
   }
}