/*****************************
* CornerTheQueen - A simple, *
* two-person game for one    *
* human and one computer     *
* (c)1999 Oliver Kreylos     *
*****************************/

#include <math.h>
#include <stdio.h>

/***************************************************************
We define a structure to hold the queen's position on the board:
***************************************************************/

typedef struct _Position
	{
	int x; // Horizontal coordinate, from 1 to boardSize
	int y; // Vertical coordinate, from 1 to boardSize
	} Position;

/****************************************************
Display the main menu and ask for user's menu choice:
****************************************************/

int queryMainMenu(int boardSize)
	{
	int userChoice;
	int validResponse;
	
	/* Display menu: */
	printf("\"Corner the Queen\"\n\n");
	printf("Main menu\n\n");
	printf("The current board size is %dx%d\n\n",boardSize,boardSize);
	printf("Available options:\n");
	printf("  1 - Change board size\n");
	printf("  2 - Play a game\n");
	printf("  3 - Quit the program\n");
	printf("\nYour choice: ");
	/* Ask for user's response until user makes valid choice: */
	do
		{
		scanf("%d",&userChoice);
		validResponse=userChoice>=1&&userChoice<=3;
		if(!validResponse)
			printf("Invalid option. Please choose another menu option: ");
		}
	while(!validResponse);
	/* Return choice to calling function: */
	return userChoice;
	}

/*******************************
Ask user for the new board size:
*******************************/

int changeBoardSize(int boardSize)
	{
	int responseValid;
	
	printf("The current board size is %dx%d\n",boardSize,boardSize);
	printf("Please enter the new board width: ");
	/* Ask for new board width, until user enters something reasonable: */
	do
		{
		scanf("%d",&boardSize);
		responseValid=boardSize>0;
		if(!responseValid)
			printf("Invalid board width. Please enter another board width: ");
		}
	while(!responseValid);
	/* Return new board size to calling function: */
	return boardSize;
	}

/********************************************************
Let the user position the queen on a board of given size:
********************************************************/

Position getInitialPosition(int boardSize)
	{
	Position initial;
	int validResponse;
	
	printf("Please enter the queen's initial position (x y): ");
	/* Ask for initial position, until user enters valid position: */
	do
		{
		scanf("%d %d",&initial.x,&initial.y);
		validResponse=initial.x>=1&&initial.x<=boardSize&&initial.y>=1&&initial.y<=boardSize;
		if(!validResponse)
			printf("Invalid position. Please enter another position (x y): ");
		}
	while(!validResponse);
	/* Return queen's position to calling function: */
	return initial;
	}

/******************************************************
Check if the queen is located in the lower left corner:
******************************************************/

int isLowerLeftCorner(Position p)
	{
	return p.x==1&&p.y==1;
	}

/************************
Check if a move is legal:
************************/

int isMoveLegal(Position old,Position new)
	{
	int legal;
	
	/* Check which kind of move we're dealing with: */
	if(old.y==new.y) /* Horizontal move */
		legal=new.x>=1&&new.x<old.x;
	else if(old.x==new.x) /* Vertical move */
		legal=new.y>=1&&new.y<old.y;
	else if(new.x-old.x==new.y-old.y) /* Diagonal move */
		legal=new.x>=1&&new.y>=1&&new.x<old.x;
	else /* Some other move */
		legal=0;
	/* Return result to calling function: */
	return legal;
	}

/*************************************************
Mirror a position about the board's main diagonal:
*************************************************/

Position mirrorPosition(Position current)
	{
	Position new;
	
	/* Swap x and y coordinates: */
	new.x=current.y;
	new.y=current.x;
	/* Return mirrored position to calling function: */
	return new;
	}

/*************************************************
Calculate the winning position with a given index:
*************************************************/

Position calculateWinningPosition(int index)
	{
	int realIndex;
	double goldenRatio;
	Position winner;
	
	/* Since each winning position comes in two flavors, we generate
	   the "lower" one for even values of index, and the "upper" one
	   for odd values. This makes the rest of the program somewhat simpler,
	   which justifies this "hack." */
	realIndex=index/2;
	/* Create the "lower" position: */
	goldenRatio=0.5*(sqrt(5.0)+1.0);
	winner.y=1+(int)floor(goldenRatio*(double)realIndex);
	winner.x=winner.y+realIndex;
	/* Now, if index is odd, mirror the position to get the "upper" one: */
	if(index%2==1)
		winner=mirrorPosition(winner);
	/* Return the winning position to calling function: */
	return winner;
	}

/*******************************
Test if two positions are equal:
*******************************/

int arePositionsEqual(Position pos1,Position pos2)
	{
	return pos1.x==pos2.x&&pos1.y==pos2.y;
	}

/*********************************
Calculate a very intelligent move:
*********************************/

Position calculateComputerMove(Position current)
	{
	Position new;
	int index;
	int positionFound;
	
	/* Strategy: Find the first "winning position" we can reach. There are
	   two cases: Either we can reach a winning position, or we already are
	   on a winning position (for the other player). In the former case, we
	   will win the game; in the latter case, the user might win. */
	positionFound=0;   
	for(index=0;!positionFound;++index)
		{
		/* Calculate the next winning position: */
		new=calculateWinningPosition(index);
		if(arePositionsEqual(current,new)) /* We are at the position - we lost. */
			{
			/* We generate some move and hope that the user will screw up: */
			if(new.x>=new.y)
				--new.x;
			else
				--new.y;
			positionFound=1;
			}
		else if(isMoveLegal(current,new)) /* We can reach that position! */
			positionFound=1;
		/* Position can't be reached, we have to try the next one */
		}
	/* Return the found position to the calling function: */
	return new;
	}

/********************
Read the user's move:
********************/

Position getUserMove(Position current)
	{
	Position new;
	int validResponse;
	
	printf("Please enter the queen's new position (x y): ");
	do
		{
		scanf("%d %d",&new.x,&new.y);
		/* Check if the move is valid: */
		validResponse=isMoveLegal(current,new);
		if(!validResponse)
			printf("Invalid move. Please choose another new position (x y): ");
		}
	while(!validResponse);
	/* Return new position to calling function: */
	return new;
	}

/********************************************
Play the game on a board of the current size:
********************************************/

void playGame(int boardSize)
	{
	Position current; /* Current position of the queen on the board */
	int winningPlayer; /* Flag to keep track of who has won the game */
	
	/* Let the user begin the game by positioning the queen on the board: */
	current=getInitialPosition(boardSize);
	/* We assume that the user will win the game: */
	winningPlayer=1;
	/* Let players move the queen in turns, until one wins: */
	while(!isLowerLeftCorner(current))
		{
		/* Let the computer make a (hopefully) winning move: */
		current=calculateComputerMove(current);
		/* Print the computer's move: */
		printf("I moved the queen to position %d %d.\n",current.x,current.y);
		if(isLowerLeftCorner(current))
			winningPlayer=2;
		else
			{
			/* Let the user make a (hopefully) stupid move: */
			current=getUserMove(current);
			}
		}
	/* Tell the user who has won the game: */
	if(winningPlayer==1)
		{
		printf("#################\n");
		printf("# You have won! #\n");
		printf("#################\n");
		}
	else
		{
		printf("***************\n");
		printf("* I have won! *\n");
		printf("***************\n");
		}
	}

int main(void)
	{
	int boardSize;
	int userChoice;
	
	/* Start out with a standard chess board: */
	boardSize=8;
	/* Repeatedly show the main menu and ask user's
	   response, until user wants to quit: */
	do
		{
		userChoice=queryMainMenu(boardSize);
		switch(userChoice)
			{
			case 1:
				boardSize=changeBoardSize(boardSize);
				break;
			case 2:
				playGame(boardSize);
				break;
			case 3:
				printf("Good bye, and thanks for playing!\n");
				break;
			}
		}
	while(userChoice!=3);
	return 0;
	}