I as at a friend's place over the holidays, and I picked up a little
sliding-tile puzzle of a lizard. There were 8 pieces on a little 3x3
grid, and I futzed with it a bit and decided that I didn't even like
those sorts of puzzles when they were that small.
That night, the cat got up in my lap, arranged itself across my
forearms, so I decided to "solve" the 3x3 8-piece sliding tile puzzle.
Now, this would have been an ideal time to try out Ruby, but with a
purring cat trapping my arms, that wasn't really practical.
Same with perl or TCL... I'd need a reference book at hand, and that
wasn't going to happen unless I dumped the cat. And it's just wrong
to dump a purring cat, so I fell back on that old standby we call C.
Just for fun. It's just 'noodling'... futzing around, really, until
I got a reasonable answer. Then I went to bed.
The next day I looked at the code and cringed. There's lots of things
about this code that, frankly, suck. So I'll append it here for all
to pick at, criticize, and so forth. I'll also follow up this post
with _my_ initial reaction.
(The approach is simple -- a brute-force breadth-first search of all
the possible moves.)
There's lots of stuff to criticize. Have fun.
-----------------------------------------------------------------------------
/*
* $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;
}
-----------------------------------------------------------------------------
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
