/*
coded by :Da_MoRz
Email :p_mdriyaz@hotmail.com

header file : functions.h
*/

knight::knight(void)
     {

     loc_row=-1;
     cout<<"Enter the starting coordintes :"<<endl;
     cout<<"Row(1-8) :";cin>>row;
     cout<<"Coloum(1-8) :";cin>>col;

     if(row<1 || row>8 || col<1 || col>8)
          {

               cout<<"Invalid location";
               exit(0);

          }

     row--;
     col--;

     for(int m=0;m<8;m++)
          for(int n=0;n<8;n++)
               chess[m][n]=0;

     for(int m=0;m<64;m++)
          for(int n=0;n<10;n++)
               location[m][n]=0;

     for(int m=0;m<64;m++)
          denied[m]=9999;

     for(int m=0;m<8;m++)
          valid[m]=9999;

     assignment();

     }//end function

void knight::assignment(void)
     {

     while(1)
          {

               int pos;
               chess[row][col]=1;
               refresh();
               pos=value(linear(row,col));
               dimension(row,col,pos);

          }//end while

     }//end function

int knight::value(int val)
     {

     int swap,
          found,
          ii,
          jj;

     loc_row++;
     location[loc_row][0]=val;

     if(loc_row==63)
          display();

     dimension(ii,jj,val);
     possiblity(val);
     append();

     for(int m=1;m<10 && location[loc_row][m]!=-1;m++)
          {

               found=0;
               possiblity(location[loc_row][m]);

               for(int n=0;n<8 && valid[n]!=9999;n++)
                    {

                         dimension(ii,jj,valid[n]);
                         if(chess[ii][jj]==0)
                              {

                                   found=1;
                                   break;

                              }

                    }//end for n

               if(!found)
                    {

                         swap=location[loc_row][m];
                         break;

                    }

          }//end for m

          if(!found && location[loc_row-1][2]==-1)
               {

                    if(loc_row==62)
                         return swap;

                    backtrace();
               }

          if(!found && location[loc_row-1][2]!=-1)
               backtrace();

          while(location[loc_row][1]==-1)
               backtrace();

          #ifdef std

               std_algorithm();

          #endif

          return location[loc_row][1];

     }//end function

void knight::refresh(void)
     {

     int count=0;

     for(int m=0;m<8;m++)
          {

               for(int n=0;n<8;n++)
                    {

                         if(chess[m][n]==1)
                              {

                                   denied[count]=linear(m,n);
                                   count++;

                              }

                    }//end for n

          }//end for m

     for(int m=count;m<64;m++)
          denied[m]=9999;

     }//end function

void knight::append()
     {

     int ii,
          jj,
          lock,
          temp;

     temp=1;

     for(int m=0;m<8 && valid[m]!=9999;m++)
          {

               dimension(ii,jj,valid[m]);
               lock=1;

               for(int n=0;n<64;n++)
                    if(denied[n]==valid[m])
                         {

                              lock=0;
                              break;

                         }

               if(lock)
                    {

                         location[loc_row][temp]=valid[m];
                         temp++;

                    }

          }//end for m

     location[loc_row][temp]=-1;

     }//end function

int knight::possiblity(int val)
     {

     int counter=0,
          ii,
          jj;

     dimension(ii,jj,val);

     if(check(ii-1,jj-2)) {valid[counter]=linear(ii-1,jj-2);counter++;}
     if(check(ii-1,jj+2)) {valid[counter]=linear(ii-1,jj+2);counter++;}
     if(check(ii+1,jj-2)) {valid[counter]=linear(ii+1,jj-2);counter++;}
     if(check(ii+1,jj+2)) {valid[counter]=linear(ii+1,jj+2);counter++;}
     if(check(ii-2,jj-1)) {valid[counter]=linear(ii-2,jj-1);counter++;}
     if(check(ii-2,jj+1)) {valid[counter]=linear(ii-2,jj+1);counter++;}
     if(check(ii+2,jj-1)) {valid[counter]=linear(ii+2,jj-1);counter++;}
     if(check(ii+2,jj+1)) {valid[counter]=linear(ii+2,jj+1);counter++;}

     for(int m=counter;m<8;m++)
          valid[m]=9999;

     return counter;

     }//end function

void knight::backtrace(void)
     {

     int ii,
          jj;

     dimension(ii,jj,location[loc_row][0]);
     chess[ii][jj]=0;
     loc_row--;

     for(int m=1;m<9;m++)
          location[loc_row][m]=location[loc_row][m+1];

     }//end function

#ifndef chess_display

     void knight::display(void)
          {

          int ii,
               jj;

          cout<<"The result is :"<<endl;

          for(int m=0;m<64;m++)
               {

                    dimension(ii,jj,location[m][0]);
                    chess[ii][jj]=m+1;

               }//end for m

          for(int m=0;m<8;m++)
               {

                    for(int n=0;n<8;n++)
                         {

                              cout<<setw(2)<<chess[m][n]<<" ";

                         }//end for n

                    cout<<endl;

               }//end for m

          getche();
          exit(0);

          }//end function

#endif

int knight::check(int ii,int jj)
     {

     if(ii<0 || jj<0 || ii>7 ||jj>7)
          return 0;
     return 1;

     }//end function

void knight::dimension(int &ii,int &jj,int val)
     {
          ii=val/8;
          jj=val%8;

          }//end function

int knight::linear(int ii,int jj)
     {
          return ((8*ii)+jj);

          }//end function

void main()
     {
          knight k;

          }//end function