Solution of the 8 puzzle.
                Uses A-Star algorithm.
                #include <stdio.h>
                #include <string.h>
                #include <iostream.h>
                #include <math.h>
                #include <stdlib.h>
                #define DOWN 0
                #define UP 1
                #define LEFT 2
                #define RIGHT 3
                #define H2
                struct elementstruct
                {
                  int block[9];
                  char* str;
                  int pathcost;
                  int valid;
                  int totalcost;
                  elementstruct* next;
                };
                int heur(int block[]);
                void prepend(elementstruct* newnode, elementstruct* oldnode, int operator1);
                int goal(int* block);
                int notonqueue(int block[]);
                elementstruct* bestnodefromqueue();
                void print_block(int* block);
                int apply (int* newstate, int* oldstate, int op);
                elementstruct* newelement();
                int op(char);
                char to_char(int i);
                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 goal_block[9] = { 0, 1, 2, 3, 4, 5, 6, 7, 8}; //8 indicates no tile
                int maxdepth;
                elementstruct* top;
                int main()
                {
                  int block[9];
                  printf("\nThe Eight Puzzle!\n");
                  printf("\nPlease Enter the initial state of the game \n"
                         " [Represent tiles with numbers 1 to 8, and the blank space as 'x'.\n"
                         " Start writing them from left to right for each row. Start from the topmost row to the bottommost row.\n"
                         " Your final string will look similar to this '1 4 2 3 x 6 7 8 5'.\n"
                         " Do not forget the spaces in between the characters]\n");
                  int i = 0;
                  while(i<9)
                    {
                    char chr;
                    chr = fgetc(stdin);
                    if (chr==32) continue;
                    if (chr=='x') block[i] = 8;
                    else if (chr >= '1' && chr <= '9') block[i] = chr - '1';
                    else { printf("Invalid Input. Example of valid input...2 1 3 4 7 5 6 8 x.", chr); return 1; }
                    i++;
                    }
                  fgetc(stdin); //flush out the end of line character
                  printf("\n Now Enter the Goal State in a similar way. (Typical. 1 2 3 4 5 6 7 8 x): ");
                  i = 0;
                  while(i<9)
                    {
                    char chr;
                    chr = fgetc(stdin);
                    if (chr==32) continue;
                    if (chr=='x') goal_block[i] = 8;
                    else if (chr >= '1' && chr <= '9') goal_block[i] = chr - '1';
                    else { printf("chr=%d. Invalid Input. Example of valid input...2 1 3 4 7 5 6 8 x.",(int) chr); return 1; }
                    i++;
                    }
                  printf("Enter the maximum depth you want to search (<25 is solved quickly): ");
                  scanf("%d", &maxdepth);
                  printf("\nWorking...");
                  top = newelement();
                  for(i=0; i<9; i++)
                    top->block[i] = block[i];
                  top->totalcost = heur(block);
                 
                  elementstruct* newnode = newelement();
                  while (1)
                    {
                      elementstruct* node = bestnodefromqueue();
                      if (node == NULL) {
                    printf("done!\n");
                    printf("There is no solution to this of less than %d depth.\n", maxdepth);
                    printf("Try increasing the depth by 5.\n");
                    printf("If there is no solution within 35-40 depth, the pattern is usually unsolvable.\n\n");
                    break;
                      }
                      else if (goal(node->block)) {
                    char chr[15];
                    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++)
                      {
                        print_block(block);
                        apply(block2, block, op(node->str[i]));
                        for(int j=0; j<=8; j++)
                          block[j] = block2[j];
                      }
                    print_block(block);
                   
                    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;
                   
                      }
                      if (node->totalcost > maxdepth) continue;
                      for(i=0; i<=3; i++) {
                    if (apply(newnode->block, node->block, i) == -1)
                      continue;
                    if (notonqueue(newnode->block)) {
                      prepend(newnode, node, i);
                      newnode = newelement();
                      if (newnode==NULL) { printf ("ERROR!! insufficient memory!! Try decreasing depth!"); return 1; }
                    }
                      }
                    }
                    return 0;
                }
                int heur(int* block)
                {
                #ifdef H2
                  int to_return = 0;
                  for(int i=0; i<9; i++)
                    {
                    to_return += abs((i/3) - (block[i]/3));
                    to_return += abs((i%3) - (block[i]%3));
                    }
                  return to_return;
                 
                #else
                  int to_return = 0;
                  for(int i=0; i<9; i++)
                    {
                      if (block[i] != i) to_return++;
                    }
                  return to_return;
                 
                #endif
                }
                void prepend(elementstruct* newnode, elementstruct* 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->block);
                  if (newnode->totalcost < oldnode->totalcost) newnode->totalcost = oldnode->totalcost;
                }
                int goal(int* block)
                {
                  int* g_block = goal_block;
                  for(int i=0; i<9; i++)
                    if ((*(block++))!=(*(g_block++)))
                      return 0;
                  return 1;
                }
                int notonqueue(int* block)
                {
                  int i,j;
                  elementstruct* t = top;
                 
                  while (t!=NULL)
                    {
                      for(i=0; i<9; i++)
                    if (t->block[i] != block[i]) break;
                      if (i==9) return 0;
                     
                      t = t->next;
                    }
                  return 1;
                }
                elementstruct* bestnodefromqueue()
                {
                  elementstruct* t = top;
                  int min_totalpathcost = 1000;
                  int totalpathcost;
                  elementstruct* 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;
                }
                elementstruct* newelement()
                {
                  elementstruct* t = new elementstruct;
                  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 print_block(int* block)
                {
                  printf("\n");
                  printf ("\n-------");
                  printf ("\n|%c|%c|%c|", to_char(block[0]), to_char(block[1]), to_char(block[2]));
                  printf ("\n-------");
                  printf ("\n|%c|%c|%c|", to_char(block[3]), to_char(block[4]), to_char(block[5]));
                  printf ("\n-------");
                  printf ("\n|%c|%c|%c|", to_char(block[6]), to_char(block[7]), to_char(block[8]));
                  printf ("\n-------");
                }
                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 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;
                  }
                }