//eq.cpp  -- copy from a OO book, modified by tsaiwn@csie.nctu.edu.tw
// Eight Queen problem  西洋棋的八皇后在 8x8 棋盤互相不會打到
// http://en.wikipedia.org/wiki/Eight_queens_puzzle
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// 8 queens are linked using a single linked list.
//////  C++ 認識 bool, 若不認識就 typedef int bool;
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
class Queen {
   int row, column;   // default is private:
   Queen *neighbor;
   bool canAttack(int r, int c);  // [r][c] 是否會被打到?
   bool testOrAdvance( );  // if current position NOT ok then advance
   int firstTryRow;   // used to remember my first try
   static int table[9]; //declare to be used to remember the table, 0 不用
   friend void printTable(Queen);  // 不然就要讓 table[ ] public:
  public:
   Queen(int c, Queen* myNext);
   bool first( );
   bool next( );
   void print( );
}; // class Queen
Queen::Queen(int c, Queen* myNext) {
   column = c; neighbor = myNext;
}
// // //
bool Queen::canAttack(int r, int 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) return neighbor->canAttack(r, c);
   else return false;
}
///
// find the first legal position for this Queen
bool Queen::first( ) {
   firstTryRow = rand( )%8 + 1;  // 一開始任意放 1..8
   row = firstTryRow;
   if(neighbor!=0 && neighbor->first( ) ) return testOrAdvance( );
   return true;
}
///
bool Queen::testOrAdvance( ) {
   if(neighbor && neighbor->canAttack(row, column) ) return next( );
   return true;  // legal position found
}
///
bool Queen::next( ) {
   if(row == firstTryRow) {
      if(! neighbor) 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 Queen::print( ) { // print solution
   if(neighbor) neighbor->print( );  // 印出其他所有在我之前的 Queen,
   printf("column %d,  row %d\n", column, row); // 印出 我
   table[row]=column;
}
// // // // // // // // // // // // //
void printTable(Queen gg) {
   int r, c, i;
   printf("..");
   for(r=1; r <=8; ++r) printf("%2d", r); 
   printf("\n");
   for(r=1; r <= 8; ++r) {
      c = gg.table[r];   // c = Queen::table[r];
      printf("%d ", r);
      for(i=1; i <  c; ++i) printf("__");
      printf(".X");
      for(i= c+1; i <= 8; ++i) printf("__");
      printf("%2d\n", r);
   } 
   printf("..");
   for(r=1; r <=8; ++r) printf("%2d", r); 
   printf("\n");
   return;
}
int Queen::table[9];   // define the static variable in Queen
int main( ) {
   Queen *lastQueen = 0;  // NULL 就是 0
   srand(time(0));  // true random
   // 每隻 queen 先不決定 row, 且用 Linked List 串起來
   for(int col = 1; col <=8; col++)
      lastQueen = new Queen(col, lastQueen);
   // hava all queens move to legal table and  print the solution
   printf("Note that this is NOT the only one solution.\n");
   if( lastQueen->first( ) ) lastQueen->print( );
   printTable(*lastQueen);
   return 0;
}