/************************************************************** @VL7342 ****/
/******************************* PEG SOLITAIRE *****************************/
/***************************************************************************/
/* Takes a .txt file as an input {peg solitaire board} during the run ******/
/* process and returns the steps of a solution to this board by both *******/
/* printing them on the screen and saving them in a file {output.txt}. *****/
/* The program accepts two types of boards: ********************************/
/* a) an odd sized square board, and ***************************************/
/* b) an english style peg solitaire board. ********************************/
/* If there is no solution available it returns an appropriate message. ****/
/***************************************************************************/

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

#define 	OK 			1
#define 	TRUE 			1
#define 	FALSE			0

#define 	ERROR_1		803	/* Error codes used during the program. *****/
#define 	ERROR_2		813	/* If you want to find out more about them **/
#define 	ERROR_3		817	/* then view the error function. ************/
#define 	ERROR_4		833
#define	ERROR_5		877
#define	ERROR_6		883
#define	ERROR_7		887
#define	ERROR_8		891
#define	ERROR_9		893
#define	ERROR_10		897
#define	ERROR_11		911
#define	ERROR_12		917

#define	FILENAME_MAX_LENGTH	1000 /* Used to parse the input's filename */
#define	CHOICE_MAX_LENGTH		1000 /* Used to parse the 1st choice of the user */

/******************************************************* structure step ****/
/* Basic Structure of the program - Stores each state of the board *********/
/***************************************************************************/
struct step{
	int *game_board;
	int lines;
	int depth;
	struct step *previous;
	struct step *next;
};
typedef struct step step;

/***************************************************** structure boards ****/
/* Keeps a history of the boards in order to avoid state cycling ***********/
/***************************************************************************/
struct boards{
	int *board;
	int lines;
	int pegs;
	struct boards *previous;
	struct boards *next;
};
typedef struct boards boards;

/***************************************** board manipulation functions ****/
/***************************************************************************/
int *board_copy(int lines, int *board);
int board_depth(int *board, int l);
void print_board(int lines, int *board);
void fprint_board(int lines, int *board, FILE *output);

/*************************************************** file I/O functions ****/
/***************************************************************************/
int *check_in_sq(FILE *input);
int *check_in_en(FILE *input);
void to_array(FILE *input, int lines, int *board);

/********************************************* error handling functions ****/
/***************************************************************************/
void error(int error_code);

/*********************************************** ending state functions ****/
/***************************************************************************/
int end_state_check(int *board, int l);
void print_back(step *start, step *p, int l, clock_t t1, clock_t t2);
void fprint_back(step *start, step *p, int l, clock_t t1, clock_t t2);

/************************************ game states list {step} functions ****/
/***************************************************************************/
step *alloc_step(int *board, int l, int dep);
step *play_game(int l, int dep, step *start, step *current, int *board, boards *store_board, clock_t t1);
step *pointer_chasing(step *current,int l,int *temp_board,boards *search_b,int dep);

/************************************************* board list functions ****/
/***************************************************************************/
boards *alloc_board(int *board, int l, int pegs);
boards *search_board(int *board, int l, int pegs, boards *search_point);

/*************************************************** movement functions ****/
/***************************************************************************/
int check_down(int *board, int l, int i, int j);
int check_left(int *board, int l, int i, int j);
int check_right(int *board, int l, int i, int j);
int check_up(int *board, int l, int i, int j);

int *down(int *board, int l, int i, int j);
int *left(int *board, int l, int i, int j);
int *right(int *board, int l, int i, int j);
int *up(int *board, int l, int i, int j);

/************************************************** interface functions ****/
/***************************************************************************/
void print_star(int num);
void newline(int num);
void intro(void);
void instructions(void);
void print_user_choices(void);
void print_file_name_question(void);
void the_end(void);

/****************************************************** free the memory ****/
/***************************************************************************/
void free_all(step *first, step *second, step *third, int *board, boards *value);


/**** Some quick notes *****************************************************/
/***************************************************************************/
/* The value array[i][j] could be replaced with *(array + i*WIDTH + j) *****/
/* where WIDTH is the the width of the array. ******************************/
/***************************************************************************/
/* lines or l variables denote the lines of the board **********************/
/***************************************************************************/
/* depth or dep variables denote the number of the pegs on the board *******/
/***************************************************************************/


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

	FILE *input;
	step *start, *current, *result;
	boards *start2;
	int *board, *check;
	int lines, i = 0, depth = 0, c;
	char filename[FILENAME_MAX_LENGTH], choice[CHOICE_MAX_LENGTH];
	clock_t t1;

 	/* In case of the user types something like 'pegboard b1.txt' */
	if (argc > 1){
		newline(2);
		printf("Notice: This program does not accept multiple arguments.\n");
		printf("        Everything is handled during runtime.");
		return 1;
	}

	/* Intro - general directions */
	intro(); instructions(); print_user_choices();
	/* A nice way to avoid 'mistakes' from the user input */
	while ((c = getchar()) != '\n'){ /* get all the chars the user types */
		choice[i++] = (char)c;
	}
	choice[i] = '\0';
	if (i > 1){ error(ERROR_11); exit(1); } /* If the user types more than one characher */
	/* If the user input is not whithin the possible choices */
	if ( (atoi(choice) < 1) || (atoi(choice) > 2) ){ error(ERROR_11); return 1; }

	print_file_name_question();
	if ( scanf("%s",filename)!= 1 ){ error(ERROR_12); exit(1); }

	/* checking the last four characters of the filename - they should match with '.txt' */
	while (filename[i]!='\0'){ i++;}
	if ( (filename[i-1] != 't') || (filename[i-2] != 'x') || (filename[i-3] != 't') || (filename[i-4] != '.') )
	{ error(ERROR_10); return 1; }

	input = fopen(filename,"r");
	if (input == NULL){ error(ERROR_9); exit(1); }

	if (atoi(choice) == 1){ /* applying the appropriate parsing function for each choice */
		check = check_in_sq(input);
	}
	else{
		check = check_in_en(input);
	}

	if (*check != OK){ error(*check); return 1; }
	else{
		/* this value points to the number of the lines -> more info at check_in functions */
		lines = *(check+1);
	}
	fclose(input);

	board = (int *) malloc(lines * lines * sizeof(int));
	if (board == NULL){ error(ERROR_6); exit(1); }

	/* Transform .txt input to an array with ones and zeros (and 2's for the walls if it is an english board) */
	input = fopen(filename,"r");
	if (input == NULL){ error(ERROR_9); exit(1); }
	to_array(input, lines, board);
	fclose(input);

	depth = board_depth(board,lines); /* depth of the board will always be the number of pegs on it */

	/* Init list of playing boards */
	start = current = alloc_step(board,lines,depth); /* the first element of the step list */
	result = alloc_step(board,lines,depth);
	current->previous = start;

	/* Init list of stored boards */
	start2 = alloc_board(board,lines,depth); /* the first element of the boards list */
	start2->previous = NULL;


	t1 = clock(); /* trigger timer */
	/* start the game */
	result = play_game(lines,depth,start,current,current->game_board,start2,t1);

	printf("\nUnfortunately there is no solution to this board... This is not your lucky day!\n");

	return 0;
}

/************************************************************ FUNCTIONS ****/
/***************************************************************************/

/**** board manipulation functions *****************************************/
/*********************************************************** board_copy ****/
/* creates a copy of the given board ***************************************/
/***************************************************************************/
int *board_copy(int lines, int *board){

	int i, j;
	int *copy;

	copy = (int *)malloc(lines * lines * sizeof(int));
	if (copy == NULL){ error(ERROR_6); exit(2); }

	for (i = 0; i < lines; i++){
		for (j = 0; j < lines; j++){
			*(copy + i*lines + j ) = *(board + i*lines + j);
		}
	}

	return copy;
}
/********************************************************** board_depth ****/
/* assigns a value to the board's depth regarding the live pegs ************/
/***************************************************************************/
int board_depth(int *board, int l){
	int i,j, depth = 0;

	for (i = 0; i < l; i++){
		for (j = 0; j < l; j++){
			if (*(board + i*l + j) == 1){
				depth++;
			}
		}
	}

	return depth;
}
/*********************************************************** print_board ****/
/* prints the board array to the screen {surrounded by stars} ***************/
/****************************************************************************/
void print_board(int lines, int *board){

	int i, j;

	printf("\n     ");
	print_star(lines+2);

	for (i = 0; i < lines; i++){
		printf("\n     *");
		for (j=0; j<lines; j++){
			if (*(board + i*lines + j) == 1){
				printf("O");
			}
			else if (*(board + i*lines + j) == 0){
				printf(".");
			}
			else{
				printf("x");
			}
		}
		printf("*");
	}
	printf("\n     ");
	print_star(lines+2);
	printf("\n");
}
/********************************************************** fprint_board ****/
/* prints the board array {surrounded by stars!} to a file ******************/
/****************************************************************************/
void fprint_board(int lines, int *board, FILE *output){

	int i, j;

	fprintf(output,"\n     ");
	for (i = 0; i < lines + 2; i++){
		fprintf(output,"*");
	}

	for (i = 0; i < lines; i++){
		fprintf(output,"\n     *");
		for (j = 0; j < lines; j++){
			if (*(board + i*lines + j) == 1){
				fprintf(output,"O");
			}
			else if (*(board + i*lines + j) == 0){
				fprintf(output,".");
			}
			else{
				fprintf(output,"x");
			}
		}
		fprintf(output,"*");
	}
	fprintf(output,"\n     ");
	for (i = 0; i < lines + 2; i++){
			fprintf(output,"*");
	}
	fprintf(output,"\n");
}

/***************************************************************************/

/**** file I/O functions ***************************************************/
/********************************************************** check_in_sq ****/
/* Checks the solitaire board (input file) for errors **********************/
/* Returns a pointer to a static array which contains the values of error,**/
/* char number and lines ***************************************************/
/***************************************************************************/
int * check_in_sq(FILE *input){

	int j,char_count = 0,lines = 0;
	int error = OK, first_time_in = TRUE;
	double chars_per_line = 0;
	static int return_values[2];

	while ((j = fgetc(input)) != EOF){

		if ( ((char)j == 'O') || ((char)j == '.') ){
			char_count ++;
		}
		else if ((char)j == '\n'){
			lines ++;

			if (first_time_in == TRUE){
				chars_per_line = (double)char_count;
				first_time_in = FALSE;
			}

			/* check if its line has the same number of elements */
			if (chars_per_line != ((double)char_count/(double)lines)){
				return_values[0] = ERROR_3; return return_values;
			}
		}/* do not accept white spaces */
		else if ( (char)j == ' '){
			return_values[0] = ERROR_1; return return_values;
		}
		else{/* do not accept other characters */
			return_values[0] = ERROR_2; return return_values;
		}
	}

	/* do not accept even sized boards */
	if (lines%2 == 0){ return_values[0] = ERROR_5; return return_values; }

	/* check if the shape of the board is square */
	if (lines != (char_count/lines)){ return_values[0] = ERROR_4; return return_values; }

	return_values[0] = error;
	return_values[1] = lines;
	return return_values;
}
/********************************************************** check_in_en ****/
/* Checks the english peg solitaire board (input file) for errors **********/
/* Returns a pointer to a static array which contains the values of error,**/
/* char number and lines ***************************************************/
/***************************************************************************/
int * check_in_en(FILE *input){

	int j,char_count = 0,lines = 0, error = OK, first_time_in = TRUE;
	double chars_per_line = 0;
	static int return_values[2];

	while ((j = fgetc(input)) != EOF){
		if ( ((char)j == 'O') || ((char)j == '.') || ((char)j == 'x') ){
			char_count ++;
		}
		else if ((char)j == '\n'){
			lines ++;

			if (first_time_in == TRUE){
				chars_per_line = (double)char_count;
				first_time_in = FALSE;
			}

			/* check if its line has the same number of elements */
			if (chars_per_line != ((double)char_count/(double)lines)){
				return_values[0] = ERROR_3; return return_values;
			}
		}/* do not accept white spaces */
		else if ( (char)j == ' '){
			return_values[0] = ERROR_1; return return_values;
		}
		else{/* do not accept other characters */
			return_values[0] = ERROR_2; return return_values;
		}
	}

	/* do not accept even sized boards */
	if (lines%2 == 0){ return_values[0] = ERROR_5; return return_values; }

	/* check if the shape of the board is square */
	if (lines != (char_count/lines)){ return_values[0] = ERROR_4; return return_values; }

	return_values[0] = error;
	return_values[1] = lines;
	return return_values;
}
/************************************************************* to_array ****/
/* Creates an array of the given board file with ones (pegs), zeros (free **/
/* slots), and two's (wall in the case of english peg board) ***************/
/***************************************************************************/
void to_array(FILE *input, int lines, int *board){

	int i = 0, k;

	while ((k = fgetc(input)) != EOF){

		if ((char)k == '\n'){ /* skip new lines */
			continue;
		}

		if ((char)k == 'O'){
			*(board + i) = 1;	/* one for peg */
			i++;
		}
		else if ((char)k == '.'){
			*(board + i) = 0; /* zero for free square */
			i++;
		}
		else{
			*(board + i) = 2; /* two for wall */
			i++;
		}
	}
}

/***************************************************************************/

/**** error handling functions *********************************************/
/**************************************************************** error ****/
/* prints errors occured in the input file given by the user ***************/
/***************************************************************************/
void error(int error_code){

	newline(2); print_star(70); newline(1); print_star(4); printf(" ");

	switch(error_code){
		case ERROR_1:
			printf("White space in the input file is not allowed! "); print_star(19); break;
		case ERROR_2:
			printf("Wrong type of character in the file! "); print_star(28); break;
		case ERROR_3:
			printf("The lines of the input file do not have the same size. "); print_star(10);
			printf("\n**** White or blank lines are not allowed. "); print_star(27); break;
		case ERROR_4:
			printf("The given board is not square. Please correct your input! "); print_star(7); break;
		case ERROR_5:
			printf("The board size must be an even number! "); print_star(26); break;
		case ERROR_6:
			printf("Cannot allocate memory space for the game board! "); print_star(16); break;
		case ERROR_7:
			printf("Cannot allocate memory space for the next stage data structure! *"); break;
		case ERROR_8:
			printf("Give a filename as the second argument to start the game! "); print_star(7); break;
		case ERROR_9:
			printf("Cannot open input/output .txt file! "); print_star(29); break;
		case ERROR_10:
			printf("Give only one file of the correct format (*.txt) as an input! ***"); break;
		case ERROR_11:
			printf("Give a number {1 or 2} without any space before or after! *******"); break;
		case ERROR_12:
			printf("This is not a correct answer! Please be more careful! ***********"); break;
		default:
			printf("Wrong ERROR code... Someone changed the source code! ************");
	}

	newline(1); print_star(70); newline(2);
}

/***************************************************************************/

/**** game states list {step} functions ************************************/
/*********************************************************** alloc_step ****/
/* allocation of space for the structure elements **************************/
/***************************************************************************/
step *alloc_step(int *board, int l, int dep){

	step *p;

	p = (step *)calloc(1,sizeof(step));
	if (p == NULL){ error(ERROR_7); exit(2); }

	p->game_board = (int *)malloc(l*l*sizeof(int));
	if ((p -> game_board) == NULL){ error(ERROR_6); exit(2); }

	p->game_board = board_copy(l,board);

	p->lines = l;
	p->depth = dep;

	return p;
}
/************************************************************ play_game ****/
/* coordinates the peg solitaire solution algorithm ************************/
/* the algorithm is described in extend.pdf ********************************/
/***************************************************************************/
step *play_game(int l, int dep, step *start, step *current, int *board, boards *start_store_board, clock_t t1){

	int i, j;
	int *temp_board;
	step *temp, *p;
	boards *search_b;
	clock_t t2;

	p = alloc_step(board,l,dep);

	if ( (dep == 1) && end_state_check(board,l) == TRUE){

		t2 = clock();
		print_back(start,current,l,t1,t2);
		fprint_back(start,current,l,t1,t2);
		the_end();
		newline(1);
		free_all(p,start,current,board,start_store_board);
		exit(2);
	}

	/* for all the pegs of the board */
	for (i = 0; i < l; i++){
		for (j = 0; j < l; j++){

			if (check_right(board,l,i,j) == TRUE){ /* Is a move to right possible? */

				temp_board = board_copy(l,board);
				temp_board = right(temp_board,l,i,j); /* make the move and store the new board */
				/* search this board in the boards structure - have we been there before? */
				search_b = search_board(temp_board,l,dep-1,start_store_board);

				if (search_b != NULL){ /* if the search does not search a value, then proceed */
					/* do the pointer chasing --> explained in the function */
					temp = pointer_chasing(current,l,temp_board,search_b,dep);
					/* recursion - run the game function again for the new board */
					p = play_game(l,dep-1,start,temp,temp_board,start_store_board,t1);
				}
			}

			/* comments are the same as the first if's...! */
			if (check_left(board,l,i,j) == TRUE){

				temp_board = board_copy(l,board);
				temp_board = left(temp_board,l,i,j);
				search_b = search_board(temp_board,l,dep-1,start_store_board);

				if (search_b != NULL){
					temp = pointer_chasing(current,l,temp_board,search_b,dep);
					p = play_game(l,dep-1,start,temp,temp_board,start_store_board,t1);
				}
			}

			if (check_up(board,l,i,j) == TRUE){

				temp_board = board_copy(l,board);
				temp_board = up(temp_board,l,i,j);
				search_b = search_board(temp_board,l,dep-1,start_store_board);

				if (search_b != NULL){
					temp = pointer_chasing(current,l,temp_board,search_b,dep);
					p = play_game(l,dep-1,start,temp,temp_board,start_store_board,t1);
				}
			}

			if (check_down(board,l,i,j) == TRUE){

				temp_board = board_copy(l,board);
				temp_board = down(temp_board,l,i,j);
				search_b = search_board(temp_board,l,dep-1,start_store_board);

				if (search_b != NULL){
					temp = pointer_chasing(current,l,temp_board,search_b,dep);
					p = play_game(l,dep-1,start,temp,temp_board,start_store_board,t1);
				}
			}
		}
	}

	free(p);
	free(current);

	/* if nothing is left to explore and no end state occured, then return NULL */
	/* this route has failed! ***************************************************/
	return NULL;
}
/****************************************************** pointer_chasing ****/
/* does the appropriate chaining for the lists {step & boards} after *******/
/* a new state comes to play ***********************************************/
/***************************************************************************/
step *pointer_chasing(step *current,int l,int *temp_board,boards *search_b,int dep){
	step *temp;
	boards *temp2;

	temp = alloc_step(temp_board,l,dep-1); /* this is the new board */
	temp->previous = current; /* link the new board with the previous item of the current board */
	temp2 = alloc_board(temp_board,l,dep-1); /* this is the new board stored in the board's collection list */

	if (search_b->previous == NULL){ /* if the search result is the first element of the boards list */
		temp2->previous = search_b; /* place temp2 after the first element */
		search_b->next = temp2; /* make the first element to point to temp2 */
	}
	else{ /* if it is not the first element of the list */
		temp2->next = search_b; /* next element of temp2 will be the search result */
		/* make the next element of the (prior) previous element of the search result */
		/* to point to temp2 */
		search_b->previous->next = temp2;
		temp2->previous = search_b->previous; /* obvious! */
		/* by doing that we managed to place temp2 between 2 elements of the list */
		search_b->previous = temp2;
	}

	return temp;
}

/***************************************************************************/

/**** board list functions *************************************************/
/********************************************************** alloc_board ****/
/* Allocates space for the next element of the stored boards list **********/
/***************************************************************************/
boards *alloc_board(int *board, int l, int pegs){
	boards *p;

	p = (boards *)calloc(1,sizeof(boards));
	if (p == NULL){ error(ERROR_7); exit(2); }

	p->board = (int *)malloc(l*l*sizeof(int));
	if ((p->board) == NULL){ error(ERROR_6); exit(2); }

	p->board = board_copy(l,board);
	p->lines = l;
	p->pegs = board_depth(board,l);

	return p;
}
/********************************************************* search_board ****/
/* Searches the board list - returns NULL if it finds the same board as ****/
/* the input - returns a pointer next to the position the new board ********/
/* will be placed **********************************************************/
/***************************************************************************/
boards *search_board(int *board, int l, int pegs, boards *search_point){

	boards *pointer;
	int input_pegs, i, j, same_flag = TRUE;

	pointer = search_point;
	input_pegs = board_depth(board,l);

	while (pointer->next != NULL){

		if ( (pointer->pegs) < input_pegs){
			return pointer; /* we do not need to search anymore - there is no match! */
		}
		else if ((pointer->pegs) == input_pegs){/* checking for a possible match */
			for (i = 0; i < l; i++){
				if (same_flag == FALSE){ break; }
				for (j = 0; j < l; j++){
					if (*((pointer->board) + i*l + j) != *(board + i*l + j)){
						same_flag = FALSE;
						break; /* found a miss match - no need to continue further */
					}
				}
			}
		}
		else{
			same_flag = FALSE;
		}

		if (same_flag == FALSE){
			pointer = pointer->next; /* go to the next element */
			same_flag = TRUE;
		}
		else{
			return NULL;
		}
	}

	return pointer;
}

/***************************************************************************/

/**** movement functions ***************************************************/
/******************************************************** check_up & up ****/
/* for the functions below: check_direction -> checks if a move to that ****/
/* direction is possible and direction-> makes the move ********************/
/* if i - 2 >= 0 then i - 2 is an existing line of the board
 * board[i - 2][j] *** . -> O *** 0 -> 1
 * board[i - 1][j] *** O -> . *** 1 -> 0
 * board[i][j]     *** O -> . *** 1 -> 0
*/
int check_up(int *board, int l, int i, int j){
	if ( ((i-2) >= 0) && (*(board + i*l + j) == 1) && (*(board + (i-1)*l + j) == 1) && (*(board + (i-2)*l + j) == 0)){
		return TRUE;
	}
	else{
		return FALSE;
	}
}
/***************************************************************************/
int *up(int *board, int l, int i, int j){

	*(board + i*l + j) = 0;
	*(board + (i-1)*l + j) = 0;
	*(board + (i-2)*l + j) = 1;
	return board;
}
/**************************************************** check down & down ****/
/***************************************************************************/
/* if i + 2 < lines then i + 2 is an existing line of the board
 * board[i][j]      *** O -> . *** 1 -> 0
 * board[i + 1][j]  *** O -> . *** 1 -> 0
 * board[i + 2][j]  *** . -> O *** 0 -> 1
*/
int check_down(int *board, int l, int i, int j){
	if ( ((i+2) < l) && (*(board + i*l + j) == 1) && (*(board + (i+1)*l + j) == 1) && (*(board + (i+2)*l + j) == 0)){
		return TRUE;
	}
	else{
		return FALSE;
	}
}
/***************************************************************************/
int *down(int *board, int l, int i, int j){

	*(board + i*l + j) = 0;
	*(board + (i+1)*l + j) = 0;
	*(board + (i+2)*l + j) = 1;
	return board;
}
/**************************************************** check left & left ****/
/* checks if a move left is possible and then carries out the move *********/
/***************************************************************************/
/* the same applies for the horizontal lines * view the previous comments **/
int check_left(int *board, int l, int i, int j){
	if ( ((j-2) >= 0) && (*(board + i*l + j) == 1) && (*(board + i*l + j-1) == 1) && (*(board + i*l + j-2) == 0) ){
		return TRUE;
	}
	else{
		return FALSE;
	}
}
/***************************************************************************/
int *left(int *board, int l, int i, int j){

	*(board + i*l + j) = 0;
	*(board + i*l + j-1) = 0;
	*(board + i*l + j-2) = 1;
	return board;
}
/************************************************** check right & right ****/
/* checks if a move right is possible and then carries out the move ********/
/***************************************************************************/
/* the same applies for the horizontal lines * view the previous comments **/
int check_right(int *board, int l, int i, int j){

	if ( ((j+2) < l) && (*(board + i*l + j) == 1) && (*(board + i*l + j+1) == 1) && (*(board + i*l + j+2) == 0)){
		return TRUE;
	}
	else{
		return FALSE;
	}
}
/***************************************************************************/
int *right(int *board, int l, int i, int j){

	*(board + i*l + j) = 0;
	*(board + i*l + j+1) = 0;
	*(board + i*l + j+2) = 1;
	return board;
}

/***************************************************************************/

/**** ending state functions ***********************************************/
/****************************************************** end_state_check ****/
/* decides if a state is an ending one *************************************/
/***************************************************************************/
int end_state_check(int *board, int l){

	int i,j;
	int flag_the_end = TRUE;

	for (i=0; i<l; i++){
		if (flag_the_end == FALSE){ break; }
		for (j=0; j<l; j++){
			/* only the middle square = 1, else return FALSE */
			if ( (*(board + i*l + j) == 1) && ((i != (l/2)) || (j != (l/2))) ){
				flag_the_end = FALSE;
				break;
			}
		}
	}

	return flag_the_end;
}
/*********************************************************** print_back ****/
/* goes backwards and prints the steps of the solution {in the proper way} */
/* in the end reveals the amount of time taken to compute the solution of **/
/* the input board *********************************************************/
/***************************************************************************/
void print_back(step *start, step *p,int l, clock_t t1, clock_t t2){

	step *reverse, *temp, *pp;
	int state = 1;

	pp = p; /* make a copy to avoid pointer CHAOS */
	reverse = alloc_step(pp->game_board,l,start->depth);

	/* go from previous to previous in the list and save the results in an other list */
	/* we do that in order to print the solution in a proper reversed way */
	while (pp!=start){
		pp = pp->previous;
	   reverse->next = alloc_step(pp->game_board,l,pp->depth);
		temp = reverse;
		reverse = reverse->next;
		reverse->previous = temp;
	}

	printf("\n------ INPUT ------");
	print_board(l,start->game_board);

	/* printint the reverse list */
	while ((reverse->previous)!= NULL){
		printf("\n------ %d ------",state);
		print_board(l,reverse->game_board);
		reverse = reverse->previous;
		state++;
	}

	printf("\n------ %d ------",state);
	print_board(l,reverse->game_board);
	newline(1); print_star(34);

	/* printing the time taken! -> for the solution not for the printing! */
	printf("\n**** Time taken: %.5f sec \n",((double)(t2-t1))/((double)CLOCKS_PER_SEC) );
	print_star(34); newline(1);
}
/********************************************************** fprint_back ****/
/* is the same with print_back but prints the data in the file output.txt **/
/***************************************************************************/
void fprint_back(step *start, step *p, int l, clock_t t1, clock_t t2){

	FILE *output;
	step *reverse, *temp, *pp;
	int state = 1;

	pp = p;
	reverse = alloc_step(pp->game_board,l,start->depth);

	while (pp!=start){
		pp = pp->previous;
	   reverse->next = alloc_step(pp->game_board,l,pp->depth);
		temp = reverse;
		reverse = reverse->next;
		reverse->previous = temp;
	}

	output = fopen("output.txt","w");
	if (output == NULL){ error(ERROR_9); exit(1); }

	fprintf(output,"\n------ INPUT ------");
	fprint_board(l,start->game_board,output);

	while ((reverse->previous)!= NULL){
		fprintf(output,"\n------ %d ------",state);
		fprint_board(l,reverse->game_board,output);
		reverse = reverse->previous;
		state++;
	}

	fprintf(output,"\n------ %d ------",state);
	fprint_board(l,reverse->game_board,output);
	fprintf(output,"\n**********************************");
	fprintf(output,"\n**** Time taken: %.5f sec \n",((double)(t2-t1))/((double)CLOCKS_PER_SEC) );
	fprintf(output,"**********************************\n");

	fclose(output);
}

/***************************************************************************/

/**** interface functions **************************************************/
/* used for printing information to the user *******************************/
/************************************** an easy way to printf new lines ****/
void newline(int num){
	if (num > 0){
		printf("\n");
		newline(num-1);
	}
}
/******************************************* an easy way to print stars ****/
void print_star(int num){
	if (num > 0){
		printf("*");
		print_star(num-1);
	}
}
/******************************************************** intro message ****/
void intro(void){
	newline(2); print_star(70);
	newline(1); print_star(51); printf(" Peg Solitaire "); print_star(4);
	newline(1); print_star(4); printf(" @vl7342 "); print_star(57);
	newline(1); print_star(70);
	newline(1);
}
/********************************************************* instructions ****/
void instructions(void){
	newline(1);
	print_star(70);
	newline(1);
	print_star(47); printf(" Game Instructions "); print_star(4); newline(1);
	print_star(70); newline(1);
	print_star(4); printf(" 1. You can choose a different game type in the beginning "); print_star(8); newline(1);
	print_star(7); printf(" by typing the appropriate choice [1 or 2] "); print_star(20); newline(1);
	print_star(70); newline(1);
	print_star(4); printf(" 2. Then you type the filename {*.txt} in which your starting "); print_star(4); newline(1);
	print_star(7); printf(" game board is held "); print_star(43); newline(1);
	print_star(70); newline(1);
	print_star(4); printf(" 3. In type 1 .txt boards you should use O for a peg and . for "); print_star(3); newline(1);
	print_star(7); printf(" an empty square "); print_star(46); newline(1);
	print_star(70); newline(1);
	print_star(4); printf(" 4. In type 2 .txt boards you should use O for a peg, . for an "); print_star(3); newline(1);
	print_star(7); printf(" empty square and x for the squares that are not used "); print_star(9); newline(1);
	print_star(70); newline(2);
}
/**************************************** print the choices to the user ****/
void print_user_choices(void){
	newline(1); print_star(70); newline(1);
	print_star(4); printf(" Type 1 if you want to play odd sized square peg solitaire or ");
	print_star(4); newline(1);
	print_star(4); printf(" type 2 if you want to play english peg solitaire...::... ");
}
/*************************************** typing the prompt for filename ****/
void print_file_name_question(void){
	print_star(70);
	newline(1);
	print_star(4);
	printf(" Type the name of the text file that defines the peg board ");
	print_star(7); newline(1);
	print_star(4); printf(" {e.g. b1.txt}...::... ");
}
/****************************************************** the end message ****/
void the_end(void){
	newline(2);
	print_star(60); newline(1);
	print_star(4); printf(" You may view the solution in the file output.txt! ");
	print_star(5); newline(1); print_star(60); newline(2);
}

/***************************************************************************/

/************************************************************* free_all ****/
/* frees the memory from 'not needed anymore' data *************************/
/***************************************************************************/
void free_all(step *first, step *second, step *third, int *board, boards *value){
	free(first);
	free(second);
	free(third);
	free(board);
	free(value);
}

/***************************************************************************/
/**** @VL7342 **** T.L. **** S.I.L.W.Y. ******************* END OF CODE ****/