#include "board.h"
#include "conio.h"
#include <windows.h>
#include <iomanip>
#include <vector>

void gameBoard::setInitialPosition(position p)
{
	knightPosition=p;
}
void gameBoard::setInitialPosition(int r, int c)
{
	knightPosition.x=c;
	knightPosition.y=r;
}

void gameBoard::setInitialPosition()
{
	char choice=NULL;

	position newKnightPos=knightPosition;
	displayBoard();
	cout << "Use arrow keys to select initial position, enter to accept.";

	do
	{	
		choice=_getch();
		if ( choice == -32 )
		{
			char key;
			key=_getch();
			if ( key == 72 )
			{	// up
				newKnightPos.y = knightPosition.y-1;
				if ( newKnightPos.y < 0 ) { newKnightPos.y=boardSize-1; }
			} else if ( key == 80 )
			{	// down
				newKnightPos.y = knightPosition.y+1;
				if ( newKnightPos.y >= boardSize ) { newKnightPos.y=0; }
			} else if ( key == 75 )
			{	// left
				newKnightPos.x = knightPosition.x-1;
				if ( newKnightPos.x < 0 ) { newKnightPos.x=boardSize-1; }
			} else if ( key == 77 )
			{	// right
				newKnightPos.x = knightPosition.x+1;
				if ( newKnightPos.x >= boardSize ) { newKnightPos.x=0; }
			}
			// clear the current square
			setScreenPos(knightPosition);
			cout << setw(3) << "";
			// move the knight
			knightPosition=newKnightPos;
			// display the knight
			setScreenPos(knightPosition);
			cout << " K ";
		}
	} while ( choice != 13 );
}

gameBoard::gameBoard(int size)
{
	// set up the board
	boardSize=size;
	visitedSquares=0;
	assert ( boardSize > 0 );
	board=new square*[boardSize];
	for ( int r=0; r < boardSize; r++ )
	{
		board[r]=new square[boardSize];
	}
	knightPosition.x=0;
	knightPosition.y=0;
}
gameBoard::gameBoard(gameBoard &g, int moveNum)
{
	// copy
	boardSize=g.boardSize;
	visitedSquares=g.visitedSquares;
	knightPosition=g.knightPosition;

	board=new square*[boardSize];
	for ( int r=0; r < boardSize; r++ )
	{
		board[r]=new square[boardSize];
		for ( int c=0; c < boardSize; c++ )
		{
			board[r][c]=g.board[r][c];
		}
	}

	// mark current position as visited
	board[knightPosition.y][knightPosition.x].visited=true;
	board[knightPosition.y][knightPosition.x].moveNum=moveNum;
	visitedSquares++;
}

gameBoard gameBoard::operator =(const gameBoard &g)
{
	knightPosition=g.knightPosition;
	visitedSquares=g.visitedSquares;

	if ( this != &g )
	{
		for ( int r=0; r < boardSize; r++ )
			delete [] board[r];
		delete [] board;
		
		boardSize=g.boardSize;
		visitedSquares=g.visitedSquares;
		
		board=new square*[boardSize];
		for ( int r=0; r < boardSize; r++ )
		{
			board[r]=new square[boardSize];
			for ( int c=0; c < boardSize; c++ )
			{
				board[r][c]=g.board[r][c];
			}
		}
	}
	return *this;
}

gameBoard::~gameBoard()
{
	for ( int r=0; r < boardSize; r++ )
		delete [] board[r];
	delete [] board;
}

void gameBoard::displayBoard(int hlstep)
{
	system("cls");

	setColor(15);

	// print top border
	cout << char(201); // ╔
	for ( int i=0; i < boardSize; i++ )
	{
		cout << char(205) << char(205) << char(205); // ═
		if ( i < boardSize-1 ) 
			cout << char(209); // ╤
		else
			cout << char(187); // ╗
	}
	cout << endl;

	for ( int r=0; r < boardSize; r++ )
	{	// print each row
		for ( int c=0; c < boardSize; c++ )
		{   // print each column
			if ( c == 0 ) 
				cout << char(186) << setw(3) ; // ║
			else
				cout << char(179) << setw(3) ; // │

			if ( board[r][c].visited ) {
				
				if ( board[r][c].moveNum == hlstep ) setColor(42);	// highlight
				cout << board[r][c].moveNum; // display move #
				if ( board[r][c].moveNum == hlstep ) setColor(15);	// return to default

			} else if ( r == knightPosition.y && c == knightPosition.x ) { 
				cout << " K "; 
			} else {
				cout << "   ";
			}
			if ( c == boardSize-1 ) 
				cout << char(186); // ║
		}
		
		if ( r < boardSize-1 ) 
		{	// display border between rows
			cout << endl;
			cout << char(199); // ╟
			for ( int i=0; i < boardSize; i++ )
			{
				cout << char(196) << char(196) << char(196); // ─
				if ( i < boardSize-1 ) 
					cout << char(197); // ┼
				else
					cout << char(182); // ╢
			}
			cout << endl;
		}  // end display border between rows
	} // end for each row

	// display bottom border
	cout << endl;
	cout << char(200); // ╚
	for ( int i=0; i < boardSize; i++ )
	{
		cout << char(205) << char(205) << char(205); // ═
		if ( i < boardSize-1 ) 
			cout << char(207); // ╧
		else
			cout << char(188); // ╝
	}
	cout << endl;
		
}

void gameBoard::stepThroughSolution()
{
	char choice=NULL;
	int step=1;



	do {
		displayBoard(step);
		cout << "Arrow left & right to highlight step, Q to quit stepthrough.\n";

		choice=_getch();
		choice=toupper(choice);
		if ( choice == -32 ) {
			char key=_getch();
			if ( key == 75 )
			{ // left
				step--;
				if ( step < 1 ) step=1;
			} else if ( key == 77 )
			{ // right
				step++;
				if ( step > boardSize*boardSize) step=boardSize*boardSize;
			}
		}
		
	} while ( choice != 'Q' );
}


void gameBoard::setColor(int color)
{
	HANDLE hConsole;
	hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleTextAttribute(hConsole,color);
}

bool gameBoard::solve(position startPos, int moveNum, bool showProgress, bool bruteForce)
{

	// move the knight into this square.
	moveNum++;
	visitedSquares++;
	board[startPos.y][startPos.x].visited=true;
	board[startPos.y][startPos.x].moveNum=moveNum;
	knightPosition=startPos;
	if ( showProgress )
	{
		setScreenPos(startPos);
		cout << setw(3) << moveNum;
	}

	position originalKnightPos=startPos; // make a note of where he moved from so that he can go back if this is a dead end

	if ( visitedSquares == boardSize*boardSize )
	{	// every square has been visited, the solution has been found
		return true;
	}
	else
	{	// from here there are (up to) 8 possible moves, try each until a solution is found
		position testPoint[8];
		testPoint[7].x=startPos.x-2;		testPoint[7].y=startPos.y-1;
		testPoint[6].x=startPos.x-1;		testPoint[6].y=startPos.y-2;
		testPoint[5].x=startPos.x+1;		testPoint[5].y=startPos.y-2;
		testPoint[4].x=startPos.x+2;		testPoint[4].y=startPos.y-1;
		testPoint[3].x=startPos.x-2;		testPoint[3].y=startPos.y+1;
		testPoint[2].x=startPos.x-1;		testPoint[2].y=startPos.y+2;
		testPoint[1].x=startPos.x+2;		testPoint[1].y=startPos.y+1;
		testPoint[0].x=startPos.x+1;		testPoint[0].y=startPos.y+2;

		int bestPoint=-1;	int bestScore=(boardSize*boardSize)+1; // lowest # wins, assume worst
		int thisPossibleMoves;

		for ( int i=0; i < 8; i++ )
		{	// make sure the test point is on the board
			if ( testPoint[i].x >=0 && testPoint[i].x < boardSize && testPoint[i].y >=0 && testPoint[i].y < boardSize ) 
			{	// and hasn't been visited yet
				if ( !(board[testPoint[i].y][testPoint[i].x].visited) )
				{
					if ( bruteForce ) 
					{
						// brute force will always find a solution if one exists, but can be slow in certain situations.
						if ( solve(testPoint[i],moveNum,showProgress,bruteForce) ) return true;
					} else {
						// smart method is fast but not always successful.
						thisPossibleMoves=getPossibleMoves(testPoint[i]);
						if ( thisPossibleMoves < bestScore )
						{
							bestPoint=i;
							bestScore=thisPossibleMoves;
						} else if ( thisPossibleMoves == bestScore && bestPoint >= 0 )
						{
							int tieBreakResult=breakTie(testPoint[bestPoint],testPoint[i]);
							if ( tieBreakResult == 1 )
								bestPoint=i;
						}
					} // end brute force or not
				} // end if test point has not been visited
			} // end if test point is on board
		} // end for (each possible move) loop

		if ( !bruteForce )
		{
			if ( bestPoint >= 0 && bestScore > 0 )
			{
				if ( solve(testPoint[bestPoint],moveNum,showProgress) ) 
				{
					return true;
				} 
			} // end if bestPoint exists
		} // end if !brute force
	} // end if visited squares = total squares (or not)


	// this move was a dead end, undo everything and move back to the previous square
	startPos=originalKnightPos;
	board[startPos.y][startPos.x].visited=false;
	visitedSquares--;
	moveNum--;
	if ( showProgress )
	{
		setScreenPos(startPos);
		cout << setw(3) << "";
	}


	return false;
} // end solve

position gameBoard::getKnightPosition()
{	return knightPosition;
}

int gameBoard::getPossibleMoves(position fromPos)
{
	// returns the number of moves available from this spot (+1 for this spot itself) 
	int count=1;

	position testPoint[8];
	testPoint[7].x=fromPos.x-2;		testPoint[7].y=fromPos.y-1;
	testPoint[6].x=fromPos.x-1;		testPoint[6].y=fromPos.y-2;
	testPoint[5].x=fromPos.x+1;		testPoint[5].y=fromPos.y-2;
	testPoint[4].x=fromPos.x+2;		testPoint[4].y=fromPos.y-1;
	testPoint[3].x=fromPos.x-2;		testPoint[3].y=fromPos.y+1;
	testPoint[2].x=fromPos.x-1;		testPoint[2].y=fromPos.y+2;
	testPoint[1].x=fromPos.x+2;		testPoint[1].y=fromPos.y+1;
	testPoint[0].x=fromPos.x+1;		testPoint[0].y=fromPos.y+2;	
	for ( int i=0; i < 8; i++ )
	{	// make sure the test point is on the board
		if ( testPoint[i].x >=0 && testPoint[i].x < boardSize && testPoint[i].y >=0 && testPoint[i].y < boardSize ) 
		{	// and hasn't been visited yet
			if ( !(board[testPoint[i].y][testPoint[i].x].visited) )
				count++;
		}
	}
	return count;
}

int gameBoard::breakTie(position posA, position posB)
{
	// points A & B both have the same score (# of possible moves from those points)
	// which of those has the least # of sub-moves?
	// return values:
	// -1 tie could not be broken
	// 0 posA is best (fewest submoves)
	// 1 posB is best (fewest submoves)

	int count[2]={0};
	
	position testPoint[2][8];
	testPoint[0][7].x=posA.x-2;		testPoint[0][7].y=posA.y-1;
	testPoint[0][6].x=posA.x-1;		testPoint[0][6].y=posA.y-2;
	testPoint[0][5].x=posA.x+1;		testPoint[0][5].y=posA.y-2;
	testPoint[0][4].x=posA.x+2;		testPoint[0][4].y=posA.y-1;
	testPoint[0][3].x=posA.x-2;		testPoint[0][3].y=posA.y+1;
	testPoint[0][2].x=posA.x-1;		testPoint[0][2].y=posA.y+2;
	testPoint[0][1].x=posA.x+2;		testPoint[0][1].y=posA.y+1;
	testPoint[0][0].x=posA.x+1;		testPoint[0][0].y=posA.y+2;	

	testPoint[1][7].x=posB.x-2;		testPoint[1][7].y=posB.y-1;
	testPoint[1][6].x=posB.x-1;		testPoint[1][6].y=posB.y-2;
	testPoint[1][5].x=posB.x+1;		testPoint[1][5].y=posB.y-2;
	testPoint[1][4].x=posB.x+2;		testPoint[1][4].y=posB.y-1;
	testPoint[1][3].x=posB.x-2;		testPoint[1][3].y=posB.y+1;
	testPoint[1][2].x=posB.x-1;		testPoint[1][2].y=posB.y+2;
	testPoint[1][1].x=posB.x+2;		testPoint[1][1].y=posB.y+1;
	testPoint[1][0].x=posB.x+1;		testPoint[1][0].y=posB.y+2;	


	for ( int p=0; p < 2; p++ )
	{
		for ( int i=0; i < 8; i++ )
		{	// make sure the test point is on the board
			if ( testPoint[p][i].x >=0 && testPoint[p][i].x < boardSize && testPoint[p][i].y >=0 && testPoint[p][i].y < boardSize ) 
			{	// and hasn't been visited yet
				if ( !(board[testPoint[p][i].y][testPoint[p][i].x].visited) )
					count[p] += getPossibleMoves(testPoint[p][i]);
			}
		}
	}

	if ( count[0] > count[1] )
		return 0;
	else if ( count[0] < count[1] )
		return 1;
	else
		return -1;
}

void gameBoard::saveToFile(char filename[], double solveTime)
{
	ofstream outFile;
	outFile.open(filename);
	
	int numWidth=3;
	if ( boardSize*boardSize > 999 ) numWidth=4;
	if ( boardSize*boardSize > 9999) numWidth=5;

	if ( outFile ) 
	{
		
		// print top border
		outFile << "Knight's Tour " << boardSize << " x " << boardSize << " board, solved in " << solveTime << " seconds.\n";

		outFile << "+";
		for ( int i=0; i < boardSize; i++ )
		{
			for ( int j=0; j < numWidth; j++ ) 
				outFile << "=";
			outFile << "+";
		}
		outFile << endl;

		for ( int r=0; r < boardSize; r++ )
		{	// print each row
			for ( int c=0; c < boardSize; c++ )
			{   // print each column
				outFile << "|" << setw(numWidth);

				if ( board[r][c].visited ) {					
					outFile << board[r][c].moveNum; // display move #
				} else if ( r == knightPosition.y && c == knightPosition.x ) { 
					outFile << " K "; 
				} else {
					outFile << "   ";
				}
				if ( c == boardSize-1 ) 
					outFile << "|";
			}
			
			if ( r < boardSize-1 ) 
			{	// display border between rows
				outFile << endl;
				outFile << "+";
				for ( int i=0; i < boardSize; i++ )
				{
					for ( int j=0; j < numWidth; j++ ) 
						outFile << "-";
					outFile << "+";
				}
				outFile << endl;
			}  // end display border between rows
		} // end for each row

		// display bottom border
		outFile << endl;
		outFile << "+";
		for ( int i=0; i < boardSize; i++ )
		{
			for ( int j=0; j < numWidth; j++ ) 
				outFile << "=";
			outFile << "+";
		}
		outFile << endl;

	} else {
		cout << "\nFailed to save.\n";
	} 

	outFile.close();
}