/* Problem 5:  Andy Poe's Tic-Tac-Toe 
   Given an incomplete Tic-Tac-Toe board configuration, determine the
   eventual winner of the game. */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char BT[3][3];  /* The 3 x 3 Tic-Tac-Toe grid */

int main (int argc, char **argv);
char Winner (BT Board);
char Turn (BT Board);
char WillWin (BT Board, char t);

FILE *in, *out;

int main (int argc, char **argv) {

  int n; /* # of test cases */
  BT Board; /* Tic-Tac-Toe board */
  char Bstr[10];

 in = fopen ("prob5.in","r");  /* redirect I/O */
 out = fopen ("prob5.out","w");  
 for (fscanf (in,"%d",&n); n>0; n--) { /* read in test cases */
  fscanf (in,"%s",Bstr);
  memcpy (Board,Bstr,sizeof Board); /* read in the board */
  switch (WillWin (Board,Turn(Board))) {  /* print winner */
   case 'X':
    fprintf (out,"X wins the game.\n");
    break;
   case 'O':
    fprintf (out,"O wins the game.\n");
    break;
   default:
    fprintf (out,"The game goes to the cat.\n");
  }
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Winner checks a tic-tac-toe board to determine if someone has already
   won, i.e. if there are 3 in a row of the same mark.  If so, it
   returns the winner, otherwise it returns 'T'. */

char Winner (BT Board) {

  int i; /* Loop iterator */

 for (i = 0; i < 3; i++) {
  if (Board[i][0]==Board[i][1] && Board[i][0]==Board[i][2] && 
      Board[i][0]!='B') return Board[i][0];  /* horizontal row */
  if (Board[0][i]==Board[1][i] && Board[0][i]==Board[2][i] && 
      Board[0][i]!='B') return Board[0][i];  /* vertical row */
 }
 if (Board[0][0]==Board[1][1] && Board[0][0]==Board[2][2] && 
     Board[0][0]!='B') return Board[0][0]; /* diagaonal rows */
 if (Board[0][2]==Board[1][1] && Board[0][2]==Board[2][0] && 
     Board[0][2]!='B') return Board[0][2];
 return 'T';
}

/* Turn returns whose turn it is by counting X's and O's.  If the
   same, it's X's turn.  Otherwise, it's O's turn. */

char Turn (BT Board) {

  int i, j, x=0; /* i and j are loop iterators; x counts the difference
                    between x's and o's */

 for (i = 0; i < 3; i++) 
  for (j = 0; j < 3; j++) 
   switch (Board[i][j]) {
    case 'X':
     x++;
     break;
    case 'O':
     x--;
   }
 return (x==0)?'X':'O';
}

/* WillWin looks at a board and whose turn it is anddetermines who will 
   win this game if everyone makes the best possible move */

char WillWin (BT Board, char t) {

  char w, ww;
  int i, j;

 w = Winner (Board);  /* Has anyone already won the game? */
 if (w=='T') {   /* If not ... */
  w = ' ';
  for (i = 0; i < 3; i++) {    /* Go through the empty squares one by */
   for (j = 0; j < 3; j++) {   /* one, and assume the next turn will */
    if (Board[i][j] == 'B') {  /* be to that square. */
     Board[i][j] = t;
     ww = WillWin (Board,t=='X'?'O':'X');     /* Who wins now? */
     Board[i][j] = 'B';        /* Remove my mark */
     if (ww==t) return t;      /* If I win, that's where I will move!*/
     else if (ww=='T') w = 'T';   
       /* if it's a tie, I will move there for now and hope a better 
          move will present itself */
     else if (w==' ') w = ww;
       /* Losing is only the best move so far if it's the first one I 
          check. */
    }
   }
  }
  if (w==' ') return 'T'; /* If there is no legal move, it's a tie! */
 }
 return w; /* otherwise return my best alternative */
}