SJS wrote:
> /*
> * $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 ' '
#define BLANK '.'
/* allows entry of board with 10-key */
>
> /* 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;
> }
> -----------------------------------------------------------------------------
>
> --
> [email protected]
> http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
