/*
 * $Id: sliding_nine.c,v 1.2 2007/12/24 19:55:58 stremler Exp $
 */

/*
 * This program 'solves' the 3x3 sliding-puzzle problem.
 * Not robustly, it was hacked together in an evening. No design,
 * no testing, no good C programming habits.
 *
 * Author: Stewart Stremler
 * License: public domain
 */

#include <stdlib.h>
#include <stdio.h>
#include <strings.h>

#ifndef FALSE
#define FALSE 0
#define TRUE 1
#endif

#define ERROR_EMPTY_ARG "Programmer error. Empty argument in %s at %d\n"
#define ERROR_MALLOC_FAIL "Failed to allocate memory. In %s at %d\n"
#define ERROR_BAD_BOARD "Bad board configuration: '%s' in %s at %d\n"
#define ERROR_SWITCH_BROKE "Unknown value in switch: %d in %s at %d\n"

/* change BLANK to use a different 'empty' character. '_' might be good. */
#define BLANK ' '

/* The fundamental board structure. We have nine puzzle slots, but
 * we want to treat it as a string, so we need space for the terminating
 * null.  We want to eliminate repeats, so we keep track of the parent,
 * which also offers a simple way to print out the final pieces in order.
 */
typedef struct {
   char board[10];
   void *moves[4];
   void *prev;
} configuration;

/* We need a simple queue of arbitrary size, so we use a singly linked list.
 */
typedef struct {
   configuration *data;
   void *next;
} dequenode;

/* We push new items to the tail and pull them from the head for fast
 * O(1) access.
 * TODO - also keep a count of the # of elements in the queue?
 */
typedef struct {
   dequenode *head;
   dequenode *tail;
} deque;

/* ----------------------------------------------------------------- */

/* make_dequeue
 * creates a new queue.
 * exits on malloc failure.
 */
deque *make_deque() {
   deque *p;
   p = malloc( sizeof( deque ) );
   if ( p == NULL ) {
      fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__ );
      exit( EXIT_FAILURE );
   }

   p->head = NULL;
   p->tail = NULL;
}

/* deque_insert
 * inserts the current node into the queue.
 * exits on malloc failure.
 */
void deque_insert( deque *d, configuration *current ) {
   dequenode *n, *t;
   n = malloc( sizeof( dequenode ) );
   if ( n == NULL ) {
      fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__ );
      exit( EXIT_FAILURE );
   }

   n->data = current;

   if ( d->head == NULL ) {
      d->head = n;
   } else {
      t = d->tail;
      t->next = (struct dequenode *)n;
      /*d->tail->next = n;*/
   }
   d->tail = n;
}

/* deque_remove
 * removes the oldest node from the queue.
 * do not call if queue is empty.
 */
configuration *deque_remove( deque *d ) {
   configuration *p;
   dequenode *q;

   q = d->head;
   p = q->data;

   if ( d->head == d->tail ) {
      d->head = NULL;
      d->tail = NULL;
   } else {
      d->head = (dequenode *)d->head->next;
   }

   free( q );

   return p;
}

/* deque_empty
 * answers if the queue is empty.
 */
int deque_empty( deque *d ) {
   return d->head == NULL;
}

/* deque_size
 * answers the number of items in the queue.
 * warning - very slow. Walks the linked list. See TODO for struct.
 */
int deque_size( deque *d ) {
   int count = 0;
   dequenode *p = d->head;
   dequenode *end = d->tail;
   while ( p != end ) { count++; p = p->next; }
   return count;
}

/* ----------------------------------------------------------------- */

/* got_match
 * Answers if the two configurations are equivalent.
 * Exits on programmer error.
 */
int got_match( configuration *current, configuration *final ) {
   if ( current == NULL ) {
      return FALSE;
   }
   if ( final == NULL ) {
      fprintf( stderr, ERROR_EMPTY_ARG, __FILE__, __LINE__ );
      /*return FALSE;*/
      exit( EXIT_FAILURE );
   }

   return ! (strncmp( current->board, final->board, 10 ));
}

/* got_repeat
 * Walks the ancestor list looking for a configuration that is equivalent
 * to the current node. This is an optimization step.
 */
int got_repeat( configuration *current ) {
   configuration *p;
   p = (configuration *)current->prev;
   while ( p != NULL ) {
      if ( got_match( p, current ) ) return TRUE;
      p = (configuration *)p->prev;
   }
   return FALSE;
}

/* new
 * Answers a clone of the the provided configuration. A NULL configuration
 * will cause an uninitialized configuration to be created.
 * TODO - how much of the brute-force initialization can we remove?
 */
configuration *new( configuration *current ) {
   configuration *p;

   p = malloc( sizeof( configuration ) );
   if ( p == NULL ) {
      fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__);
      exit( EXIT_FAILURE );
   }
   p->board[0] = '\0';
   p->board[1] = '\0';
   p->board[2] = '\0';
   p->board[3] = '\0';
   p->board[4] = '\0';
   p->board[5] = '\0';
   p->board[6] = '\0';
   p->board[7] = '\0';
   p->board[8] = '\0';
   p->board[9] = '\0';
   p->board[10] = '\0';
   p->prev = NULL;
   p->moves[0] = NULL;
   p->moves[1] = NULL;
   p->moves[2] = NULL;
   p->moves[3] = NULL;

   if ( current != NULL ) {
      char *a, *b;
      p->prev = (struct configuration *)current;
      strncpy( p->board, current->board, 10 );
   } 

   return p;
}

/* swap_tile
 * Swaps the board elements at the specified location.
 * Assumes arguments are valid and sensible.
 */
void swap_tile( configuration *current, int source, int dest ) {
   char temp;
   temp = current->board[dest]; 
   current->board[dest] = current->board[source]; 
   current->board[source] = temp;
}

/* make_child
 * Creates a unique new child of the current configuration using the
 * specified swap of tiles and adding to the specified move slot.
 * If the child repeats an ancestor state, it is discarded.
 */
void make_child( configuration *current, int move, int dest, int source ) {
   configuration *p;
   p = new( current );
   swap_tile( p, source, dest );
   if ( ! got_repeat( p ) ) {
      current->moves[move] = (struct configuration *)p;
   } else {
      free( p );
   }
}

/* fill_children
 * Creates all the possible children of the current configuration and
 * adds them to the current configuration.
 */
void fill_children( configuration *current ) {
   configuration *p;
   char temp;
   int i;
   int blank = -1;

   for ( i = 0; i < 9; i++ ) {
      if ( current->board[i] == BLANK ) {
         blank = i;
         break;
      }
   }

   if ( blank < 0 ) {
      fprintf( stderr, ERROR_BAD_BOARD, current->board, __FILE__, __LINE__);
      return;
   }

   /*
    *   0  |  1  |  2
    * -----+-----+-----
    *   3  |  4  |  5
    * -----+-----+-----
    *   6  |  7  |  8
    *
    */

   switch ( blank ) {
      case 0: /* 1->0, 3->0 */
         make_child( current, 0, 0, 1 );
         make_child( current, 1, 0, 3 );
         break;
      case 1: /* 0->1, 2->1, 4->1 */
         make_child( current, 0, 1, 0 );
         make_child( current, 1, 1, 2 );
         make_child( current, 2, 1, 4 );
         break;
      case 2: /* 1->2, 5->2 */
         make_child( current, 0, 2, 1 );
         make_child( current, 1, 2, 5 );
         break;
      case 3: /* 0->3, 4->3, 6-> 3 */
         make_child( current, 0, 3, 0 );
         make_child( current, 1, 3, 4 );
         make_child( current, 2, 3, 6 );
         break;
      case 4: /* 1->4, 3->4, 5->4, 7->4 */
         make_child( current, 0, 4, 1 );
         make_child( current, 1, 4, 3 );
         make_child( current, 2, 4, 5 );
         make_child( current, 3, 4, 7 );
         break;
      case 5: /* 2->5, 4->5, 8->5 */
         make_child( current, 0, 5, 2 );
         make_child( current, 1, 5, 4 );
         make_child( current, 2, 5, 8 );
         break;
      case 6: /* 3->6, 7->6 */
         make_child( current, 0, 6, 3 );
         make_child( current, 1, 6, 7 );
         break;
      case 7: /* 6->7, 4->7, 8->7 */
         make_child( current, 0, 7, 4 );
         make_child( current, 1, 7, 6 );
         make_child( current, 2, 7, 8 );
         break;
      case 8: /* 5->8, 7->8 */
         make_child( current, 0, 8, 5 );
         make_child( current, 1, 8, 7 );
         break;
      default:
         fprintf( stderr, ERROR_SWITCH_BROKE, blank, __FILE__, __LINE__ );
   }
}

/* walk_solutions
 * Breadth-first walk of the solution tree and find the first solution.
 */
configuration *walk_solutions( configuration *initial, configuration *final ) {
   configuration *current;
   deque *queue;
   int i;

   queue = make_deque();
   deque_insert( queue, initial );

   while ( TRUE ) {
      current = deque_remove( queue );
      if ( got_match( current, final ) ) {
         return current; /* leak memory like mad */
      }

#ifdef MONITOR_PROGRESS
      i = deque_size( queue );
      if ( i % 100 == 0 ) {
         if ( i < 1000 ) fprintf(stderr, ".");
         else if ( i < 10000 ) fprintf(stderr, ":");
         else if ( i < 100000 ) fprintf(stderr, "!");
         else fprintf(stderr, "#");
      }
#endif

      fill_children( current );
      for ( i = 0; i < 4; i++ ) {
         if ( current->moves[i] != NULL ) {
            deque_insert( queue, (configuration *)current->moves[i] );
         }
      }/* for */

   }/* while */
}

/* print_solution_size
 * Outputs the number of moves it took to solve the problem.
 */
void print_solution_size( configuration *end ) {
   configuration *p;
   int count;

   count = 0;
   p = end;
   while ( p != NULL ) { 
      p = (configuration *)p->prev; 
      count++; 
   }

   fprintf( stdout, "There are %d steps in the solution.\n", count);
}

/* print_solutions
 * Print the solution-stack, in reasonable order.
 * Recursive.
 */
void print_solutions( configuration *end ) {
   if ( end->prev != NULL ) {
      print_solutions( (configuration *)end->prev );
   }
   int row, col;
   for ( row = 0; row < 3; row++ ) {
      for ( col = 0; col < 3; col++ ) {
         fprintf( stdout, " [%c] ", end->board[row * 3 + col] );
      }
      fprintf( stdout, "\n" );
   }
   fprintf( stdout, "\n" );
}

/* ----------------------------------------------------------------- */

/* usage
 * Outputs how to use the program.
 */
void usage( char **argv ) {
   fprintf( stderr, "Usage: %s start end\n", argv[0]);
   fprintf( stderr, "\tstart = 9 character board configuration\n");
   fprintf( stderr, "\tend   = 9 character board configuration\n");
   fprintf( stderr, "\t(Note that a blank is REQUIRED!)\n");
   /* change this if change definition of BLANK define */
}

/* main
 * program entry-point
 */
int main( int argc, char **argv ) {
   configuration *start;
   configuration *end;
   configuration *solution;

   if ( argc != 3 ) { usage( argv ); return EXIT_FAILURE; }

   start = new( NULL );
   end = new( NULL );

   if ( strlen( argv[1] ) != 9 ) { usage( argv ); return EXIT_FAILURE; }
   if ( strlen( argv[2] ) != 9 ) { usage( argv ); return EXIT_FAILURE; }

   strncpy( start->board, argv[1], 10 );
   strncpy( end->board, argv[2], 10 );

   fprintf( stdout, "Starting with '%s' and trying for '%s'\n",
            start->board, end->board );
   fprintf( stdout, "start: %p \t end: %p\n", start, end );

   solution = walk_solutions( start, end );

   print_solution_size( solution );

   print_solutions( solution );

   return EXIT_SUCCESS;
}