/*
Mark Kolich
Ben Hildebrand
Adam Peterson
Wendy Pang
Nicole Yee

Started:  Tuesday, October 5, 1999
Finished: Thursday, October 7, 1999

AP Programming  --  The Knights Tour 1
Mr. Davis
*/

#include <dice.h>
#include <fstream.h>
#include <apmatrix.h>
#include <iomanip.h>
#include <stdio.h>
#include <conio.h>
#include <sys/timeb.h>
#include <time.h>

bool check(apmatrix<int> &, int, int);
void poss(int, int, int, int &, int &);
void move(apmatrix<int> &, int &, int &, int &);
void output(apmatrix<int> &, int);
void negative(apmatrix<int> &);
void outwhole(apmatrix<int>);
void clsr();

struct _timeb timebuffer;   
char *timeline;

int main()
{


	int most=0, moves=0, finalmoves=0;
	long int attempt = 1;
	char kontinue;

	do
	{

		apmatrix<int> final(12,12,0);

        
do{
        
    	int x = 2, y = 2;
        bool checks = false;

		apmatrix<int> board(12,12,0);
        
        
        negative(board);
        //outwhole(board);

        //cout << "Attempt # " << attempt << endl;
        moves=0;
        do
        {
                checks = check(board, x, y);
                if(checks)
                {		
                        move(board, x, y, moves);
                        checks = true;
                }

        }
        while(checks);


        attempt++;
	

	    if(most <= moves)
        {
			most = moves;
			clsr();
			cout << "    The Knights Tour" << endl;
			cout << "    [===================================================]" << endl << endl;	

			_ftime( &timebuffer );
			timeline = ctime( & ( timebuffer.time ) );
			cprintf("    Attempt #%d %s",attempt,"@ ");
			cprintf( "%.19s.%hu %s", timeline, timebuffer.millitm, &timeline[20]);

			cout << endl << endl;        	
        	output(board,--moves);
			cout << endl << "    Will Continue Execution of Loop Until Moves Is = To 64!" << endl;
		}
		final = board;
		finalmoves = most;
	}
	while(moves <= 63);


	clsr();
	cout << "    The Knights Tour" << endl;
	cout << "    [===================================================]" << endl << endl;	

	_ftime( &timebuffer );
	timeline = ctime( & ( timebuffer.time ) );
	cprintf("    Attempt #%d %s",attempt,"@ ");
	cprintf( "%.19s.%hu %s", timeline, timebuffer.millitm, &timeline[20]);

	cout << endl << endl;        	
    output(final,finalmoves);

	cout << endl << "    Continue (y or n)?: ";
	cin >> kontinue;
	}
	while(kontinue == 'Y' || kontinue == 'y');

	return 0;
}

 
void poss(int dice_roll, int x, int y, int & a, int & b)
/*
Adam Peterson:

Function that determines coordinates of the eight possibilities from the
current position of the knight.

Variable Explanations:
@  int dice_roll is the ramdom roll of the dice on which position to choose to go to
@  int x is the x coordinate of the current position of the knight
@  int y is the y coordinate of the current position of the knight
@  int &a is a reference int that determines the x coordinate of choice dice_roll
@  int &b is a reference int that determines the y coordinate of choice dice_roll
*/
{
        switch(dice_roll){ //switch for all the possilities coming from rolling dice_roll

        case 1: a = x + 1;      //position 1 is one to the right and two above current
                        b = y + 2;      //coordinates of knight
                        break;
        case 2: a = x + 2;      //position 2 is two to the right and one above current
                        b = y + 1;      //coordinates of knight
                        break;
        case 3: a = x + 2;      //position 3 is two to the right and one below current
                        b = y - 1;      //coordinates of knight
                        break;
        case 4: a = x + 1;      //position 4 is one to the right and two below current
                        b = y - 2;      //coordinates of knight
                        break;
        case 5: a = x - 1;      //position 5 is one to the left and two below current
                        b = y - 2;      //coordinates of knight
                        break;
        case 6: a = x - 2;      //position 6 is two to the left and one below current
                        b = y - 1;      //coordinates of knight
                        break;
        case 7: a = x - 2;      //position 7 is two to the left and one above current
                        b = y + 1;      //coordinates of knight
                        break;
        case 8: a = x - 1;      //position 8 is one to the left and two above current
                        b = y + 2;      //coordinates of knight
                        break;
        }//end switch
}//end poss


bool check(apmatrix<int> & board, int spotr, int spotc)
{
/*
Wendy Pang:
*/
        
        int x = 1; // random roll of the dice on which position to choose to go to
        bool in = false; // whether there is an open (0) spot
        int newr, newc; // where to check for open (0) spot

        do
        {
                poss(x,spotr,spotc,newr,newc);

                if (board[newr][newc] == 0)
                        in = true;
                        
                x++;
        } // tests if there is an open spot anywhere
        while(in == false && x <= 8);

        return in;
}


void output(apmatrix<int> & board, int counter)
{
        int row, column; // row and column of matrix
        int x; // counter variable

        cout<< setw(5)<<" ";

        for(x = 1; x <= 8; x++) // outputs row number
                cout << setw(5) << x << " ";
                

        cout << endl << endl;

        for(row = 2; row < 10; row++)
        {
                cout << setw(5) << row - 1; // outputs column number
                for(column = 2; column < 10; column++) // outputs matrix
                {
                        cout << setw(5) << board[row][column] << " ";
                }
                cout << endl;
        }

        cout << endl << "    Total Moves Made: " << counter<<endl; // outputs total moves made by knight
}

void move(apmatrix<int> & matrix, int & x,int & y, int & count)
{
        int numRoll = 0, a, b;
        bool changed=false;

        dice square(8);

do{
        a=0;
        b=0;
        numRoll=square.roll();
        poss(numRoll, x, y, a, b);
    
    if(matrix[a][b]==0)
        {
                matrix[a][b]=count;
            x=a; y=b;
            count++;
            changed=true;
        }
    }
    while(changed==false);

} // End of function

void negative(apmatrix<int> & board)
{
int x, y;
        for(x=0; x<=11; x++)
        {
                for(y=0; y<=11; y++)
                {
                if((x<=1)||(x>=10)||(y<=1)||(y>=10))
                        {
                        board[x][y]= (-1);
                        }
                }
        }
}


void outwhole(apmatrix<int> board)
{
        int x, y;

        for(x=0; x<11; x++)
        {
                for(y=0; y<11; y++)
                {
                cout<<board[y][x];
                }
        }
        cout<<endl;
}

void clsr()
{
        cout << endl << endl << endl << endl;
        cout << endl << endl << endl << endl;
        cout << endl << endl << endl << endl;
        cout << endl << endl << endl << endl;
        cout << endl << endl << endl << endl;
        cout << endl << endl << endl << endl;
}

/*
         1     2     3     4     5     6     7     8 

    1    0    54    45    56    39     4    35     6 
    2   46    57    38    33    36     7    14     3 
    3   53    44    55    40     1    34     5     8 
    4   58    47    52    37    32    15     2    13 
    5   43    62    41    28    51    18     9    16 
    6   48    59    26    31    24    21    12    19 
    7   61    42    29    50    27    10    17    22 
    8    0    49    60    25    30    23    20    11 

    Total Moves Made: 62

*/