t1.c

solve the 8-puzzle problem using A* algorithm. Definitely written by my self, also include BGI graph

/*
Solution of the 8 puzzle.
*/

#include <stdio.h>
#include <string.h>
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <windows.h>
#include <stdio.h>

#include "graphics.h"
const int Height = 400;
const int Width  = 400;

#define DOWN 0
#define UP 1
#define LEFT 2
#define RIGHT 3
#define H2

struct element
{
  int state[9];
  char* str;
  int pathcost;
  int valid;
  int totalcost;
  element* next;
};

int heur(int state[]);
void prepend(element* newnode, element* oldnode, int operator1);
int goal(int* state);
int NotOnQueue(int state[]);
element* BestFromQueue();
void PrintState(int* state);
int apply (int* newstate, int* oldstate, int op);
element* newelement();
int op(char);
char to_char(int i);// convert to char to display
int to_int(int j);// convert to int to display at BGI windows

void swap (int &m, int &n);
void moveUp (int *state,int &count_state);
void moveDown (int *state,int &count_state);
void moveLeft (int *state,int &count_state);
void moveRight (int *state,int &count_state);

void update(int **board);// update to BGI windows

char rep[] = "dulr";
int notvalid1[4] = { 6, 0, 0, 2 };
int notvalid2[4] = { 7, 1, 3, 5 };
int notvalid3[4] = { 8, 2, 6, 8 };
int applyparam[4] = { +3, -3, -1, +1 };
int GoalState[9] = { 0, 1, 2, 3, 4, 5, 6, 7, 8}; //8 indicates no tile 
int maxdepth;
char choice;

element* top;

int main()
{
  int state[9];

  printf("\nThe Eight Puzzle Game!\n");
  printf("Have Fun!!\n");
  printf("\n************************************************\n"
         " Please Enter the initial state of the game \n"
         " The Number will be 1 to 8, use x for the blank space.\n"
         " Please start writing them from left to right for each row,\n" 
         " from the top row to the bottom row.\n"
         " For example, your string will look like this '1 3 4 8 x 5 7 2 6'.\n"
         " Do not forget the spaces in between the characters.\n"
         " **************************************************\n");

  int i = 0;
  while(i<9)
	{
	char chr;
	chr = fgetc(stdin);
	if (chr==32) continue;
	if (chr=='x') state[i] = 8;
	else if (chr >= '1' && chr <= '9') state[i] = chr- '1';
	else { printf("\n!!Invalid Input.\n "
	              "Please ensure you enter the correct number. Example of valid input...1 3 4 8 x 5 7 2 6.", chr); return 1; }
	i++;
	}

  fgetc(stdin); //flush out the end of line character

  PrintState(state);
  
  printf("\n Now Enter the Goal State in a similar way. (Typical. 1 2 3 8 x 4 7 6 5): \n");

  i = 0;
  while(i<9)
	{
	char chr;
	chr = fgetc(stdin);
	if (chr==32) continue;
	if (chr=='x') GoalState[i] = 8;
	else if (chr >= '1' && chr <= '9') GoalState[i] = chr-'1';
	else { printf("chr=%d. Invalid Input.\n"
	              "Please ensure you enter the correct number. Example of valid input...1 2 3 8 x 4 7 6 5.",(int) chr); return 1; }
	i++;
	}
  PrintState(GoalState);
  int count=0;
  while(1) {//while loop S
  printf("\nEnter an action:\n"); 
  printf("For swap move-up('u') move-down('d') move- right('r') move-left('l'):\n");
  printf("('q') exit to do A start algorithm.\n");
  getchar();
  scanf("%c", &choice);
  if ((choice == 'q')||(choice == 'Q' )) break;
  if ((choice == 'u')||(choice == 'U' )) { moveUp (state,count);}
  if ((choice == 'd')||(choice == 'D' )) { moveDown (state,count);}
  if ((choice == 'l')||(choice == 'L' )) { moveLeft (state,count);}
  if ((choice == 'r')||(choice == 'R' )) { moveRight (state,count);}
  printf("Count of State: %d",count);
  PrintState(state);
  }
       
  while(1) {//while loop A
  bool search_again;
  printf( "\nNow, starting the A algorithm, \n"
          "\nEnter the maximum depth you want to search, less than 25 is solved quickly: ");
  scanf("%d", &maxdepth);

  printf("\nWorking...");
//link list
  top = newelement();
  for(i=0; i<9; i++)
    top->state[i] = state[i];
  top->totalcost = heur(state);
  
  element* newnode = newelement();
  while (1)
    {// while loop B
      element* node = BestFromQueue();
      if (node == NULL) {
	printf("done!\n");
	printf("There is no solution to this of less than %d depth.\n", maxdepth);
	printf("Up to 35 will take more time, if there is no solution of that, the pattern is usually unsolvable.\n\n"); 
	search_again=true;
	break;
     }
      else if (goal(node->state)) {// if A
	char chr[15];
	search_again=false;
	printf("done. \nFound the solution of least number of steps (%d).", node->pathcost);
	printf("\nWant a graphical display of each step? (Y/N)?");
	scanf("%s", chr);
	if(chr[0] =='n' || chr[0]=='N') {
	  printf("\n (Move Blank u=up, d=down, l=left, r=right)\n");
	  printf(node->str);
	  printf("\n");
	  break;
	}
	
	int block2[9];
	for (i=0; i<node->pathcost; i++)
	  {
	    PrintState(state);
	    printf("\nPress any key at the WINBGI windows and see the solution.\n");
	    getch();
	    apply(block2, state, op(node->str[i]));
	    for(int j=0; j<=8; j++)
	      state[j] = block2[j];
	  }
	PrintState(state);
	
	printf("\nGraphical Display Complete.\nThe steps taken were: (Move blank u=up, d=down, l-left, r=right)\n");
	printf(node->str);
	printf("\n");
	break;
      }//end of if A

      if (node->totalcost > maxdepth) continue;

      for(i=0; i<=3; i++) {// for A
	if (apply(newnode->state, node->state, i) == -1)
	  continue;

	if (NotOnQueue(newnode->state)) {// if B
	  prepend(newnode, node, i);
	  newnode = newelement();
	  if (newnode==NULL) { printf ("ERROR!! insufficient memory!! Try decreasing depth!"); return 1; }
	     }//end of if B
      }//end of for A
	  }//end of while loop B
	if (!search_again) break;
	}//end of while loop A
	return 0;
}

int heur(int* state)
{
#ifdef H2
  int to_return = 0;

  for(int i=0; i<9; i++)
    {
    to_return += abs((i/3) - (state[i]/3));
    to_return += abs((i%3) - (state[i]%3));
    }
  return to_return;
  
#else
  int to_return = 0;

  for(int i=0; i<9; i++)
    {
      if (state[i] != i) to_return++;
    }
  return to_return;
  

#endif

}


void prepend(element* newnode, element* oldnode, int op)
{
  newnode->next = top;
  top = newnode;

  strcpy(newnode->str, oldnode->str);
  newnode->str[oldnode->pathcost] = rep[op];
  newnode->str[oldnode->pathcost+1] = 0;

  newnode->pathcost = oldnode->pathcost+1;
  newnode->totalcost = newnode->pathcost + heur(newnode->state);
  if (newnode->totalcost < oldnode->totalcost) newnode->totalcost = oldnode->totalcost;
}


int goal(int* state)
{
  int* g_block = GoalState;

  for(int i=0; i<9; i++)
    if ((*(state++))!=(*(g_block++)))
      return 0;

  return 1;
}

int NotOnQueue(int* state)
{
  int i,j;
  element* t = top;
  
  while (t!=NULL)
    {
      for(i=0; i<9; i++)
	if (t->state[i] != state[i]) break;
      if (i==9) return 0;
      
      t = t->next;
    }
  return 1;
}

element* BestFromQueue()
{
  element* t = top;
  int min_totalpathcost = 1000;
  int totalpathcost;
  element* to_return = NULL;

  while (t != NULL)
    {
	  if (t->valid==1 && t->totalcost < min_totalpathcost)
	{
	min_totalpathcost = t->totalcost;
	to_return = t;
	}
      t = t->next;
    }
  
  if (to_return != NULL) to_return->valid = 0;

  return to_return;
}


int apply (int* newstate, int* oldstate, int op)
{
  int j;
  int blank;

  for (j=0; j<9; j++)
	if (oldstate[j]==8) { blank=j; break; }

  if (blank==notvalid1[op] || blank==notvalid2[op] || blank==notvalid3[op])
    return -1;

  for (j=0; j<9; j++)  
    newstate[j] = oldstate[j];

  newstate[blank] = newstate[blank+applyparam[op]];
  newstate[blank+applyparam[op]] = 8;

  return 1;
}

element* newelement()
{
  element* t = new element;
  if (t==NULL) return NULL;
  t->valid = 1;
  t->str = new char[maxdepth+1];
  if (t->str ==NULL) return NULL;
  t->str[0] = 0;
  t->pathcost = t->totalcost = 0;
  t->next = NULL;
  return t;
}

void PrintState(int* state)
{  
  int **matrix = new int*[3];//initilize matrix
	matrix[0]=new int[3];
	matrix[1]=new int[3];
	matrix[2]=new int[3];
   int k=0;
	for(int i=0;i<3;i++){
		 for (int j=0;j<3;j++){
		     matrix[i][j]=to_int(state[k]);//convert the queue to matrix,ready to display at BGI
		     k++;
	   }
	 }
	 update(matrix);
return 0;
}

char to_char(int i)
{
  if (i>=0 &&i<=7) return i+'1';
  else if (i==8) return 'x';
  else { printf("ERROR in Program!"); return -1; }

}

int to_int(int j)
{
	if (j>=0 && j<=7) return j+1;
	else if (j==8) return 0;
	else {printf("ERROR in Program!");return -1;}
	}
	
int op(char i)
{
switch (i)
  {
  case 'd': return 0;
  case 'u': return 1;
  case 'l': return 2;
  case 'r': return 3;
  default: printf("ERROR!"); return -1;
  }
}

void swap (int &m, int &n){
	int temp = m;
	m=n;
	n=temp;
}

void moveUp (int *state, int &count_state){
	       for (int q=0;q<9;q++){
	          if(state[q]==8){//move down
			       if ((q!=0)&&(q!=1)&&(q!=2)){//not in 0,1,2
				       swap(state[q],state[q-3]);
				       count_state++;
                   break;
				 }
				    else printf("Always be in position %d, you can't move up.",q);
			  }
		  }//finished
	
}

void moveDown (int *state,int &count_state) {
	       for (int q=0;q<9;q++){
	          if(state[q]==8){//move down
			       if ((q!=6)&&(q!=7)&&(q!=8)){//not in 6,7,8
				       swap(state[q],state[q+3]);
				       count_state++;
                   break;
               }
               else printf("Always be in position %d, you can't move down.",q);
				 }
	}//finished
}

void moveLeft (int *state,int &count_state){
	       for (int q=0;q<9;q++){
	          if(state[q]==8){//move left
			       if ((q!=0)&&(q!=3)&&(q!=6)){//not in 0.3.6
				       swap(state[q],state[q-1]);
				       count_state++;
				       break;
				 }
				 else printf("Always be in position %d, you can't move left.",q);
			  }
		  }//finished
}

void moveRight (int *state,int &count_state){
	       for (int q=0;q<9;q++){
	          if(state[q]==8){//move right
			       if ((q!=2)&&(q!=5)&&(q!=8)){//not in 2,5,8
				       swap(state[q],state[q+1]);
				       count_state++;
                  break;
				 }
				 else printf("Always be in position %d, you can't move right.",q);
			  }
		  }//finished
}

void update(int **board) {
	//Daniel's flicker-free function to draw out an 8-puzzle board
	//Takes a 3x3 array as input, 0 indicates the empty space
	
	//Setting up the Graphics
	static bool setup=false;
	if(!setup) {
   	int GraphDriver=0,GraphMode=0;
   	initgraph(&GraphDriver,&GraphMode,"", Width, Height );
   	setup = true;
	}

	//Variables for the function
	int XIncrement = (Width-40)/3;
	int YIncrement = ((Height-6)-40)/3;
	int x=0;
	int y=0;
	char s[2];
	static bool visual;
	
	//Initalising the variables
	s[1]='\0';
	setactivepage(visual);
	setbkcolor(BLACK);
	cleardevice();
	setfillstyle (SOLID_FILL, WHITE); 
	settextstyle(GOTHIC_FONT, HORIZ_DIR, 6);
	settextjustify(CENTER_TEXT, CENTER_TEXT);
	
	//Display different coloured squares for different numbers
	y=10;
	for(int i=0; i<3; i++) {
		x=10;
		for(int n=0; n<3; n++) {
			if(board[i][n]!=0) {
				setcolor(board[i][n]);
				bar(x,y,x+XIncrement,y+YIncrement);
			}
      	x+=10;
      	x+=XIncrement;
		}
		y+=10;
		y+=YIncrement;
	}
	
	//Display the actual numbers
	y=8*Height/40;
	for(int i=0; i<3; i++) {
		x=Width/6;
		for(int n=0; n<3; n++) {
			setcolor(WHITE);
			setbkcolor(board[i][n]);
			if(board[i][n]!=0) {
         	s[0] = board[i][n]+'0';
         	outtextxy(x, y, s);
         	moveto(0,0);
      	}
      	x+=2*(Width/6);
      }
      y+=13*Height/40;
   }
   
   //Set the page to display
   setvisualpage(visual);
   visual=!visual;
   
	delay(1000);
}