/*
	scramble.c   -   Play scrabble against computer
		
	Author: Dale Reed
	Date: 	4/14/99
	Class:	EECS 171
	System: gcc compiler running under UNIX
	Input:  Interactive user's commands
	Output: Resulting 2-D board configuration, tiles in hand, score
	
	Approach: This program implements a pseudo-scrabble game.  The human
			plays against the computer, and the goal is to play the most
			number of tiles from one's "hand", making a valid word on the
			board.  The first letter of each word must be an existing letter
			on the board.  The exception, of course, is the first word, which
			must be entered by the user.
			     The program checks each word by comparing it against a dictionary
			file.  The words in the dictionary file are read into a large array,
			and a binary search is done for each word lookup.
				The computer tries all possible words by generating all permutations
			of the letter tiles in its "hand," prepended by each square on the board.
			The longest generated computer word which is found in the dictionary is
			then selected.
				Note that when a new word has letters adjacent to existing letters,
			unlike scrabble the new adjacent letters need not form a word.  It is 
			recommended that the first move be in the upper-left hand corner of the
			board, as play always proceeds to the right or down.
	
*/

// Include libraries
#include < stdio.h>
#include < stdlib.h>
#include < string.h>
#include < ctype.h>

// Global constants
#define ROWS 26000			// dictionary number of words max.
#define MAXLENGTH 15		// max. size of a word in dictionary
#define LINE_LENGTH 81		// max length of a line
#define BOARD_SIZE 10		// size of board on a side
#define TRUE 1
#define FALSE 0
#define NUMBER_OF_LETTERS 98 // Number of letters stored (no blanks)
#define TILES_IN_HAND 7		 // # of tiles a player has at a time
#define WARNING 1		 // severity level 1 for error message
#define TERMINATE 2		 	// severity level 2 for error message
#define CLEAR_SCREEN 1	 // flag to indicate clearing screen
#define DO_NOT_CLEAR_SCREEN 0 // flag indicating do not clear


//--------------------------------------------------------------------------
void error( char message[], 	// the message
			int severity,		// severity: 1 or 2 (most severe)
			int clearScreen)
// display error message.  Depending on severity, exit.
{
	if ( clearScreen == TRUE)  {
		system( "clear");
	}
	
	printf("\n*** %s ***\n", message);  fflush( stdout);
	
	if ( severity == TERMINATE) {
		printf("Abnormal termination of program...\n"); fflush( stdout);
		exit (-1);
	}
}


//--------------------------------------------------------------------------
void displayWords( 
	char theWords[][ MAXLENGTH], 	// array of dictionary words
	int limit)			// number of words in dictionary
// display words in dictionary limited by size.  Used for debugging.
{
	int size;		// stores size of strings
	int i;			// loop counter		
	int min, max;	// limits on word sizes to display	

	// Selectively display words from dictionary array.  We do not
	// display them all because there are usually tens of thousands
	// of them.	
	printf("Please enter min. and max. sizes of strings to display: ");
	scanf("%d %d", &min, &max);

	printf("\nWords stored in array are: \n");
	for (i=0; i< limit; i++) {
		size = strlen( theWords[ i]);
		if ( (size >= min) && (size <= max) )
			printf( "%s ", theWords[ i]);
	}
	printf("\n");		// leave an extra line at the end
}


//--------------------------------------------------------------------------
void getDictionaryWords( char dictionary[][ MAXLENGTH], // dictionary array
						 char dictionaryFileName[],		// dictionary file name
						 int *numberOfWords)			// number of dictionary words 
// Read dictionary words into dictionary array
{	
	FILE *fin;						// input file pointer
	char tempString[ LINE_LENGTH];	// stores a single string
	int  size;						// string size
	int i;							// loop counter
   
	fin = fopen( dictionaryFileName, "r" );		// Open file
	
	*numberOfWords = 0;
	while ( fscanf( fin, "%s", tempString ) != EOF ) {
		size = strlen( tempString);
		for (i=0; i< strlen( tempString); i++)  {
			if ( islower( tempString[ i]))  {
				tempString[ i] = toupper( tempString[ i]);
			}
		}
		/* Only store words that aren't too long */
		if ( size < MAXLENGTH ) {
			strcpy( dictionary[ (*numberOfWords)++], tempString);
		}
		/* Verify that we still have room in array*/
		if ( *numberOfWords >= ROWS)  {
			/* Bomb out of program, dictionary array is full */
			printf("Exceeded row limit where currentRow = %d.", *numberOfWords);
			printf("  Exiting program...\n");
			fflush(stdout);
			exit( -1);
		}
	}
	fclose( fin);		// Done, close input file
	
	// Now display the number of words found based on word size.  
	// 		Used for debugging.
	// displayWords( dictionary, *numberOfWords);

}




//--------------------------------------------------------------------------
int foundInDictionary( 
			 char *pWord,					// pointer to a word
			 char dictionary[][ MAXLENGTH], // dictionary array
			 int numberOfDictionaryWords)	// number of words in dictionary array					   
// Look up the word in the dictionary array, returning 1 if found, 0 otherwise
{
	int i;				// counter to go through dictionary
	int low, mid, high;	// array indices for binary search
	int searchResult;	// Stores 0 if search succeeded

	// First eliminate any spaces in the words by substituting a NULL 
	//   character for any space found
	for (i=0; i< TILES_IN_HAND; i++)  {
		if ( pWord[ i] == ' ')  {
			pWord[ i] = '\0';	// End of string marker
		}
	}
	
	// Binary search for word
	low = 0;
	high = numberOfDictionaryWords - 1;
	while ( low <= high)  {
		mid = (low + high) / 2;
		searchResult = strcmp( pWord, dictionary[ mid]);
		if ( searchResult == 0)  {
			// found the word
			return 1;	
		}
		else if (searchResult < 0)  {
			// word should be located prior to mid location
			high = mid - 1;
		}
		else  {
			// word should be located after mid location
			low = mid + 1;
		
		}
	}
	
	
/*	Brute force method, takes ~30 seconds per turn
	for (i=0; i< numberOfDictionaryWords; i++)  {
		if( strcmp( pWord, dictionary[ i]) == 0)  {
		   return 1;	// Found the word!
		}
	}
*/

	return 0;	// Did not find the word

}


//--------------------------------------------------------------------------
void getTiles( 	char playerTiles[], 	// tiles player has
				char letters[],			// tiles remaining
				int *tilesRemaining)		// # of tiles remaining
// Get new tiles for player and correspondingly update tilesRemaining
{
	int i;					// loop counter
	int tileIndex;			// the tile to get
	
	// replace blank tiles
	for (i=0; i< TILES_IN_HAND; i++)  {
		if ( playerTiles[ i] == ' ')  {
			// Pick a random tile, use linear probing if it is already taken
			tileIndex = rand() % NUMBER_OF_LETTERS;
			// Verify that all tiles haven't been used up
			if ( *tilesRemaining > 0)  {
				while ( letters[ tileIndex] == ' ')  {
					tileIndex = (tileIndex + 1) % NUMBER_OF_LETTERS;
				}
				// got one, now decrement # available and assign it
				(*tilesRemaining)--;
				playerTiles[ i] = letters[ tileIndex];
				letters[ tileIndex] = ' ';	// Tile taken, blank it out
			}
		} // end if( player...
	} // end for ...
}


//--------------------------------------------------------------------------
void help()
// Display help information
{
	char returnCharacter;
	
	printf("\n");
	printf("     For each move you need to enter a row, a column, a move\n");
	printf("direction (a or d), and the word to be played at that spot.\n");
	printf("You may also enter 'X' to exit or 'H' for help. Input can\n");
	printf("be either upper or lower case.\n"); 
	printf("\n");
	printf("E.g.  \"E3 d rap\"  puts the word \"rap\" starting at row E,\n");
	printf("column 3, going downwards.\n");
	printf("Alternatively \"E3 a rap\" would put the word \"rap\" starting at\n");
	printf("row E, column 3, going across.\n");
	printf("\n");
	printf("Please press the return key to continue...");
	scanf("%c", &returnCharacter);
}


//--------------------------------------------------------------------------
void initialize( char board[ ][ BOARD_SIZE], 	// the board
				 char letters[],				// stores scrabble letter tiles
				 char lettersFileName[],		// file name for tiles
				 char computerTiles[],			// tiles the computer has
				 char humanTiles[],				// tiles human has
				 int *tilesRemaining)			// # of tiles remaining
{
	int i,j;		// loop counters
	int totalTiles;	// total tiles, used for sanity check
	FILE *fTiles;
	char aLine[ LINE_LENGTH];	// Store an entire input line at a time
	char letter;				// Stores letter read in from input line
	int howManyLetters;			// How many of that letter there are
	int value;					// Value for that letter for scoring.
								//   Not used in this program.
	int currentLetterIndex = 0;	// iterator used to track current spot
								// to store a letter in letters array
			
	// Display initial welcome and game explanation.
	system( "clear");  	// clear the screen
	printf("     Welcome to the game of scramble, where you try to build \n");
	printf("English words on a board. The board itself is two dimensional,\n");
	printf("with rows marked by letters, and columns marked by numbers.\n");
	printf("A combination of row and column uniquely identify each square.\n");
	printf("     Each word you create (after the first one) must start \n");
	printf("with an existing letter on the board, and the subsequent \n");
	printf("letters must be played into blank squares. Words must be \n");
	printf("created out of the tiles you have in your \"hand\".\n");
	printf("     When a new word has letters adjacent to existing letters,\n");
	printf("you do not need to create valid words with those adjacent letters.\n");
	printf("One point is given per letter played.  The winner is the player with\n");
	printf("the most points.");
	printf("\n");
	
	// initialize 2-D board with periods
	for (i=0; i< BOARD_SIZE; i++)  {
		for (j=0; j < BOARD_SIZE; j++)  {
			board[ i][ j] = '.';
		} 
	}
	
	fTiles = fopen( lettersFileName, "r");
	fgets( aLine, LINE_LENGTH, fTiles);		// read in an entire line
	sscanf( aLine, "%d", &totalTiles);		// read number from input line
	fgets( aLine, LINE_LENGTH, fTiles);		// skip title line
	if ( totalTiles != NUMBER_OF_LETTERS)  {
		// Sanity check
		printf( " *** Error, number of tiles: %d ", totalTiles);
		printf( "in file %s", lettersFileName);
		printf(" doesn't match NUMBER_OF_LETTERS: %d\n", NUMBER_OF_LETTERS);
		printf(" Exiting program...\n");
		exit( -1);
	}
	
	// zero out totalTiles and use it to accumulate sum of number of tiles
	// to again verify totals are correct
	totalTiles = 0;
	
	// Read number of each type of tile in from file
	while (	fgets( aLine, LINE_LENGTH, fTiles) != NULL)  {
		sscanf( aLine, "%c %d %d", &letter, &howManyLetters, &value);
		totalTiles += howManyLetters;
		for (i=currentLetterIndex; i< currentLetterIndex + howManyLetters; i++)  {
			letters[ i] = letter;
		}
		currentLetterIndex+= howManyLetters;
	}
	
	// Verify sum of individual letters equals total at top of file
	if ( totalTiles != NUMBER_OF_LETTERS)  {
		// Sanity check
		printf(" *** Error, sum of number of letters: %d ", totalTiles);
		printf("in file %s ", lettersFileName);
		printf(" doesn't match NUMBER_OF_LETTERS: %d\n", NUMBER_OF_LETTERS);
		printf(" Exiting program...\n");
		exit( -1);
	}
	
	fclose( fTiles);
	
	// Seed random number generator used for getting tiles
	srand( 0);
	
	// initialize tiles for computer and human
	// first initialize to blanks so the "getTiles" function works properly
	for( i=0; i< TILES_IN_HAND; i++)  {
		humanTiles[ i] = ' ';
		computerTiles[ i] = ' ';
	}
	// set end of string character
	humanTiles[ TILES_IN_HAND] = '\0';
	computerTiles[ TILES_IN_HAND] = '\0';
	
	getTiles( humanTiles, letters, tilesRemaining);
	getTiles( computerTiles, letters, tilesRemaining);
}


//--------------------------------------------------------------------------
void displayBoard( 	char board[ ][ BOARD_SIZE],	// the board
					char humanTiles[],			// human's tiles
					char computerTiles[],		// computer's tiles
					int humanScore,				// human's score
					int computerScore)			// computer's score
{
	int i,j;		// loop counters
	
	// display top header
	printf("\n  ");
	for (i=0; i< BOARD_SIZE; i++)  {
		printf("%d ", i + 1);
	}
	printf("\n");
		
	// display 2-D board with row #'s on left
	for (i=0; i< BOARD_SIZE; i++)  {
		printf("%c ", 'A'+i);
		for (j=0; j < BOARD_SIZE; j++)  {
			printf("%c ", board[ i][ j]);
		} 
		printf("\n");
	}
	
	printf("\n");
	// display human's and computer's tiles & scores
	printf("             Player             Computer\n");
	printf("   Tiles: ");
	for (i=0; i< TILES_IN_HAND; i++)  {
		printf("%c ", humanTiles[ i]);
	}
	printf("     ");
	for (i=0; i< TILES_IN_HAND; i++)  {
		printf("%c ", computerTiles[ i]);
	}
	printf("\n");
	printf("  Scores:       %d                  %d\n", humanScore, computerScore);
}


//--------------------------------------------------------------------------
int targetSquaresAreValid( 
			char theWord[],				// the word being checked
			char board[][ BOARD_SIZE], 	// the board
			int row,					// proposed row for the word
			int column,					// proposed column for the word
			char direction,				// 'A' for across or 'D' for down
			char warningMessage[])		// Possibly stores a warning message
/* Verify that target squares are valid.  Ensure that target squares do
	not go off edge of board, and do not already contain letters.
 */
{
	int rowOffset, columnOffset; 	// used to know how to change subscripts
	int wordLength;					// length of theWord
	int i;						// loop counters

	
	wordLength = strlen( theWord);  // compute the length of the word
	
	// Initialize and set offsets
	rowOffset=columnOffset=0;
	if ( direction == 'A')  {
		columnOffset = 1;
	}
	else if (direction == 'D')  {
		rowOffset = 1;
	} 
	else  {
		// Sanity check
		sprintf( warningMessage, "*** Direction was %c, not 'A' or 'D'.", direction); 
		error( warningMessage, TERMINATE, DO_NOT_CLEAR_SCREEN); 
	}	
	
	// Now verify that target squares are on board and are blank
	for (i=0; i< wordLength; i++)  {
		if ( (row >= BOARD_SIZE) || (column >= BOARD_SIZE) )  {
			// Out of bounds, no good
			sprintf( warningMessage, "Word goes out of bounds, retry."); 
			return FALSE;
		}
		if ( board[ row][ column] != '.')  {
			sprintf( warningMessage, "Destination not blank, retry."); 
			return FALSE;		// square not blank (actually '.'), invalid move
		}
		// Only one of the following will actually change value
		row += rowOffset;
		column += columnOffset;
	}
	
	// Passed all tests, so squares must be valid
	return TRUE;
}


//--------------------------------------------------------------------------
int validHumanMove( 	
				int row, 						// board row for word
				int column, 					// board column for word
				char direction,					// direction 'D' or 'A'
				char theWord[], 				// the actual word
				char playerTiles[], 			// player's tiles
				char board[][ BOARD_SIZE], 		// the board
				char dictionary[][ MAXLENGTH],	// dictionary 
				int numberOfDictionaryWords,	// # words in dictionary
				int tilesRemaining)				// # of tiles remaining to use
				
/* Verify that the word is found in the dictionary and destination squares
	are valid, and human has those tiles to play.  This verifies the human's moves.
 */
{
	char errorLine[ LINE_LENGTH];	// used to display error messages
	char userTilesCopy[ LINE_LENGTH];	// copy of tiles in user's hand.
										// This is used to verify tiles in proposed
										//    word are actually in user's hand.
	int wordLength;					// length of proposed word
	int i,j;						// loop counters
	int startPosition;	   /* position to start checking a words
							  letters to verify they are in user's hand.  This
							  is 0 for the first word, but 1 for subsequent words
							  since the first letter for those words should already
							  be on the board and not in the users hand.
							*/

	// if 'H' for help was selected (and there was no valid column value specified)
	if ( ( row == 'H') && (column == 0))  {
		return FALSE;
	}
	// if 'P' for pass was selected (and there was no valid column value specified)
	if ( ( row == 'P') && (column == 0))  {
		return FALSE;
	}
	
	if ( ! foundInDictionary( theWord, dictionary, numberOfDictionaryWords) )  {
		sprintf( errorLine, "Word not found in dictionary, retry."); 
		error( errorLine, WARNING, CLEAR_SCREEN); 
		return FALSE;
	}

	// Make sure player has those tiles to play
	// 
	wordLength = strlen( theWord);  // compute the length of proposed word
	// computer starting position to start checking for letter tiles
	if ( tilesRemaining < (NUMBER_OF_LETTERS - (TILES_IN_HAND*2))  )  {
		// Is NOT the first move; first character will not be checked
		startPosition = 1;		// skip checking the first letter
	}
	else  {
		// IS the first move; first character will be checked 
		startPosition = 0;		// check all letters
	}

	// ensure player has the tiles necessary for the word
	strcpy( userTilesCopy, playerTiles);	// make a copy so we can blank it out
	//   for each letter in the proposed word...
	for (i=startPosition; i< wordLength; i++)  {	
		// clear each letter tile to be played from copy of user's hand
		for (j=0; j< TILES_IN_HAND; j++)  {
			if ( theWord[ i] == userTilesCopy[ j])  {
				userTilesCopy[ j] = ' ';	// blank out that letter
				break;			// Found it. Go to next letter in outer loop
			}
		}
		if( j == TILES_IN_HAND)  {
			// This should only happen if human user is trying to play tiles
			// that are not in the human's hand
			sprintf( errorLine, "You are trying to play a letter not in your hand."); 
			error( errorLine, WARNING, CLEAR_SCREEN); 
			return FALSE;
		}	
	}

	
	/* Ensure target squares are valid.  If it is the first move, 
	 	 the word can start anywhere.  If it is not the first move,
	 	 the first letter of the proposed word must also already be
	 	 found on the board at the proposed playing position.
	 */
	// To find out if it is the first move we must
	//   compare against the formula below because the initialize() function
	//   has already given each player tiles to start out
	if ( tilesRemaining < (NUMBER_OF_LETTERS - (TILES_IN_HAND*2))  )  {
		// Is NOT the first move
		
		// first verify that first letter of word to play is the same
		// as the letter stored on the board at the playing position
		if ( board[ row][ column] != theWord[ 0])  {
			// First letter doesn't match, word can't be played there
			sprintf (errorLine,"First letter doesn't match. Can't do that.");
			error( errorLine, WARNING, DO_NOT_CLEAR_SCREEN); 
			return FALSE;			
		}
		
		/* We now know that the first letter matches. Skip the first letter
		  		of the word to check as well as the first character on the
		  		board when verifying that target squares are valid.		
		 */
		if ( direction == 'A') {
			// word is proposed to go across
			if ( ! targetSquaresAreValid( theWord + 1, board, row,  
									      column+1, direction, errorLine ) ) {
				error( errorLine, WARNING, DO_NOT_CLEAR_SCREEN); 
				return FALSE;						       
			}
		}
		else if ( direction == 'D')  {
			// word is proposed to go down
			if ( ! targetSquaresAreValid( theWord + 1, board, row+1,  
									      column, direction, errorLine ) ) {
				error( errorLine, WARNING, DO_NOT_CLEAR_SCREEN); 
				return FALSE;						       
			}
		
		} else  {
			// Sanity check
			sprintf( errorLine, "%s", "Invalid direction for word.");
			error( errorLine, TERMINATE, CLEAR_SCREEN); 						       
		}
	} // end if (tilesRemaining...
	else  {
		// IS the first move
		if ( ! targetSquaresAreValid( theWord, board, row,  
									  column, direction, errorLine ) )  {
			// display the error which was found in above function call
			error( errorLine, WARNING, DO_NOT_CLEAR_SCREEN); 
			// target squares were not valid
			return FALSE;
		}	
	}
	
	// all tests passed
	return TRUE;
}


//--------------------------------------------------------------------------
void makeMove( 	int row, 						// board row for word
				int column, 					// board column for word
				char direction,					// direction 'D' or 'A'
				char theWord[], 				// the actual word
				char playerTiles[], 			// player's tiles
				char board[][ BOARD_SIZE], 		// the board
				int tilesRemaining,				// overall tiles remaining
				int *score)						// score to be updated
/* Move has been verified, so place theWord on board at row,column using 
   direction to specify 'A' for across or 'D' for down.
 */
{
	int rowOffset, columnOffset; 	// used to know how to change subscripts
	int wordLength;					// length of theWord
	int i, j;						// loop counters
	int startPosition;	   /* position to start checking a words
							  letters to verify they are in user's hand.  This
							  is 0 for the first word, but 1 for subsequent words
							  since the first letter for those words should already
							  be on the board and not in the users hand.
							*/
	
	wordLength = strlen( theWord);  // compute the length of the word
	
	*score += wordLength;	// update score, 1 point per character
	
	// Initialize and set offsets
	rowOffset=columnOffset=0;
	if ( direction == 'A')  {
		columnOffset = 1;
	}
	else if (direction == 'D')  {
		rowOffset = 1;
	} 
	else  {
		// Sanity check
		printf("*** Direction was %c, not 'A' or 'D'. Exiting..\n", direction);
		fflush( stdout);
		exit( -1);
	}
	
	// Now store word at that location.  First figure out whether the first
	// 	 letter should be taken into account or not.
	//
	// Find computer starting position to start checking for letter tiles
	if ( tilesRemaining < (NUMBER_OF_LETTERS - (TILES_IN_HAND*2))  )  {
		// Is NOT the first move; first character will not be checked
		startPosition = 1;		// skip checking the first letter
	}
	else  {
		// IS the first move; first character will be checked 
		startPosition = 0;		// check all letters
	}

	for (i=0; i< wordLength; i++)  {
		board[ row][ column] = theWord[ i];
		// Only one of the following will actually change value
		row += rowOffset;
		column += columnOffset;
	}
	// Now reset row & column values to beginning of the word
	// This is used to verify that a square on the board is part
	// of the chosen word.
	for (i=0; i< wordLength; i++)  {
		// Only one of the following will actually change value
		row -= rowOffset;
		column -= columnOffset;
	}
	
	// clear those tiles to make space for new ones
	for (i=startPosition; i< wordLength; i++)  {
		// clear each letter tile played from user's hand
		for (j=0; j< TILES_IN_HAND; j++)  {
			if ( theWord[ i] == playerTiles[ j])  {
				playerTiles[ j] = ' ';		// blank it out, it's been used
				break;						// go to next letter in outer loop
			}
		}
		if( j == TILES_IN_HAND)  {
			// j == TILES_IN_HAND should only be true when no match was
			//		found in the above loop
			// Sanity check.  If letters matched, should never get here
			printf("*** Letters played not found in users hand.\n");
			printf("Error occured in word %s looking for letter %c\n",
					theWord, theWord[ i]);
			printf("Exiting program...\n");   fflush(stdout);
			exit ( -1);		
		}	
	}
}


//--------------------------------------------------------------------------
void humanMove( char board[ ][ BOARD_SIZE],	// the board
				int *notDone,				// stores when user wants to exit
				char humanTiles[],			// human's tiles
				char computerTiles[],			// computer's tiles
				char dictionary[][ MAXLENGTH],	// dictionary
				int numberOfDictionaryWords,	// # words in dictionary
				char letters[],				// tiles remaining
				int *tilesRemaining,			// # of tiles remaining
				int *humanScore,			// human's score
				int computerScore)			// computer's score
{
	char userInput[ 80];	// temporarily store input line
	int i;					// loop counter
	char row;				// board row for word to be put
	int column;				// board column for word to be put
	char direction;			// direction: 'A' for across, or 'D' for down
	char theWord[ LINE_LENGTH];	// stores the word to be put on the board
	char errorLine[ LINE_LENGTH];	// used to display error messages

	
	do {		
		printf("\n");
		printf("Enter row, column, move direction (a or d), and word.\n");
		printf("You may also enter 'P' to pass, 'X' to exit or 'H' for help. --> "); 
		 
		// Get an input line
		fgets(userInput, LINE_LENGTH, stdin);	
		// ensure it is upper case
		for (i=0; i< strlen( userInput); i++)  {
			if ( islower( userInput[ i]))  {
				userInput[ i] = toupper( userInput[ i]);
			}
		}
		
		// Parse input line
		column = 0;		// this is needed to differentiate between help & row 'H'
		sscanf( userInput, "%c%d %c %s", &row, &column, &direction, theWord);
		// prematurely exit if 'x' was entered
		if (row == 'X')  {
			*notDone = FALSE;
			return;
		}
		// If 'H' was entered for help, but no column info was entered
		if ( (row == 'H') && ( column == 0) )  {
			help();		// Display help information
			displayBoard( board, humanTiles, computerTiles, 
						  *humanScore, computerScore);
			continue;
		}
		if (row == 'P')  {
			// 'P' to pass this turn was chosen.  Return from this function.
			if ( *tilesRemaining == (NUMBER_OF_LETTERS - (TILES_IN_HAND*2))  )  {
				// IS the first move; disallow passing on this turn.  Human
				// must enter first word, otherwise computer has no letters
				// with which to start its words.
				sprintf( errorLine, "%s", "Can't pass on your first turn.");
				error( errorLine, WARNING, DO_NOT_CLEAR_SCREEN); 
				continue;	
			}	
			else  {
				return;
			}			
		}
		
		row -= 'A';		// convert lower case character row values to numbers
		column -= 1;	// Fix index, since column #'s start at 1, not 0
		
	} while ( ! validHumanMove( row, column, direction,theWord, humanTiles,
						   		board, dictionary, numberOfDictionaryWords,
						   		*tilesRemaining) 
			);
			
	// Move must have been valid to get here
	makeMove( row, column, direction, theWord, humanTiles, 
			  board, *tilesRemaining, humanScore);
	getTiles( humanTiles, letters, tilesRemaining);
}


//--------------------------------------------------------------------------
void swap( char theString[], int i, int j) 
{
	int temp = theString[ i];
	
	theString[ i] = theString[ j];
	theString[ j] = temp;
}


//--------------------------------------------------------------------------
int thisIsBestWord( char answer[],		// Current word being checked
					char bestWord[],	// Best word found so far
					int currentRow,		// Current starting position row
					int currentColumn,	// Current starting position column
					char *theDirection,	// Direction for best word
			  		char board[ ][ BOARD_SIZE])	 	// the board.  
/* See if this is the best word found so far.  For a word to be the best,
	it must have a higher or equal point score to any other word, and the word
	must fit into that position on the board.  In order to even call this
	function we know that the first character of the word matched a starting
	position on the board.
 */					
{
	char errorMessage[ LINE_LENGTH] = {" "};	// for error messages
	
	// Check point score
	if ( strlen( bestWord) >= strlen( answer) )  {
		// length is no longer than current best word, so simply return
		return FALSE;
	}
	
	// If there is not a valid move across or a move down, return
	//
	// find out the direction of the valid move
	*theDirection = ' ';
	/* set theDirection if a valid move is found.  
	   Increment answer to start checking for valid squares
	   *after* the first character, which is the same character
	   as the first character stored on the board.  For the same
	   reason also increment either row or column.
	 */ 
	// check for valid move going Across ('A') 
	if ( targetSquaresAreValid( answer+1, board, currentRow,  
								currentColumn+1,'A', errorMessage) ) {
		*theDirection = 'A';
		return TRUE;							
	}
	// check for valid move going Down ('D') 
	if ( targetSquaresAreValid( answer+1, board, currentRow+1,  
								currentColumn,'D', errorMessage) ) {
		*theDirection = 'D';							
		return TRUE;
	}
						
	// Target squares not valid.  Error message should have been generated
	return FALSE;
}


//--------------------------------------------------------------------------
void permute( char theString[], 	// current string
			  char answer[], 		// constructed using 1st. char of string
			  						//    at each recursive level
			  int position, 		// spot in answer where we're currently
			  						//    storing the next character
			  int maxDepth,			// used to limit recursive depths and
			  						//    generate answers of different lengths
			  char dictionary[][ MAXLENGTH],	// dictionary
			  int numberOfDictionaryWords,	// # words in dictionary
			  char bestWord[],				// stores best word found
			  int *bestRow,					// Store row for bestWord
			  int *bestColumn,				// Store column for bestWord
			  char *bestDirection,			// Direction for best word
			  char board[ ][ BOARD_SIZE])	// the board.  Used to pass
			  								//    along to verify if a
			  								//	  found word is the best.
{
	int length;			// stores string length of permutation being checked
	int i;				// loop counter
	int row, column;	// row & column indices for traversing board
	char theDirection;	// Used to store direction if a new best word is found
	char wordToLookup[ LINE_LENGTH] = {" "};
	
	length = strlen( theString);
					
	if (length == maxDepth)  {
		// construct word to lookup by appending permutation to a character alreay
		// on the board.  To do this, go through each character on board and make
		// it the first character of the word to check.
		for (row=0; row< BOARD_SIZE; row++)  {
			for (column=0; column< BOARD_SIZE; column++)  {
				// make sure there is a character there
				if ( board[ row][ column] == '.')  {
					// no character there
					continue;
				}

				// Construct the word to lookup
				wordToLookup[ 0] = board[ row][ column];	// store first character for word
				// variable "answer" has blanks on the end of it, so we don't want to copy those
				// Find the number of chacters until we get to the first blank.
				for (i=0; (answer[i]!= ' ') && (answer[i]!= NULL); i++)  {
					wordToLookup[ i+1] = answer[ i];	// offset destination 'cause of link letter
				}
				wordToLookup[ i + 1] = NULL;	// Properly terminate destination string
								
				if ( foundInDictionary( wordToLookup, dictionary, numberOfDictionaryWords)) {
					// See if we've found a new best word. 
					if ( thisIsBestWord( wordToLookup, bestWord, row,  
						                 column, &theDirection, board) )  {
						strcpy( bestWord, wordToLookup);	// store new best word
						*bestRow = row;				// store best row & column
						*bestColumn = column;
						*bestDirection = theDirection;	// store direction for best word		
					}
				}
			} // end for (column...
		} // end for (row...
		
		return;
	} // end if (length == maxDepth)


	// For each starting character
	for (i=0; i< length; i++)  {
		swap( theString, 0, i);		// swap items
		answer[ position] = theString[ 0];
		
		// recursive call without first letter
		permute( &(theString[ 1]), answer, position+1, maxDepth, 
				 dictionary, numberOfDictionaryWords, 
				 bestWord, bestRow, bestColumn, bestDirection, board);	
		
		swap( theString, 0, i);		// swap items back to original position
	}
}

//--------------------------------------------------------------------------
void computerMove(  char board[ ][ BOARD_SIZE],	// the board
					char computerTiles[],		// computer's tiles
					char dictionary[][ MAXLENGTH],	// dictionary
					int numberOfDictionaryWords,	// # words in dictionary
					char letters[],				// tiles remaining
					int *tilesRemaining,			// # of tiles remaining
					int *computerScore)				// computer's score
{
	char permutedWord[ TILES_IN_HAND + 1];	// permuted word, + 1 for NULL
	int i, row, column;				// loop counters
	int maxDepth;			// used for generating different size strings
	char bestWord[ TILES_IN_HAND + 2] = {""};	// best word found
	int bestRow, bestColumn;	// location for best word
	char bestDirection;			// direction 'A' or 'D' for best word


	// By varying the maximum recursive call depth, we create strings of 
	// different lengths.  I.e. when max depth is 0, recursive calls are made
	// until all characters in the string are exhausted.  When MAX-1 is the
	// max. depth, then recursion ends right away giving strings of length
	// one only.		
	for ( maxDepth = 0; maxDepth < TILES_IN_HAND + 1; maxDepth++)  {
		// blank out initial permuted word
		for (i=0; i< TILES_IN_HAND; i++)  {
			permutedWord[ i] = ' ';		
		}
		permutedWord[ TILES_IN_HAND] = '\0';	// mark end of string
		// Generate permutations, look them up in dictionary,
		// and get "best" word that fits into board
		permute( computerTiles, permutedWord, 0, maxDepth,
				 dictionary, numberOfDictionaryWords, 
				 bestWord, &bestRow, &bestColumn, &bestDirection, board);	
	}		

	printf("\nBest computer word found was: %s, ", bestWord);
	printf("played %s ", (bestDirection == 'A') ? "across" : "down");
	printf("starting at %c%d", bestRow+'A', bestColumn+1);

	
	// Move must have been valid to get here
	makeMove( bestRow, bestColumn, bestDirection, bestWord, 
		      computerTiles, board, *tilesRemaining, computerScore);
	getTiles( computerTiles, letters, tilesRemaining);

}


//--------------------------------------------------------------------------
void main()
{
	// Set all file names here in one place to make it easier to change
	//		later if needed.  Pass the names to functions where needed.
	char dictionaryFileName[] = {"words"};		// dictionary file name
	char lettersFileName[] = {"letters.txt"};	// scrabble letters file name
	
	char dictionary[ ROWS][MAXLENGTH];	// 2-D array used to store dictionary 
										//		words.
	int numberOfDictionaryWords;		// Number of Dictionary words
	char board[ BOARD_SIZE][ BOARD_SIZE]; 	// the scrabble board
	int notDone = TRUE;					// Flag to indicate when we're done
	char letters[ NUMBER_OF_LETTERS];	// Stores scrabble letter tiles
	char computerTiles[ TILES_IN_HAND + 2];	// computer's letters
			// Extra space needed to add in a character from the board
	char humanTiles[ TILES_IN_HAND + 2];	// human's letters
	int tilesRemaining = NUMBER_OF_LETTERS;	// tiles left for anyone to use
	int humanScore = 0;						// human score
	int computerScore = 0;					// computer score

	// Read dictionary words into dictionary array
	getDictionaryWords( dictionary, dictionaryFileName, 
						&numberOfDictionaryWords);
	
	// Initialize board to '.', initialize letters array to the letters 
	// 		from file, Give human and computer their starting letters
	initialize( board, letters, lettersFileName,
				computerTiles, humanTiles, &tilesRemaining);
				
	// display help information for first time through
	help();
	
	// main loop	
	do {
		
		// Display board
		displayBoard( board, humanTiles, computerTiles, humanScore, computerScore);

		// Prompt for input and make human's move, get new tiles
		humanMove( board, &notDone, humanTiles, computerTiles, dictionary, 
				   numberOfDictionaryWords, letters, &tilesRemaining, 
				   &humanScore, computerScore);
		
		if ( notDone)  {
			// if human has not indicated being done yet
			// Determine computers move, get new tiles
			computerMove( board, computerTiles, dictionary, numberOfDictionaryWords, 
				   	      letters, &tilesRemaining, &computerScore);
		}


		
	} while ( notDone);
	
	printf("Thanks for playing.\n");
}