#include <vector>
#include <iostream>

using namespace std;


bool boardful();
bool check2(int f,bool already);
int comp_move(int s);
int check(int c,int d);
void setBoard(int p);



int MAX = 100;
int MIN = -100;
typedef int depth;
typedef int State;
typedef int Ply;
typedef int ListIndex;


vector<int> board(18);          /* dummy game tree   */
vector<int> solutions(20);      

/* this function is used to compute the gcd which is in turn 
*  used to deduce possible solutions to game.
*/
int euclid(int a ,int b)
{
    if(b==0)
        return a;
    else 
        return euclid(b,a%b);
}



int game(int x, int y, int j)
{
    int i1;
    int i,k,m;
    cout << endl << endl;
    board[0] = x;
    board[1] = y;
    cout << "      " << x << "     " << y << " " << endl<< endl;
    if(x == y)
    {
               cout << " DRAW - NO WINNER ! " << endl;
               return 0;
    }
          
    for(i=0; i<j-2;i=i+2)
    {     
          
          cout << endl;
          cout << "Enter the difference: ";
          
          cin >> i1;
          check(i1,j);
          
          for(int k=0;k<board.size();k++){
                if(board[k]==0)
                   break;                
                else
                   cout << board[k] << "  ";
          }
          cout << endl;
          cout << endl << "COMPUTER: " << comp_move(i) << endl<<endl;
          
          for(int k=0;k<board.size();k++){
                if(board[k]==0)
                   break;                
                else
                   cout << board[k] << "  ";
          } 
      
         
    }            
    cout << " You WIN! " << endl;
    return 0;
}            

int check(int c,int d)
{      
       bool t = true;
       bool already = false;
       for(int x=0; x<d;x++)
       {     if(solutions[x] == c)
             {  //cout << "valid solution! ";
                t =false;
                check2(c,already);
                if(!already)
                   setBoard(c);
                
                break;     
             }
             
       }
       if(t){
             cout << "invalid solution! " << endl;
             cout << "LOSE your turn. " << endl;
             return d-1;
       }
        if(board.size() == d)
             cout << "WINNER " << endl;
       
       return 0;
}

bool check2(int f, bool already)
{
     for(int x=0; x<board.size();x++)
     {          if(board[x] == f){
                   cout << " Number already on the board. " << endl;
                   cout << "      LOSE your turn.         " << endl;   
                   //already = true;
                   return -1;
                }
     }              
     already = false;
     return already;
}

int comp_move(int m)
{ 
  int cm=0; 
  int x=0;
  cm = (rand() % 10) + 1;
     
  for(int i=0;i<solutions.size();i++)
  {
    if(solutions[i] == cm)
    { 
      for(int r=0; r<board.size();r++){
       if(board[r] == cm)
          cm = solutions[r+1];
      }
      setBoard(cm);
      return cm;
    }                       
  }  
}
  
       
    
void setBoard(int c)
{
     int d;
     for(int i=0;i<board.size();i++)
     {  
        if(board[i] == c)
           return;
        else if(board[i] == 0)
             { board[i] = c;
               return;
             }
     }
     
}
     


float Max(float X, float Y)
  // Returns maximum of X and Y.
{
    if (X > Y)
      return X;
    else
      return Y;
}

float Min(float X, float Y)
  //Returns minimum of X and Y.
{
    if (X < Y)
      return X;
    else
      return Y;
}

int game2(int x, int y, int j)
{
    int i1;
    int i,k,m;
    cout << endl << endl;
    board[0] = x;
    board[1] = y;
    cout << "      " << x << "     " << y << " " << endl<< endl;
    if(x == y)
    {
               cout << " DRAW - NO WINNER ! " << endl;
               return 0;
    }
          
    for(i=0; i<j-2;i=i+2)
    {     
          int n = j-2;
          cout << endl;
          cout << endl << "COMPUTER: " << comp_move(m) << endl<<endl;
          for(int k=0;k<board.size();k++){
                if(board[k]==0)
                   break;                
                else
                   cout << board[k] << "  ";
          } 
          cout << "Enter the difference: ";
          cin >> i1;
          check(i1,j);
          
          for(int k=0;k<board.size();k++){
                if(board[k]==0)
                   break;                
                else
                   cout << board[k] << "  ";
          }
          cout << endl;
    }            
    cout << " You WIN! " << endl;
    return 0;
}            

// MAIN FUNCTION     
      
int main()
{
    int n1, n2 ;
    int n3=0;
    int n4=0;
    int i=1;
    int ch;
    srand(time(NULL));
    do{
       n1 = (rand() % 10) + 1;
       n2 = (rand() % 10) + 1;
    }while(n1<n2);
    cout << "  *****  *   *    ***   *     *****   *****  '   *****   " << endl;
    cout << "  *      *   *   *      *       *     *    *     *       " << endl;
    cout << "  ***    *   *   *      *       *     *     *     ****   " << endl;
    cout << "  *      *   *   *      *       *     *    *         *   " << endl;
    cout << "  *****   ***     ***   ***** *****   *****      *****   " << endl;
    cout << endl<<endl;
    cout << "---------------------------------------------------------" << endl;
    cout << "                  Welcome to Euclid's Game.              " << endl;
    cout << " The object of this game is simple. It begins with two   " << endl;
    cout << " random numbers being displayed. Select who goes first:  " << endl;
    cout << " computer or human.                                      " << endl;
    cout << " Players take turns writing the positive differences of  " << endl;
    cout << " the numbers displayed. Play continues until one can't   " << endl;
    cout << " write a difference that is not already displayed. Enjoy!" << endl;
    cout << " --------------------------------------------------------" << endl;
    
    n3 = euclid(n1,n2);
    n4 = n3;
    cout << endl << "All numbers that will appear on the board " << n4 << ",";
    solutions[0] = n4;
    while(i<int(n1/n4))
    {
      n3 =  n3 + n3 / i;
      solutions[i] = n3;
      i++; 
      cout << n3 << ",";
         
    }
    
    cout << endl << endl;
    cout << " Choose which player starts: " << endl;
    cout << "      1. Computer " << endl;
    cout << "      2. Human    " << endl;
    cout << " Enter choice:    ";
    cin >> ch;
    cout << endl;
    switch(ch)
    {
       case 1: game2(n1,n2,i);
               break;
       case 2: game(n1,n2,i);
               break;
    }
    
    /*for(int t=0;t<solutions.size();t++){
        if(solutions[t]==0)
           break;                
        else
           cout << solutions[t] << " ";
    }*/
    cout << endl << endl << endl;
    //cout << "     There were  " << i <<  " possible solutions. " << endl;
    cout << "                 Thanks for playing.              " << endl;
    
    system("pause");
    return 0;
}