/*  POTM entry:  LostLuggage               */
/*  Creator:     Gunnar Andersson          */
/*  Email:       gunnar@nada.kth.se        */
/*  Compile with 'gcc LostLuggage.c -lm'   */
/*  Source last modified October 24, 2000  */


/*  Second version of LostLuggage, will probably score a bit better
    on the systest problem, and also for most other problems.  This
    POTM, as opposed to last time around, it was non-trivial to write
    a program that's better than a clever human for all positions.

    / Gunnar                                                    */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>



#define  TRUE                     1
#define  FALSE                    0

#define  INFINITY                 1000000000

#define  MAX_ROWS                 16
#define  MAX_COLS                 32
#define  MAX_MOVES                512

#define  MAX_OBJECTS              25

#define  MAX_DEPTH                1000

/* Various hash table sizes, all must be powers of 2 */
#define  SEARCH_TABLE_SIZE        262144
#define  GREEDY_TABLE_SIZE        262144
#define  PENALTY_TABLE_SIZE       131072
#define  LOWER_TABLE_SIZE         65536

/* The time in seconds after which the best solution found is output */
#define  MAXIMUM_TIME             570.0

/* The number of nodes between consecutive clock readings */
#define  TIME_CHECK_INTERVAL      5000



typedef struct {
  int row, col;
  int height, width;
  int area;
  int exists;
  int active;
  int last_playable_row, last_playable_col;
  int index;
  int type;
  unsigned int mask;
} Object;


typedef struct {
  int row, col;
  char name;
} Move;


typedef struct {
  unsigned long high, low;
} HashCode;


typedef struct {
  unsigned low_code;
  int failed_draft;
} SearchHashEntry;


typedef struct {
  unsigned low_code;
  int penalty;
  short piece;
  short failed_draft;
  short row;
  short col;
} GreedyHashEntry;


typedef struct {
  unsigned low_code;
  int penalty;
} PenaltyHashEntry;


typedef struct {
  unsigned low_code;
  int lower_bound;
} LowerHashEntry;



double program_start_time;
int solution_found;
int solution_length;
int rows;
int cols;
int obj_count;
int timeout;
int occupied[MAX_ROWS];
unsigned long node_count;
unsigned long last_time_check;
unsigned long hash_probe_count, hash_hit_count;
short first_one[32768];
Move history[MAX_DEPTH + 1];
Object target;
Object obj_list[MAX_OBJECTS];
HashCode piece_hash[MAX_OBJECTS][MAX_ROWS][MAX_COLS];
HashCode current_hash;
SearchHashEntry search_table[SEARCH_TABLE_SIZE];
GreedyHashEntry greedy_table[GREEDY_TABLE_SIZE];
PenaltyHashEntry penalty_table[PENALTY_TABLE_SIZE];
LowerHashEntry lower_table[LOWER_TABLE_SIZE];



/*
  SORT_SHAPE_LIST
  Sort the pieces and check if there are any pieces of the same shape
  and size.
*/

static void
sort_shape_list( void ) {
  int i, j;
  int found;
  int shape_count;
  int changed;
  Object temp;

  do {
    changed = FALSE;
    for ( i = 0; i < obj_count - 1; i++ )
      if ( (obj_list[i].area > obj_list[i + 1].area) ||
	   ((obj_list[i].area == obj_list[i + 1].area) &&
	    (obj_list[i].width > obj_list[i + 1].width)) ) {
	temp = obj_list[i];
	obj_list[i] = obj_list[i + 1];
	obj_list[i + 1] = temp;
	changed = TRUE;
      }
  } while ( changed );

  shape_count = 0;
  for ( i = 0; i < obj_count; i++ ) {
    found = FALSE;
    for ( j = 0; j < i; j++ )
      if ( (obj_list[i].height == obj_list[j].height) &&
	   (obj_list[i].width  == obj_list[j].width) ) {
	found = TRUE;
	break;
      }
    if ( found )
      obj_list[i].type = obj_list[j].type;
    else {
      obj_list[i].type = shape_count;
      shape_count++;
    }
  }
}



static void
hash_table_init( void ) {
  int i, j, k;

  srandom( 4711 );

  for ( i = 0; i < MAX_OBJECTS; i++ )
    for ( j = 0; j < MAX_ROWS; j++ )
      for ( k = 0; k < MAX_COLS; k++ ) {
	piece_hash[i][j][k].high = random();
	piece_hash[i][j][k].low = random();
      }

  for ( i = 0; i < SEARCH_TABLE_SIZE; i++ ) {
    search_table[i].low_code = 0;
    search_table[i].failed_draft = 0;
  }

  for ( i = 0; i < GREEDY_TABLE_SIZE; i++ ) {
    greedy_table[i].low_code = 0;
    greedy_table[i].penalty = INFINITY;
  }

  for ( i = 0; i < PENALTY_TABLE_SIZE; i++ ) {
    penalty_table[i].low_code = 0;
    penalty_table[i].penalty = INFINITY;
  }

  for ( i = 0; i < LOWER_TABLE_SIZE; i++ ) {
    lower_table[i].low_code = 0;
    lower_table[i].lower_bound = INFINITY;
  }
}



static HashCode
get_hash( void ) {
  int i;
  int row, col, type;
  HashCode result;

  result.high = 0;
  result.low = 0;
  for ( i = 0; i < obj_count; i++ ) {
    row = obj_list[i].row;
    col = obj_list[i].col;
    type = obj_list[i].type;
    result.high ^= piece_hash[type][row][col].high;
    result.low  ^= piece_hash[type][row][col].low;
  }

  return result;
}



static void
table_init( void ) {
  unsigned int i;

  first_one[0] = -1;
  for ( i = 1; i < 32768; i++ )
    if ( i & 1 )
      first_one[i] = 0;
    else
      first_one[i] = first_one[i >> 1] + 1;
}



static double
get_timer( void ) {
  return (double) clock() / ((double) CLOCKS_PER_SEC);
}



/*
  POP_COUNT
  Counts the number of bits set in N.
*/

static int
pop_count( unsigned int n ) {
  int count;

  for ( count = 0; n; count++, n &= (n - 1) )
    ;

  return count;
}



/*
  FIND_FIRST_ONE
  Returns the bit position for the first set bit in N.
*/

static int
find_first_one( int n ) {
  if ( n >= 32768 ) {
    if ( n & 32767 )
      return first_one[n & 32767];
    else
      return 15 + first_one[n >> 15];
  }
  else
    return first_one[n];
}



/*
  GENERATE_ALL_MOVES
  Generates a bit vector where the Ith entry has bits set for the
  moves possible to row I for OBJ.
*/

static void
generate_all_moves( Object *obj, unsigned int *feasible ) {
  int i, j;
  unsigned int mask;

  for ( i = 0; i < rows; i++ ) {
    feasible[i] = occupied[i];
    for ( j = (obj->width - 1); j >= 1; j-- )
      feasible[i] |= (feasible[i] >> 1);
  }

  for ( i = 0; i <= obj->last_playable_row; i++ )
    for ( j = (obj->height - 1); j >= 1; j-- )
      feasible[i] |= feasible[i + j];

  mask = (1 << (cols + 1 - obj->width)) - 1;
  for ( i = obj->last_playable_row; i >= 0; i-- )
    feasible[i] = (~feasible[i]) & mask;
}



/*
  XOR_PIECE
  Adds or removes piece # INDEX to position (ROW,COL).
*/

#define xor_piece( index, row, col ) { \
  int loop; \
  unsigned int mask; \
  Object *obj; \
\
  obj = &obj_list[index]; \
  mask = obj->mask << col; \
  for ( loop = obj->height - 1; loop >= 0; loop-- ) \
    occupied[loop + row] ^= mask; \
\
  current_hash.high ^= piece_hash[obj->type][row][col].high; \
  current_hash.low  ^= piece_hash[obj->type][row][col].low; \
}



/*
  PENALTY_VALUE
  Calculates the following penalty function: For all possible places
  where the target piece can be played, the number of occupied positions
  is counted.  The penalty value is the minimum of this over all positions.
*/

static int
penalty_value( void ) {
  int i, j, k;
  int penalty, lowest_penalty;
  int bits_set[MAX_ROWS];
  unsigned int hash_index;

  hash_index = current_hash.high & (PENALTY_TABLE_SIZE - 1);
  if ( penalty_table[hash_index].low_code == current_hash.low )
    return penalty_table[hash_index].penalty;

  lowest_penalty = INFINITY;
  for ( i = 0; i <= target.last_playable_col; i++ ) {
    if ( i == 0 )
      for ( j = 0; j < rows; j++ )
	bits_set[j] = pop_count( occupied[j] & target.mask );
    else
      for ( j = 0; j < rows; j++ ) {
	bits_set[j] -= (occupied[j] >> (i - 1)) & 1;
	bits_set[j] += (occupied[j] >> (i + target.width - 1)) & 1;
      }
    penalty = 0;
    for ( k = 0; k < target.height; k++ )
      penalty += bits_set[k];
    if ( penalty < lowest_penalty )
      lowest_penalty = penalty;
    for ( j = 1; j <= target.last_playable_row; j++ ) {
      penalty += (bits_set[j + target.height - 1] - bits_set[j - 1]);
      if ( penalty < lowest_penalty )
	lowest_penalty = penalty;
    }
  }

  penalty_table[hash_index].low_code = current_hash.low;
  penalty_table[hash_index].penalty = lowest_penalty;

  return lowest_penalty;
}



static void
greedy_and_complete_search( int current_penalty, int depth,
			    int max_depth, int depth_bound );

static void
complete_search( int depth, int max_depth, int depth_bound );



/*
  GREEDY_SEARCH
  Searches for the move which decreases the penalty value the most,
  plays this move, and calls greedy_and_complete_search() recursively.
  If there are no moves decreasing the penalty value, nothing happens.
*/

static void
greedy_search( int current_penalty, int depth, int max_depth,
	       int depth_bound ) {
  int i, j, k;
  int row, col;
  int old_row, old_col;
  int best_row, best_col, best_index;
  int generated_height, generated_width;
  int move_count;
  int this_penalty, lowest_penalty;
  int stored_row[MAX_MOVES], stored_col[MAX_MOVES];
  unsigned int hash_index;
  unsigned int feasible[MAX_ROWS];
  Object *this;

  node_count++;

  if ( solution_found || timeout )
    return;

  hash_index = current_hash.high & (GREEDY_TABLE_SIZE - 1);

  hash_probe_count++;
  if ( greedy_table[hash_index].low_code == current_hash.low ) {
    hash_hit_count++;
    if ( greedy_table[hash_index].failed_draft >= max_depth - depth )
      return;
  }

  if ( greedy_table[hash_index].low_code == current_hash.low ) {
    lowest_penalty = greedy_table[hash_index].penalty;
    best_index = greedy_table[hash_index].piece;
    best_row = greedy_table[hash_index].row;
    best_col = greedy_table[hash_index].col;
  }
  else {
    generated_height = -1;
    generated_width = -1;
    move_count = 0;
    lowest_penalty = INFINITY;

    /* Start with the largest pieces, they can result in the largest
       decrease in the penalty value */
    for ( i = obj_count - 1; i >= 0; i-- ) {
      this = &obj_list[i];

      if ( !this->active )
	continue;

      if ( current_penalty - this->area >= lowest_penalty )
	continue;

      /* Never optimal to move a 1x1 piece twice in a row */
      if ( (this->area == 1) && (depth > 0) &&
	   (history[depth - 1].name == this->index + 'A') )
	continue;

      if ( (this->height != generated_height) ||
	   (this->width != generated_width) ) {
	generate_all_moves( this, feasible );
	move_count = 0;
	for ( j = 0; j <= this->last_playable_row; j++ )
	  while ( feasible[j] != 0 ) {
	    k = find_first_one( feasible[j] );
	    feasible[j] ^= (1 << k);
	    stored_row[move_count] = j;
	    stored_col[move_count] = k;
	    move_count++;
	  }
	generated_height = this->height;
	generated_width = this->width;
      }

      for ( j = 0; (j < move_count) && !solution_found; j++ ) {
	node_count++;

	row = stored_row[j];
	col = stored_col[j];
	old_row = this->row;
	old_col = this->col;
	xor_piece( i, old_row, old_col );
	xor_piece( i, row, col );

	this_penalty = penalty_value();
	if ( this_penalty < lowest_penalty ) {
	  lowest_penalty = this_penalty;
	  best_index = i;
	  best_row = row;
	  best_col = col;
	}

	xor_piece( i, old_row, old_col );
	xor_piece( i, row, col );
      }
    }

    greedy_table[hash_index].low_code = current_hash.low;
    greedy_table[hash_index].penalty = lowest_penalty;
    greedy_table[hash_index].piece = best_index;
    greedy_table[hash_index].row = best_row;
    greedy_table[hash_index].col = best_col;
    greedy_table[hash_index].failed_draft = 0;
  }

  if ( lowest_penalty < current_penalty ) {
    this = &obj_list[best_index];
    row = best_row;
    col = best_col;
    history[depth].name = obj_list[best_index].index + 'A';
    history[depth].row = row;
    history[depth].col = col;

    old_row = this->row;
    old_col = this->col;
    xor_piece( best_index, old_row, old_col );
    xor_piece( best_index, row, col );
    this->row = row;
    this->col = col;

    greedy_and_complete_search( lowest_penalty, depth + 1,
				 max_depth + 1, depth_bound );

    this->row = old_row;
    this->col = old_col;
    xor_piece( best_index, old_row, old_col );
    xor_piece( best_index, row, col );

    if ( !solution_found ) {
      greedy_table[hash_index].low_code = current_hash.low;
      greedy_table[hash_index].failed_draft = max_depth - depth;
    }
  }
}



/*
  COMPLETE_SEARCH
  Tries all possible moves from a position.
*/

static void
complete_search( int depth, int max_depth, int depth_bound ) {
  int i, j, k;
  int row, col;
  int old_row, old_col;
  int generated_height, generated_width;
  int move_count;
  int stored_row[MAX_MOVES], stored_col[MAX_MOVES];
  unsigned long hash_index;
  unsigned int feasible[MAX_ROWS];
  Object *this;

  node_count++;

  if ( solution_found || timeout )
    return;

  /* Check if this configuration, or an equivalent, has already been
     tried with at least the same number of remaining moves available. */

  hash_probe_count++;

  hash_index = current_hash.high & (SEARCH_TABLE_SIZE - 1);
  if ( search_table[hash_index].low_code == current_hash.low ) {
    hash_hit_count++;
    if ( search_table[hash_index].failed_draft >= max_depth - depth )
      return;
  }

  generate_all_moves( &target, feasible );
  for ( i = 0; i <= target.last_playable_row; i++ )
    if ( feasible[i] != 0 ) {
      solution_found = TRUE;
      solution_length = depth + 1;
      history[depth].name = 'X';
      history[depth].row = i;
      j = 0;
      while ( !(feasible[i] & (1 << j)) )
	j++;
      history[depth].col = j;
    }

  if ( depth < max_depth - 1 ) {
    generated_height = -1;
    generated_width = -1;
    move_count = 0;
    for ( i = 0; i < obj_count; i++ ) {
      this = &obj_list[i];

      if ( !this->active )
	continue;

      /* Never optimal to move a 1x1 piece twice in a row */
      if ( (this->area == 1) && (depth > 0) &&
	   (history[depth - 1].name == this->index + 'A') )
	continue;

      /* When generating moves, exploit the fact that pieces of the
	 same shape have identical sets of feasible moves. */

      if ( (this->height != generated_height) ||
	   (this->width != generated_width) ) {
	generate_all_moves( this, feasible );
	move_count = 0;
	for ( j = 0; j <= this->last_playable_row; j++ )
	  while ( feasible[j] != 0 ) {
	    k = find_first_one( feasible[j] );
	    feasible[j] ^= (1 << k);
	    stored_row[move_count] = j;
	    stored_col[move_count] = k;
	    move_count++;
	  }
	generated_height = this->height;
	generated_width = this->width;
      }

      for ( j = 0; (j < move_count) && !solution_found; j++ ) {
	row = stored_row[j];
	col = stored_col[j];
	history[depth].name = obj_list[i].index + 'A';
	history[depth].row = row;
	history[depth].col = col;

	old_row = this->row;
	old_col = this->col;
	xor_piece( i, old_row, old_col );
	xor_piece( i, row, col );
	this->row = row;
	this->col = col;

	greedy_and_complete_search( penalty_value(), depth + 1,
				     max_depth, depth_bound );

	this->row = old_row;
	this->col = old_col;
	xor_piece( i, old_row, old_col );
	xor_piece( i, row, col );
      }
    }
  }

  /* Store what's known about the current position in the hash table */

  if ( !solution_found &&
       (search_table[hash_index].failed_draft <= (max_depth - depth) + 1) ) {
    search_table[hash_index].low_code = current_hash.low;
    search_table[hash_index].failed_draft = max_depth - depth;
  }
}



/*
  ESTIMATE_LOWER_BOUND
  Returns a conservative lower bound on the number of moves in an
  optimal solution from the current position.
*/

static int
estimate_lower_bound( void ) {
  int i, j, k;
  int this_bound, lower_bound;
  static int low_row_index = 0;
  static int low_col_index = 0;
  unsigned int hash_index;
  Object *this;

  hash_index = current_hash.high & (LOWER_TABLE_SIZE - 1);
  if ( lower_table[hash_index].low_code == current_hash.low )
    return lower_table[hash_index].lower_bound;

  /* The minimum coverage is likely to be attained by the same rectangle
     in consecutive calls, so try that one first in order to get a good
     bound. */

  lower_bound = 1;  /* The target piece always has to be moved */
  for ( k = 0; k < obj_count; k++ ) {
    this = &obj_list[k];

    if ( (this->row < low_row_index + target.height) &&
	 (this->row + this->height - 1 >= low_row_index) &&
	 (this->col < low_col_index + target.width) &&
	 (this->col + this->width - 1 >= low_col_index) ) {
      if ( this->active )
	lower_bound++;
      else
	lower_bound = INFINITY;
    }
  }

  for ( i = target.last_playable_row; i >= 0; i-- )
    for ( j = target.last_playable_col; j >= 0; j-- ) {
      this_bound = 1;
      /* Start with the biggest pieces, they are most likely to cover */
      for ( k = obj_count - 1; k >= 0; k-- ) {
	this = &obj_list[k];
	if ( (this->row < i + target.height) &&
	     (this->row + this->height - 1 >= i) &&
	     (this->col < j + target.width) &&
	     (this->col + this->width - 1 >= j) ) {
	  if ( this->active )
	    this_bound++;
	  else  /* Never optimal to move this piece in an optimal solution */
	    this_bound = INFINITY;
	  if ( this_bound >= lower_bound )  /* Can't attain minimum */
	    break;
	}
      }
      if ( this_bound < lower_bound ) {
	lower_bound = this_bound;
	low_row_index = i;
	low_col_index = j;
      }
    }

  lower_table[hash_index].lower_bound = lower_bound;
  lower_table[hash_index].low_code = current_hash.low;

  return lower_bound;
}



/*
  GREEDY_AND_SELECTIVE_SEARCH
  The core search function, which calls the two subfunctions for
  complete and greedy searches.
*/

static void
greedy_and_complete_search( int current_penalty, int depth,
			    int max_depth, int depth_bound ) {
  double current_time;

  if ( node_count > last_time_check + TIME_CHECK_INTERVAL ) {
    current_time = get_timer();
    if ( current_time - program_start_time > MAXIMUM_TIME )
      timeout = TRUE;
  }

  /* See if the search can be aborted here because the shortest
     path to a solution provably exceeds the upper bound. */
  if ( (depth < depth_bound - 1) &&
       (depth > depth_bound - 10) &&
       (depth + estimate_lower_bound() > depth_bound) )
    return;

  complete_search( depth, max_depth, depth_bound );

  if ( max_depth < depth_bound )
    greedy_search( current_penalty, depth, max_depth, depth_bound );
}



static void
print_solution( Move *solution, int length ) {
  int i;

  for ( i = 0; i < length; i++ )
    printf( "%c %d-%d\n", solution[i].name, solution[i].row + 1,
	    solution[i].col + 1 );

}



int
main( int argc, char *argv[] ) {
  char board[MAX_ROWS][2 * MAX_COLS + 2];
  double stop_time;
  int i, j, k;
  int index;
  int lower_bound, upper_bound, search_bound;
  int piece_area, board_area;
  int any_stored, stored_length;
  int length[MAX_ROWS];
  FILE *stream;
  Move stored_solution[MAX_DEPTH + 1];

  program_start_time = get_timer();

  if ( argc != 2 ) {
    fputs( "No file argument provided.\n", stderr );
    exit( EXIT_FAILURE );
  }

  stream = fopen( argv[1], "r" );
  if ( stream == NULL ) {
    fprintf( stderr, "Can't open '%s' for reading.\n", argv[1] );
    exit( EXIT_FAILURE );
  }

  rows = 0;
  fgets( board[rows], 2 * MAX_COLS + 2, stream );
  while ( !feof( stream ) && (rows < MAX_ROWS) ) {
    length[rows] = strlen( board[rows] ) - 1;
    board[rows][length[rows]] = '\0';
    rows++;
    fgets( board[rows], 2 * MAX_COLS + 2, stream );
  }

  fclose( stream );

  cols = 0;
  while ( (board[0][cols] != ' ') && (board[0][cols] != '\0') )
    cols++;

  board_area = rows * cols;

  target.width = length[0] - cols - 1;
  target.last_playable_col = cols - target.width;
  target.mask = (1 << target.width) - 1;
  target.height = 0;
  while ( (target.height < rows) && (length[target.height] != cols) )
    target.height++;
  target.last_playable_row = rows - target.height;
  target.area = target.height * target.width;

#ifdef VERBOSE
  printf( "%d rows, %d columns\n", rows, cols );
  printf( "Target is %dx%d\n", target.height, target.width );
#endif

  for ( i = 0; i < MAX_OBJECTS; i++ )
    obj_list[i].exists = FALSE;
  obj_count = 0;

  piece_area = 0;
  for ( i = 0; i < rows; i++ )
    for ( j = 0; j < cols; j++ )
      if ( board[i][j] != '_' ) {
	index = board[i][j] - 'A';
	if ( !obj_list[index].exists ) {
	  obj_count++;
	  obj_list[index].index = index;
	  obj_list[index].row = i;
	  obj_list[index].col = j;
	  obj_list[index].exists = TRUE;
	  k = 0;
	  while ( ((i + k) < rows) && (board[i + k][j] == board[i][j]) )
	    k++;
	  obj_list[index].height = k;
	  obj_list[index].last_playable_row = rows - k;
	  k = 0;
	  while ( ((j + k) < cols) && (board[i][j + k] == board[i][j]) )
	    k++;
	  obj_list[index].width = k;
	  obj_list[index].last_playable_col = cols - k;
	  obj_list[index].mask = (1 << k) - 1;
	  obj_list[index].area =
	    obj_list[index].width * obj_list[index].height;

	  /* Moving a piece which is larger than the target can never be
	     the right thing to do */
	  obj_list[index].active =
	    (obj_list[index].width < target.width) ||
	    (obj_list[index].height < target.height);
#ifdef VERBOSE
	  if ( !obj_list[index].active )
	    printf( "Moving piece %c can never be optimal\n", board[i][j] );
#endif
	  piece_area += obj_list[index].area;
	}
      }

#ifdef VERBOSE
  printf( "Total area is %d, of which %d is occupied.\n\n",
	  board_area, piece_area );
#endif

  if ( piece_area + target.area > board_area ) {
    /* Not enough room for target piece! */
    puts( "NO SOLUTION" );
    return EXIT_SUCCESS;
  }

  for ( i = 0; i < rows; i++ ) {
    occupied[i] = 0;
    for ( j = 0; j < cols; j++ )
      if ( board[i][j] != '_' )
	occupied[i] |= 1 << j;
  }

  table_init();

  sort_shape_list();

  hash_table_init();
  current_hash = get_hash();

  solution_found = FALSE;

  node_count = 0;
  last_time_check = 0;
  hash_probe_count = 0;
  hash_hit_count = 0;

  timeout = FALSE;
  any_stored = FALSE;

  lower_bound = estimate_lower_bound();
#ifdef VERBOSE
  printf( "Lower bound on solution length: %d moves\n", lower_bound );
#endif
  search_bound = 1;
  upper_bound = MAX_DEPTH;

  /* Loop until either
     (a) the time is out
     (b) the lower and upper bounds on the length of an optimal solution match
  */

  do {
#ifdef VERBOSE
    printf( "Difficulty %d, bound %d\n", search_bound, upper_bound - 1 );
#endif
    greedy_and_complete_search( penalty_value(), 0, search_bound,
				upper_bound - 1 );
    if ( solution_found ) {
      any_stored = TRUE;
      stored_length = solution_length;
      for ( i = 0; i < solution_length; i++ )
	stored_solution[i] = history[i];
      upper_bound = solution_length;
      solution_found = FALSE;
#ifdef VERBOSE
      stop_time = get_timer();
      printf( "%d-move solution found (%ld nodes visited in %.2f s):\n",
	      solution_length, node_count,
	      stop_time - program_start_time );
      print_solution( stored_solution, stored_length );
#endif
    }
    else {
      if ( search_bound + 1 > lower_bound )
	lower_bound = search_bound + 1;
      search_bound++;
    }
  } while ( (lower_bound != upper_bound) && !timeout ) ;

  stop_time = get_timer();

#ifdef VERBOSE
  if ( timeout )
    printf( "Search timed out\n" );
  printf( "\n%lu nodes visited in %.2f s", node_count,
	  stop_time - program_start_time );
  if ( stop_time - program_start_time > 0.01 )
    printf( " = %.0f nodes/second", node_count /
	    (stop_time - program_start_time) );
  puts( "" );
  if ( hash_probe_count > 0 )
    printf( "%lu / %lu = %.1f%% search hash table hits / probes\n",
	    hash_hit_count, hash_probe_count,
	    (100.0 * hash_hit_count) / hash_probe_count );
  puts( "" );
#endif

  if ( any_stored )
    print_solution( stored_solution, stored_length );
  else
    puts( "NO SOLUTION" );

  return EXIT_SUCCESS;
}