//
// Code for the 8queen problem using the heuristic
// Astar method and using four different ways to
// decide the basis for index calculation
//
//                       Sameer Singh
//
#include <stdio.h>
#include <math.h>
#include <conio.h>
//These are the global constant storing the dimension
//of the square matrix in N (2 to 8) and the output
//filename in filename[]
const int N=8;
const char filename[]="astar.out";
FILE *fp=fopen(filename,"w");
//This is a string copy function different from the
//inbuilt one since it ignores the NULL character
void strcpy(unsigned char *a, unsigned char *b)
{
  for(int i=0;i<N;i++)
    a[i]=b[i];
}

class node;
void disp(node t);

//                  //
//     CLASSES      //
//                  //
class node                      //This is the main class which
{                               //stores each node of the list
  public:                       //The data members include the
  unsigned char map[N];         //coordinates and the number of
  unsigned char x[N],y[N];      //queens placed, alongwith a
  float index;                  //boolean map of the board and
  unsigned int queens;          //the index. There is also a
  node *next;                   //pointer to the next node in
                                //list
  //The constructor initialises all to zero
  node()
  {
    for(int i=0;i<N;i++)
    {
      map[i]=0;
      x[i]=0; y[i]=0;
    }
    index=0.0;
    queens=0;
    next=NULL;
  }
  //According to the coordinates, this function extracts the status
  //from the boolean map. The map is stored as 8 characters, i.e.
  //8X8 bits. It returns -1 for out of range coordinates
  int get(unsigned char i,unsigned char j)
  {
    if((i>N)&&(j>N)&&(i<0)&&(j<0)) return -1;
    j=N-j-1;
    return int(map[i]/pow(2,j))%2;
  }
  //This function follows similiar logic as get() to assign a value
  //to any cell of the board
  void set(unsigned char i,unsigned  char j,unsigned  char v)
  {
    if((i<N)&&(j<N)&&(i>=0)&&(j>=0))
    {
      if(v==0)
        if(get(i,j)==1)
          map[i]-=int(pow(2,N-j-1));
      if(v==1)
      {
        if(get(i,j)==0)
        {
          map[i]+=int(pow(2,N-j-1));
        }
      }
    }
  }
  //This function assigns the index of the noe, and returns it
  //also. It has 4 methods. They are explained below. Each of
  //them can be seperately selected by commenting as required
  float calc_index()
  {
    // Code for heuristic index calculation

    // 1. By Maximising the number of queens
    //      This is a simple method in which the node with most
    //      queens placed is preferred. Thus it does not revert
    //      to an earlier state unless no space is left on board
    
    //    Finished 8x8 in 25943 steps

//    index=queens;   //Uncomment this statement

    // 2. By Maximising the number of Attacking squares
    //       In this method, the preference is given to moves
    //       which lead to most number of squares getting
    //       attacked.
    //    Finished 8x8 in 867 steps
    
/*
    index=0.0;
    for(int i=0;i<N;i++)
      for(int j=0;j<N;j++)   //Uncomment this block
        if(get(i,j)==0)
          index++;
    index=-index;
*/


    // 3. By Minimising the Number of Adjacent sides
    //       This method is to indirectly calculate the
    //       number of adjacent cells in the square matrix.
    //       More adjacent sides coressponds to clusters of
    //       cells together, which, when trying out by playing
    //       ourselves, is something which humans avoid in this
    //       problem. It works to drastically reduce the steps
    //   Finished 8x8 in 94 steps

/*
   index=0.0;
    for(int i=0;i<N;i++)
     for(int j=0;j<N;j++)
     {
       if(get(i,j)==0)
       {
         if(get(i+1,j)==0) index++;
         if(get(i-1,j)==0) index++;
         if(get(i+1,j+1)==0) index++;
         if(get(i+1,j-1)==0) index++;
         if(get(i+1,j+1)==0) index++;
         if(get(i-1,j-1)==0) index++;
         if(get(i+1,j-1)==0) index++;
         if(get(i-1,j+1)==0) index++;
       }
     }
    index=-index;
*/

    //3. By Minimising the Standard Deviations
    //      This heuristic is taken by finding out 4
    //      standard deviations and multiplying them.
    //      They are the deviations of x coordinates,
    //      the y coordinates, x & y coords when points
    //      turned by 45 degrees. This gives an idea of
    //      shape of the resulting areas where the queens
    //      can be placed. Minimising it quickly reaches
    //      the solution
    //   Finished 8x8 in 84 steps

    index=1.0;
    float meanx=0.0,meany=0.0,meandx=0.0,meandy=0.0, tot=0.0;
    float devx=0.0,devy=0.0,devdx=0.0,devdy=0.0;
    for(int i=0;i<N;i++)
     for(int j=0;j<N;j++)
      if(get(i,j)==0)
        { meanx+=i; meany+=j; meandx+=i+j; meandy+=i-j; tot++;}
   meanx/=tot;  meany/=tot;  meandx/=tot;  meandy/=tot;

    for(int i=0;i<N;i++)
     for(int j=0;j<N;j++)
      if(get(i,j)==0)
        { devx+=abs(i-meanx);
          devy+=abs(j-meany);
          devdx+=abs(i+j-meandx);
          devdy+=abs(i-j-meandy);
        }
    devx/=tot;  devy/=tot;  devdx/=tot;  devdy/=tot;
    index=-1*devx*devy*devdx*devdy;

     //End of calculation of the index
     return index;
  }
};

class list              //This is a simple class storing the
{                       //list of options in a sorted priority
  public:               //way, since we are only concerned
  node *start;          //with the topmost node, regardless of
                        //place of the node in the graph.
  list()
  {
    start=NULL;
  }
  //Function to update list according to topmost
  int update();
  //Function to add a node in a sorted list
  //the parameters are the details of the node to be added
  void add(unsigned char *map, int queens,
           unsigned char *x, unsigned char *y)
  {
    if(start==NULL)
    {
      start=new node;
      strcpy(start->map,map);
      start->queens=queens;
      strcpy(start->x,x);
      strcpy(start->y,y);
      start->calc_index();
      start->next=NULL;
    }
    else
    {
      node a;
      strcpy(a.map,map);
      a.queens=queens;
      float i=a.calc_index();
      node *temp=start;
      if(i>=start->index)
      {
        node *temp2=new node;
        strcpy(temp2->map,map);
        temp2->queens=queens;
        strcpy(temp2->x,x);
        strcpy(temp2->y,y);
        temp2->calc_index();
        temp2->next=start;
        start=temp2;
      }
      else
      {
        while((temp->next!=NULL)&&(temp->next->index>=i))
        {
          temp=temp->next;
        }
        if(temp->next==NULL)
        {
          node *temp2=new node;
          temp->next=temp2;
          strcpy(temp2->map,map);
          temp2->queens=queens;
          strcpy(temp2->x,x);
          strcpy(temp2->y,y);
          temp2->calc_index();
          temp2->next=NULL;
        }
        else
        {
          node *temp2=new node;
          temp2->next=temp->next;
          temp->next=temp2;
          strcpy(temp2->map,map);
          temp2->queens=queens;
          strcpy(temp2->x,x);
          strcpy(temp2->y,y);
          temp2->calc_index();
        }
      }
    }
  }
  //Function to delete the topmost node
  void del()
  {
    if(start!=NULL)
    {
      node *temp=start->next;
      delete start;
      start=temp;
    }
  }
};
//This function displays the details of a node alongwith
//a grahical representation of the map with queens placed
void disp(node t)
{
  printf("Queens : %d\n",t.queens);
  for(int i=0;i<t.queens;i++)
    printf("(%d, %d) ",t.x[i],t.y[i]);
  printf("\n");
  for(int i=0;i<N;i++)
  {
    printf("           ");
    for(int j=0;j<N;j++)
    {
      char tog=0;
      for(int k=0;k<t.queens;k++)
        if((i==t.x[k])&&(j==t.y[k])) tog=1;
        if(tog) printf("%c  ",219);
        else printf("%c  ",176);
    }
    printf("\n\n");
  }
}

//                    //
//     VOID MAIN      //
//                    //
int main()
{
  clrscr();
  list astar;                 //Stores the list
  unsigned long int steps=0;  //counts the total number of steps
  unsigned char init_map[N];
  for(int i=0;i<N;i++)        //Initiliases an empty map for the
    init_map[i]=0;            //starting of the program
  astar.add(init_map,0,init_map,init_map);
  char flag=0;
  while(flag==0)              //Main Loop of the program. Loops
  {                           //till options over or success. It
    flag=astar.update();      //constantly writes to the file the
    steps++;                  //various steps of placement of queen
    if(flag==0)
    {
      for(int i=0;i<astar.start->queens;i++)
        fprintf(fp,"(%d, %d) ",astar.start->x[i],astar.start->y[i]);
      fprintf(fp,"\n");
    }
  }
  if(flag==-1) printf("No Solution\n");
  if(flag==1) printf("Solution in %D steps!!!\n",steps);

  while(astar.start!=NULL)
    astar.del();
  printf("\n\n     --Sameer Singh\n");
  fclose(fp);
  getch();
  return 0;
}
//                   //
//      UPDATE       //
//                   //
// This function takes the top of the list, stores it in
// a variable and deletes it. Then it checks the node for
// success and failure, returning with the approporiate
// value. If it is none of them, then it adds all the
// possible nodes, generated by placing another queen in
// non-attacking squares, to the list. Then it returns 0
int list::update()
{
  //Failure
  if(start==NULL) return -1;
  //Store the node
  node t,t2;
  t.queens=start->queens;
  strcpy(t.map,start->map);
  strcpy(t.x,start->x);
  strcpy(t.y,start->y);
  t.calc_index();
  //Another copy
  t2.queens=start->queens;
  strcpy(t2.map,start->map);
  strcpy(t2.x,start->x);
  strcpy(t2.y,start->y);
  t2.calc_index();
  //Delete the node
  del();
  //Check for empty
  int flag=1;
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      flag*=t.get(i,j);
  //If empty then return neutral
  if(flag==1) return 0;
  //If not empty and only one queen left, SUCCESS !
  if(t.queens==N-1)
  {
    for(int i=0;i<N;i++)
     for(int j=0;j<N;j++)
      if(t.get(i,j)==0)   //Adding left over position
      { t.x[N-1]=i;       //as the queen position, and
        t.y[N-1]=j;       //then displaying
        t.queens=t.queens+1;        
      }
     disp(t);
     return 1;
  }

  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      if(t.get(i,j)==0)
      {
        strcpy(t2.map,t.map);      //New queen added at (i,j)
        strcpy(t2.x,t.x);
        strcpy(t2.y,t.y);          //t corressponds to the original
        for(int k=0;k<N;k++)       //node, while t2 is the updated
        {                          //node after placement
           t2.set(k,j,1);
           t2.set(i,k,1);
           t2.set(k,j-i+k,1);
           t2.set(k,i+j-k,1);
        }
        t2.x[t.queens]=i;
        t2.y[t.queens]=j;
        t2.queens=t.queens+1;
        add(t2.map,t2.queens,t2.x,t2.y);
      }
  return 0;
}