#
typedef char *PUZZ_REP;
const char FINAL_1[] = "12345678#";
const char FINAL_2[] = "14725836#";
const int PUZZ_LEN = 9;
int
main( int argc, char **argv )
{
for( ; ; )
{
extern void read_init_puzz_cfg( char * );
char init_puzz_cfg[ PUZZ_LEN ];
long bgn_time;
long end_time;
// collect puzzle configuration
//
cout < “Enter initial puzzle state, three spaces per line,” < endl;
cout < “using # to indicate location of blank space” < endl;
read_init_puzz_cfg( init_puzz_cfg );
// solve via depth-first search
//
time( &bgn_time );
solve( new_cfg, new_cfg, 0, 1 );
time( &end_time );
cout < “Depth-first search took “ < ( end_time – bgn_time )
< “ secs” < endl;
// solve via breadth-first search
//
time( &bgn_time );
solve( new_cfg, new_cfg, 0, 0 );
time( &end_time );
cout < “Breadth-first search took “ < ( end_time – bgn_time )
< “ secs” < endl;
}
}
void
read_init_puzz_cfg( char *p )
{
cout < “Enter initial puzzle state on three lines, “ < endl;
cout < “using ‘#’ character to represent blank tile “ < endl;
for( int line_no = 1; line_no <= 3; line_no++ )
{
int ch;
while( ch = getchar() )
{
if( isdigit( ch ) || ch == ‘#’ )
{
*p++ = ch;
}
else
if( ch == ‘\n’ )
{
break;
}
// skip intervening chars, assumed to be white
//
}
}
*p = ‘\0’;
}
int
solve( PUZZ_REP previous, PUZZ_REP current, int call_depth, int is_depth_1st_srch )
{
char candidate[ PUZZ_LEN + 1 ];
if( is_depth_1st_srch )
{
if( strcmp( current, FINAL_1 ) == 0 || strcmp( current, FINAL_2 ) == 0 )
{
cout < current < “[” < call_depth < “]” endl;
return 1;
}
}
// locate empty slot
int blank_index;
for( blank_index = 0; blank_index < 9; blank_index++ )
{
if( current[ blank_index ] == '#' )
{
break;
}
}
int potential_moves[ 4 ];
potential_moves[ 0 ] = blank_index - 1; // left
potential_moves[ 1 ] = blank_index + 1; // right
potential_moves[ 2 ] = blank_index - 3; // up
potential_moves[ 3 ] = blank_index + 3; // down
for( int i = 0; i < 4; i++ )
{
if( is_valid_index( potential_moves[ i ] ) )
{
strcpy( candidate, current );
// try to move blank as indicated; if result
// matches previous state, don't pursue it
int temp_char = candidate[ blank_index ];
candidate[ blank_index ] = candidate[ potential_moves[ i ];
candidate[ potential_moves[ i ] ] = temp_char;
if( strcmp( candidate, previous ) != 0 )
{
if( solve( current, candidate, call_depth + 1 ) )
{
return 1;
}
}
}
}
return 0;
}
int
is_valid_index( int ndx )
{
return ndx >= 0 & ndx < PUZZ_LEN;
}
#