//eq.java  -- copy from a OO book, modified by tsaiwn@csie.nctu.edu.tw
// javac eq.java
// java eq
// Eight Queen problem  西洋棋的八皇后在 8x8 棋盤互相不會打到
// http://en.wikipedia.org/wiki/Eight_queens_puzzle
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// 8 queens are linked using a single linked list.
//////  Java 認識 boolean, 是 C++ 的 bool
class Queen {
   int row, column;     // 沒寫 access modifier 是 package available
   Queen neighbor;    // C++ 的 pointer 在  Java 是 reference
   boolean canAttack(int r, int c){  // [r][c] 是否會被打到?
      int cdiff;
      if(row == r) return true;
      cdiff = c - column;
      if(row + cdiff == r) return true;
      if(row - cdiff == r) return true;
      // check it's neighbor
      if(neighbor!=null) return neighbor.canAttack(r, c);
      else return false;
   }
   boolean testOrAdvance( ){  // if current position NOT ok then advance
     if(neighbor!=null && neighbor.canAttack(row, column) ) return next( );
     return true;  // legal position found
   }
   int firstTryRow;   // used to remember my first try
   static int table[ ] = new int[9];  // why static ?
   //friend void printTable(Queen);  // 不然就要讓 table[ ] public:
   Queen(int c, Queen myNext) {  // constructor
      column = c; neighbor = myNext;
   }
   boolean first( ) {  // note that  0 <= Math.random( )  < 1
     firstTryRow = (int)(Math.random( ) *1000)%8 + 1;  // 一開始任意放 1..8
     row = firstTryRow;
     if(neighbor!=null && neighbor.first( ) ) return testOrAdvance( );
     return true;
   }
   boolean next( ) {
     if(row == firstTryRow) {
        if(neighbor == null) return true;  // 看完全部 queen 了
        if(! neighbor.next( ) ) return false;
     }
     if(row==8) row = 0;  // wrap around because we begin at any row
     ++row;
     return testOrAdvance( );
   }
   void print( ) {
     if(neighbor!=null) neighbor.print( );  // 印出其他所有在我之前的 Queen,
     System.out.printf("column %d,  row %d\n", column, row); // 印出 我
     table[row]=column;
   }
}; // class Queen
// // // // // // // // // // // // //
class eq {
 static void printTable(Queen gg) {
   int r, c, i;
   System.out.printf("..");
   for(r=1; r <=8; ++r) System.out.printf("%2d", r);
      System.out.printf("\n");
   for(r=1; r <= 8; ++r) {
      c = gg.table[r];   // c = Queen.table[r];
      System.out.printf("%d ", r);
      for(i=1; i <  c; ++i) System.out.printf("__");
      System.out.printf(".X");
      for(i= c+1; i <= 8; ++i) System.out.printf("__");
      System.out.printf("%2d\n", r);
   } 
   System.out.printf("..");
   for(r=1; r <=8; ++r) 
       System.out.printf("%2d", r); System.out.printf("\n");
   return;
 } // printTable
 public static void main(String [ ] xxx ) {
   Queen lastQueen = null;  // NULL 就是 0
   //srand(time(0));  // true random, Java already does this
   // 每隻 queen 先不決定 row, 且用 Linked List 串起來
   for(int col = 1; col <=8; col++)
      lastQueen = new Queen(col, lastQueen);
   // hava all queens move to legal position and  print the solution
   System.out.printf("Note that this is NOT the only one solution.\n");
   if( lastQueen.first( ) ) lastQueen.print( );
   printTable(lastQueen);
   return;
 } // main
}