/*
  This program is to solve PUSH_BON!
  1994.04.22-24 by M.Kamada
  1994.05.25 speed up
  1994.06.03 reversed tracing
  1994.06.21-22 complete tracing
  1994.06.28 tune up
  1994.07.20-25 optimize path
*/

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

#ifndef __GNUC__
# define inline
#endif

#define STONE_STAR   'S'
#define STONE_NORMAL 'N'
#define STONE_LEFT   'L'
#define STONE_RIGHT  'R'
#define STONE_SPACE  '.'
#define STONE_WALL   'W'
#define STONE_PLAYER 'P'

typedef unsigned char stone;

#define FSCANF_STONE(fp,x) (fscanf(fp, "%1c", &(x)))
#define PRINTF_STONE(x)    (printf("%c", (x)))

#define M_USAGE          "usage: %s map-file-name max-try max-bound\n"
#define M_MAP_FILE       "map-file: %s\n"
#define M_MAX_TRY        "max-try: %d\n"
#define M_MAX_BOUND      "max-bound: %d\n"
#define M_MAX_TRY_ERR    "%s: max-try error\n"
#define M_MAX_BOUND_ERR  "%s: max-bound error\n"
#define M_QUESTION       "question:\n"
#define M_ALLOC_ERR      "can't allocate memory\n"
#define M_TRY_IN         "try in %d\n"
#define M_CANT_IN        "can't solve in %d\n"
#define M_SOLVED_IN      "\nsolved in %d\n"
#define M_BACK_TRACE     "\nback-tracing\n"
#define M_ALLOC_SIZE     "allocate memory: %d\n"
#define M_PAT_OVERFLOW   "pattern table overflow\n"
#define M_PATTERN        "pattern count: %d\n"
#define M_UPDATE_MAX_TRY "update max-try to %d\n"
#define M_UPDATE_NPAT    "update npat to %d\n"
#define M_FOUND_MAX_TRY  "found max try: %d\n"

#define M_FILE_NOT_FOUND       "load_map: file not found (%s)\n"
#define M_UNEXPECTED_EOF       "load_map: unexpected end-of-file (%d,%d)\n"
#define M_MAP_FORMAT_ERROR     "load_map: map format error (%d,%d)\n"
#define M_WALL_REQUIRED        "load_map: wall required (%d,%d)\n"
#define M_TOO_MANY_STAR_BLOCKS "load_map: too many star-blocks (%d,%d)\n"
#define M_TOO_MANY_PLAYERS     "load_map: too many players (%d,%d)\n"
#define M_UNKNOWN_CHARACTER    "load_map: unknown character (%d,%d)\n"
#define M_LINE_IS_TOO_LONG     "load_map: line is too long (%d)\n"
#define M_MISSING_PLAYERS      "load_map: missing players\n"
#define M_MISSING_STAR_BLOCKS  "load_map: missing star-blocks\n"

#define M_MOVABLE_STAR_BLOCKS   "movable star-blocks: %d (%d)\n"
#define M_MOVABLE_NORMAL_BLOCKS "      normal-blocks: %d (%d)\n"
#define M_MOVABLE_LEFT_BLOCKS   "        left-blocks: %d (%d)\n"
#define M_MOVABLE_RIGHT_BLOCKS  "       right-blocks: %d (%d)\n"
#define M_MOVABLE_BLOCKS        "movable  all-blocks: %d\n"

#define SIZE_X  9
#define SIZE_Y  9
#define SIZE_XY (SIZE_X * SIZE_Y)

#define V_LEFT  (-1)
#define V_RIGHT 1
#define V_UP    (-SIZE_X)
#define V_DOWN  SIZE_X

#define MAX_BOUND 10

#define MAX_TRY 10000

#define MAX_REC (MAX_BOUND * MAX_TRY)

#ifndef MAX_PAT
# define MAX_PAT 15000000
#endif

typedef struct {
  char *next;
  char *prev;
  char c[1];
} pat;

#define PAT_HEAD  (sizeof(char *) * 2)

#define PTR_MASK (sizeof(char *) - 1)

#define HASH_BITS 16
#define HASH_SIZE (1<<HASH_BITS)
#define HASH_MASK (HASH_SIZE-1)

char *htbl[HASH_SIZE];

enum {
  STAR, NORMAL, LEFT, RIGHT, SPACE, WALL, PLAYER
};

stone char_to_stone[7] = {
  STONE_STAR,
  STONE_NORMAL,
  STONE_LEFT,
  STONE_RIGHT,
  STONE_SPACE,
  STONE_WALL,
  STONE_PLAYER
};

char bcnt[4];    /* number of each stones */
char ofst[5];    /* offset of each kind of stone */
int psiz;        /* size of pattern record aligned to sizeof(char *) */
char cpat[128];  /* current pattern */
char *pats;      /* allocated pointer of pattern records */
char *npat;      /* pointer of next free pattern record */
int patcnt;      /* number of pattern records */
int stones;      /* number of stones */

char *rpat[MAX_TRY];  /* pointer to record of each time */

char map[SIZE_XY];  /* current map */

int max_try = MAX_TRY;
int max_bound = MAX_BOUND;
int try;
int pxy;

typedef struct {
  char c;   /* block */
  int xy1;  /* axis before move */
  int xy2;  /* axis after move */
} record;

record rec[MAX_REC];
record *currec;

inline int hash();
inline int equal_cpat();
inline void new_cpat();
inline int store_cpat();
inline void move_player();
inline void cpat_move();
inline int record_move();
inline void recur_move();
inline void move();
void push_left();
void push_right();
void push_up();
void push_down();
int move_normal_left();
int move_normal_right();
int move_normal_up();
int move_normal_down();
int move_left_left();
int move_left_right();
int move_left_up();
int move_left_down();
int move_right_left();
int move_right_right();
int move_right_up();
int move_right_down();
inline int check_star();
int move_star_left();
int move_star_right();
int move_star_up();
int move_star_down();
void touch_file();
void print_map();
void print_map2();
int load_map();
void solved2();
void solved();
void set_player();
void init_hash();
void init_cpat();
void main();

/* get hash value of current pattern */
inline int hash()
{
  char *p = cpat;   /* current pattern */
  int  h = 0;       /* hash value */
  int  i = stones;  /* number of stones */

  while (i--) {
    h = (h * 4 + *p) * (h + *p);
    p++;
  }

  return (h ^ (h / HASH_SIZE)) & HASH_MASK;
}

/* check equalily to current pattern */
inline int equal_cpat(pa)
     char *pa;
{
  char *p = cpat;            /* current pattern */
  char *q = ((pat *)pa)->c;  /* any recorded pattern */
  int  i = stones;           /* number of stones */

  while (i--) {
    if (*p++ != *q++) {
      return 0;  /* different pattern */
    }
  }
  return 1;  /* same pattern */
}

/* create new pattern record */
inline void new_cpat(pre)
     char *pre;
{
  char *p = cpat;              /* current pattern */
  char *q = ((pat *)npat)->c;  /* any recorded pattern */
  int  i;                      /* number of stones */

  if (++patcnt > MAX_PAT) {
    printf(M_PAT_OVERFLOW);
    exit(1);
  }

  ((pat *)npat)->next = NULL;
  ((pat *)npat)->prev = pre;

  i = stones;
  while (i--) {
    *q++ = *p++;  /* copy current pattern to record */
  }

  npat += psiz;  /* increment pattern address */
}

char *tpat;
int ttry;

/* store current pattern to record */
inline int store_cpat()
{
  char *p;
  char *q;
  char *r = rpat[try - 1];
  int  h = hash();  /* hash value */

  if ((p = htbl[h]) == NULL) {
    htbl[h] = npat;
    rpat[try] = npat;
    tpat = npat;
    ttry = try;
    new_cpat(r);
    return 1;
  }

  while (p != NULL) {
    if (equal_cpat(p)) {  /* found same pattern */
      int  t = 0;  /* try count of found pattern */
      q = p;
      while (q != NULL) {
	t++;
	q = ((pat *)q)->prev;
      }
      tpat = p;
      if (try < t) {
	ttry = try;
	((pat *)p)->prev = r;  /* update previous pattern */
      } else {
	ttry = t;
      }
      return 0;
    }
    q = p;
    p = ((pat *)p)->next;
  }

  rpat[try] = ((pat *)q)->next = npat;
  tpat = npat;
  ttry = try;
  new_cpat(r);
  return 1;
}

inline void move_player(xy)
     int xy;
{
  if (xy == pxy) {
    return;
  }

  currec->c = map[xy] = PLAYER;
  map[pxy] = SPACE;
  currec->xy1 = pxy;
  currec->xy2 = xy;
  currec++;
  pxy = xy;
}

inline void cpat_move(xy1, xy2)
     int xy1;
     int xy2;
{
  int i;

  if ((i = map[xy1]) < 4) {
    char *p = cpat + ofst[i], *q, *r;
    char w[128];
    int n = bcnt[i] - 1, i;

    i = n;
    q = p;
    r = w;
    while (i && *q < xy1) {
      *r++ = *q++;
      i--;
    }
    q++;
    while (i--) {
      *r++ = *q++;
    }

    i = n;
    q = p;
    r = w;
    while (i && *r < xy2) {
      *q++ = *r++;
      i--;
    }
    *q++ = xy2;
    while (i--) {
      *q++ = *r++;
    }
  }
}

inline int record_move(xy1, xy2)
     int xy1;
     int xy2;
{
  if (xy1 == xy2) {
    return 0;
  }

  cpat_move(xy1, xy2);

  currec->c = map[xy2] = map[xy1];
  map[xy1] = SPACE;
  currec->xy1 = xy1;
  currec->xy2 = xy2;
  currec++;
  return 1;
}

inline void recur_move()
{
  int xy1, xy2;

  currec--;
  xy1 = currec->xy1;
  xy2 = currec->xy2;

  cpat_move(xy2, xy1);

  if ((map[xy1] = currec->c) == PLAYER) {
    pxy = xy1;
  }
  map[xy2] = SPACE;
}

inline void move()
{
  char m[SIZE_XY];
  int xy = SIZE_Y * SIZE_X;

  while (xy--) {
    m[xy] = 0;
  }

  m[pxy] = 1;
#ifdef REVERSE
  push_down(pxy + V_DOWN, m);
  push_up(pxy + V_UP, m);
  push_right(pxy + V_RIGHT, m);
  push_left(pxy + V_LEFT, m);
#else
  push_left(pxy + V_LEFT, m);
  push_right(pxy + V_RIGHT, m);
  push_up(pxy + V_UP, m);
  push_down(pxy + V_DOWN, m);
#endif
}

void push_left(xy, m)
     int xy;
     char *m;
{
  int f;
  record *c0;

  switch (map[xy]) {
  case SPACE:
    if (!m[xy]) {
      m[xy] = 1;
#ifdef REVERSE
      push_down(xy + V_DOWN, m);
      push_up(xy + V_UP, m);
      push_left(xy + V_LEFT, m);
#else
      push_left(xy + V_LEFT, m);
      push_up(xy + V_UP, m);
      push_down(xy + V_DOWN, m);
#endif
    }
    return;
  case NORMAL:
    c0 = currec;
    move_player(xy - V_LEFT);
    f = move_normal_left(xy, 0);
    break;
  case STAR:
    c0 = currec;
    move_player(xy - V_LEFT);
    f = move_star_left(xy, 0);
    break;
  case LEFT:
    c0 = currec;
    move_player(xy - V_LEFT);
    f = move_left_left(xy, 0);
    break;
  case RIGHT:
    c0 = currec;
    move_player(xy - V_LEFT);
    f = move_right_left(xy, 0);
    break;
  default:
    return;
  }
  if (f > 0) {
    if (store_cpat() && try < max_try) {
      try++;
      move();
      try--;
    }
  } else if (f < 0) {
    solved2();
  }
  while (currec != c0) {
    recur_move();
  }
}

void push_right(xy, m)
     int xy;
     char *m;
{
  int f;
  record *c0;

  switch (map[xy]) {
  case SPACE:
    if (!m[xy]) {
      m[xy] = 1;
#ifdef REVERSE
      push_down(xy + V_DOWN, m);
      push_up(xy + V_UP, m);
      push_right(xy + V_RIGHT, m);
#else
      push_right(xy + V_RIGHT, m);
      push_up(xy + V_UP, m);
      push_down(xy + V_DOWN, m);
#endif
    }
    return;
  case NORMAL:
    c0 = currec;
    move_player(xy - V_RIGHT);
    f = move_normal_right(xy, 0);
    break;
  case STAR:
    c0 = currec;
    move_player(xy - V_RIGHT);
    f = move_star_right(xy, 0);
    break;
  case LEFT:
    c0 = currec;
    move_player(xy - V_RIGHT);
    f = move_left_right(xy, 0);
    break;
  case RIGHT:
    c0 = currec;
    move_player(xy - V_RIGHT);
    f = move_right_right(xy, 0);
    break;
  default:
    return;
  }
  if (f > 0) {
    if (store_cpat() && try < max_try) {
      try++;
      move();
      try--;
    }
  } else if (f < 0) {
    solved2();
  }
  while (currec != c0) {
    recur_move();
  }
}

void push_up(xy, m)
     int xy;
     char *m;
{
  int f;
  record *c0;

  switch (map[xy]) {
  case SPACE:
    if (!m[xy]) {
      m[xy] = 1;
#ifdef REVERSE
      push_up(xy + V_UP, m);
      push_right(xy + V_RIGHT, m);
      push_left(xy + V_LEFT, m);
#else
      push_left(xy + V_LEFT, m);
      push_right(xy + V_RIGHT, m);
      push_up(xy + V_UP, m);
#endif
    }
    return;
  case NORMAL:
    c0 = currec;
    move_player(xy - V_UP);
    f = move_normal_up(xy, 0);
    break;
  case STAR:
    c0 = currec;
    move_player(xy - V_UP);
    f = move_star_up(xy, 0);
    break;
  case LEFT:
    c0 = currec;
    move_player(xy - V_UP);
    f = move_left_up(xy, 0);
    break;
  case RIGHT:
    c0 = currec;
    move_player(xy - V_UP);
    f = move_right_up(xy, 0);
    break;
  default:
    return;
  }
  if (f > 0) {
    if (store_cpat() && try < max_try) {
      try++;
      move();
      try--;
    }
  } else if (f < 0) {
    solved2();
  }
  while (currec != c0) {
    recur_move();
  }
}

void push_down(xy, m)
     int xy;
     char *m;
{
  int f;
  record *c0;

  switch (map[xy]) {
  case SPACE:
    if (!m[xy]) {
      m[xy] = 1;
#ifdef REVERSE
      push_down(xy + V_DOWN, m);
      push_right(xy + V_RIGHT, m);
      push_left(xy + V_LEFT, m);
#else
      push_left(xy + V_LEFT, m);
      push_right(xy + V_RIGHT, m);
      push_down(xy + V_DOWN, m);
#endif
    }
    return;
  case NORMAL:
    c0 = currec;
    move_player(xy - V_DOWN);
    f = move_normal_down(xy, 0);
    break;
  case STAR:
    c0 = currec;
    move_player(xy - V_DOWN);
    f = move_star_down(xy, 0);
    break;
  case LEFT:
    c0 = currec;
    move_player(xy - V_DOWN);
    f = move_left_down(xy, 0);
    break;
  case RIGHT:
    c0 = currec;
    move_player(xy - V_DOWN);
    f = move_right_down(xy, 0);
    break;
  default:
    return;
  }
  if (f > 0) {
    if (store_cpat() && try < max_try) {
      try++;
      move();
      try--;
    }
  } else if (f < 0) {
    solved2();
  }
  while (currec != c0) {
    recur_move();
  }
}

int move_normal_left(bxy, n)
     int bxy;
     int n;
{
  char c;
  int xy = bxy;
  int z;

  if (n >= max_bound) {
    return 0;
  }
  while ((c = map[xy += V_LEFT]) == SPACE) {
    ;
  }
  xy -= V_LEFT;
  z = record_move(bxy, xy);
  switch (c) {
  case LEFT:
    return z | move_normal_down(xy, n + 1);
  case RIGHT:
    return z | move_normal_up(xy, n + 1);
  }
  return z;
}

int move_normal_right(bxy, n)
     int bxy;
     int n;
{
  char c;
  int xy = bxy;
  int z;

  if (n >= max_bound) {
    return 0;
  }
  while ((c = map[xy += V_RIGHT]) == SPACE) {
    ;
  }
  xy -= V_RIGHT;
  z = record_move(bxy, xy);
  switch (c) {
  case LEFT:
    return z | move_normal_up(xy, n + 1);
  case RIGHT:
    return z | move_normal_down(xy, n + 1);
  }
  return z;
}

int move_normal_up(bxy, n)
     int bxy;
     int n;
{
  char c;
  int xy = bxy;
  int z;

  if (n >= max_bound) {
    return 0;
  }
  while ((c = map[xy += V_UP]) == SPACE) {
    ;
  }
  xy -= V_UP;
  z = record_move(bxy, xy);
  switch (c) {
  case LEFT:
    return z | move_normal_left(xy, n + 1);
  case RIGHT:
    return z | move_normal_right(xy, n + 1);
  }
  return z;
}

int move_normal_down(bxy, n)
     int bxy;
     int n;
{
  char c;
  int xy = bxy;
  int z;

  if (n >= max_bound) {
    return 0;
  }
  while ((c = map[xy += V_DOWN]) == SPACE) {
    ;
  }
  xy -= V_DOWN;
  z = record_move(bxy, xy);
  switch (c) {
  case LEFT:
    return z | move_normal_right(xy, n + 1);
  case RIGHT:
    return z | move_normal_left(xy, n + 1);
  }
  return z;
}

int move_left_left(lxy, n)
     int lxy;
     int n;
{
  char c;
  int xy = lxy;
  int z;

  if (n >= max_bound) {
    return 0;
  }
  while ((c = map[xy += V_LEFT]) == SPACE) {
    ;
  }
  z = record_move(lxy, xy - V_LEFT);
  switch (c) {
  case NORMAL:
    return z | move_normal_down(xy, n + 1);
  case LEFT:
    return z | move_left_down(xy, n + 1);
  case RIGHT:
    return z | move_right_down(xy, n + 1);
  case STAR:
    return z | move_star_down(xy, n + 1);
  }
  return z;
}

int move_left_right(lxy, n)
     int lxy;
     int n;
{
  char c;
  int xy = lxy;
  int z;

  if (n >= max_bound) {
    return 0;
  }
  while ((c = map[xy += V_RIGHT]) == SPACE) {
    ;
  }
  z = record_move(lxy, xy - V_RIGHT);
  switch (c) {
  case NORMAL:
    return z | move_normal_up(xy, n + 1);
  case LEFT:
    return z | move_left_up(xy, n + 1);
  case RIGHT:
    return z | move_right_up(xy, n + 1);
  case STAR:
    return z | move_star_up(xy, n + 1);
  }
  return z;
}

int move_left_up(lxy, n)
     int lxy;
     int n;
{
  char c;
  int xy = lxy;
  int z;

  if (n >= max_bound) {
    return 0;
  }
  while ((c = map[xy += V_UP]) == SPACE) {
    ;
  }
  z = record_move(lxy, xy - V_UP);
  switch (c) {
  case NORMAL:
    return z | move_normal_left(xy, n + 1);
  case LEFT:
    return z | move_left_left(xy, n + 1);
  case RIGHT:
    return z | move_right_left(xy, n + 1);
  case STAR:
    return z | move_star_left(xy, n + 1);
  }
  return z;
}

int move_left_down(lxy, n)
     int lxy;
     int n;
{
  char c;
  int xy = lxy;
  int z;

  if (n >= max_bound) {
    return 0;
  }
  while ((c = map[xy += V_DOWN]) == SPACE) {
    ;
  }
  z = record_move(lxy, xy - V_DOWN);
  switch (c) {
  case NORMAL:
    return z | move_normal_right(xy, n + 1);
  case LEFT:
    return z | move_left_right(xy, n + 1);
  case RIGHT:
    return z | move_right_right(xy, n + 1);
  case STAR:
    return z | move_star_right(xy, n + 1);
  }
  return z;
}

int move_right_left(rxy, n)
     int rxy;
     int n;
{
  char c;
  int xy = rxy;
  int z;

  if (n >= max_bound) {
    return 0;
  }
  while ((c = map[xy += V_LEFT]) == SPACE) {
    ;
  }
  z = record_move(rxy, xy - V_LEFT);
  switch (c) {
  case NORMAL:
    return z | move_normal_up(xy, n + 1);
  case LEFT:
    return z | move_left_up(xy, n + 1);
  case RIGHT:
    return z | move_right_up(xy, n + 1);
  case STAR:
    return z | move_star_up(xy, n + 1);
  }
  return z;
}

int move_right_right(rxy, n)
     int rxy;
     int n;
{
  char c;
  int xy = rxy;
  int z;

  if (n >= max_bound) {
    return 0;
  }
  while ((c = map[xy += V_RIGHT]) == SPACE) {
    ;
  }
  z = record_move(rxy, xy - V_RIGHT);
  switch (c) {
  case NORMAL:
    return z | move_normal_down(xy, n + 1);
  case LEFT:
    return z | move_left_down(xy, n + 1);
  case RIGHT:
    return z | move_right_down(xy, n + 1);
  case STAR:
    return z | move_star_down(xy, n + 1);
  }
  return z;
}

int move_right_up(rxy, n)
     int rxy;
     int n;

{
  char c;
  int xy = rxy;
  int z;

  if (n >= max_bound) {
    return 0;
  }
  while ((c = map[xy += V_UP]) == SPACE) {
    ;
  }
  z = record_move(rxy, xy - V_UP);
  switch (c) {
  case NORMAL:
    return z | move_normal_right(xy, n + 1);
  case LEFT:
    return z | move_left_right(xy, n + 1);
  case RIGHT:
    return z | move_right_right(xy, n + 1);
  case STAR:
    return z | move_star_right(xy, n + 1);
  }
  return z;
}

int move_right_down(rxy, n)
     int rxy;
     int n;
{
  char c;
  int xy = rxy;
  int z;

  if (n >= max_bound) {
    return 0;
  }
  while ((c = map[xy += V_DOWN]) == SPACE) {
    ;
  }
  z = record_move(rxy, xy - V_DOWN);
  switch (c) {
  case NORMAL:
    return z | move_normal_left(xy, n + 1);
  case LEFT:
    return z | move_left_left(xy, n + 1);
  case RIGHT:
    return z | move_right_left(xy, n + 1);
  case STAR:
    return z | move_star_left(xy, n + 1);
  }
  return z;
}

inline int check_star(xy)
     int xy;
{
  if (map[xy + V_LEFT] == STAR) {
    if (map[xy + V_LEFT + V_LEFT] == STAR || map[xy + V_RIGHT] == STAR) {
      return -1;
    }
  }
  if (map[xy + V_RIGHT] == STAR &&
      map[xy + V_RIGHT + V_RIGHT] == STAR) {
    return -1;
  }
  if (map[xy + V_UP] == STAR) {
    if (map[xy + V_UP + V_UP] == STAR || map[xy + V_DOWN] == STAR) {
      return -1;
    }
  }
  if (map[xy + V_DOWN] == STAR &&
      map[xy + V_DOWN + V_DOWN] == STAR) {
    return -1;
  }
  return 0;
}

int move_star_left(sxy, n)
     int sxy;
     int n;
{
  char c;
  int xy = sxy;
  int z;

  if (n >= max_bound) {
    return check_star(xy);
  }
  while ((c = map[xy += V_LEFT]) == SPACE) {
    ;
  }
  xy -= V_LEFT;
  z = record_move(sxy, xy);
  switch (c) {
  case LEFT:
    return z | move_star_down(xy, n + 1);
  case RIGHT:
    return z | move_star_up(xy, n + 1);
  }
  return z | check_star(xy);
}

int move_star_right(sxy, n)
     int sxy;
     int n;
{
  char c;
  int xy = sxy;
  int z;

  if (n >= max_bound) {
    return check_star(xy);
  }
  while ((c = map[xy += V_RIGHT]) == SPACE) {
    ;
  }
  xy -= V_RIGHT;
  z = record_move(sxy, xy);
  switch (c) {
  case LEFT:
    return z | move_star_up(xy, n + 1);
  case RIGHT:
    return z | move_star_down(xy, n + 1);
  }
  return z | check_star(xy);
}

int move_star_up(sxy, n)
     int sxy;
     int n;
{
  char c;
  int xy = sxy;
  int z;

  if (n >= max_bound) {
    return check_star(xy);
  }
  while ((c = map[xy += V_UP]) == SPACE) {
    ;
  }
  xy -= V_UP;
  z = record_move(sxy, xy);
  switch (c) {
  case LEFT:
    return z | move_star_left(xy, n + 1);
  case RIGHT:
    return z | move_star_right(xy, n + 1);
  }
  return z | check_star(xy);
}

int move_star_down(sxy, n)
     int sxy;
     int n;
{
  char c;
  int xy = sxy;
  int z;

  if (n >= max_bound) {
    return check_star(xy);
  }
  while ((c = map[xy += V_DOWN]) == SPACE) {
    ;
  }
  xy -= V_DOWN;
  z = record_move(sxy, xy);
  switch (c) {
  case LEFT:
    return z | move_star_right(xy, n + 1);
  case RIGHT:
    return z | move_star_left(xy, n + 1);
  }
  return z | check_star(xy);
}

void touch_file(s, n)
     char *s;
     int n;
{
  char w[256];
  FILE *fp;

  sprintf(w, s, n);
  if ((fp = fopen(w, "wt")) != NULL) {
    fclose(fp);
  }
}

void print_map()
{
  int x, y;

  for (y = 0; y < SIZE_Y; y++) {
    for (x = 0; x < SIZE_X; x++) {
      PRINTF_STONE(char_to_stone[(int)(map[y * SIZE_X + x])]);
    }
    printf("\n");
  }
  printf("\n");
}

void print_map2(p)
     char *p;
{
  int x, y, xy = SIZE_XY;
  char *q = ((pat *)p)->c;
  char map2[SIZE_XY];
  int i, j;

  while (xy--) {
    if ((map2[xy] = map[xy]) < 4) {
      map2[xy] = SPACE;
    } else if (map2[xy] == PLAYER) {
      map2[xy] = SPACE;
    }
  }
  for (j = 0; j < 4; j++) {
    for (i = 0; i < bcnt[j]; i++) {
      map2[*q++] = j;
    }
  }
  for (y = 0; y < SIZE_Y; y++) {
    for (x = 0; x < SIZE_X; x++) {
      PRINTF_STONE(char_to_stone[map2[y * SIZE_X + x]]);
    }
    printf("\n");
  }
  printf("\n");
}

int load_map(fn)
     char *fn;
{
  FILE *fp;
  int x, y;
  int kp = 0, ks = 0, kf = 0;
  char ch;
  stone st;

  bcnt[STAR] = bcnt[NORMAL] = bcnt[LEFT] = bcnt[RIGHT] = 0;

  if ((fp = fopen(fn, "rt")) == NULL) {
    fprintf(stderr, M_FILE_NOT_FOUND, fn);
    return 1;
  }

  for (y = 0; y < SIZE_Y; y++) {
    for (x = 0; x < SIZE_X; x++) {
      if (feof(fp)) {
	fprintf(stderr, M_UNEXPECTED_EOF, x, y);
	kf = 1;
	break;
      }
      if (FSCANF_STONE(fp, st) != 1) {
	fprintf(stderr, M_MAP_FORMAT_ERROR, x, y);
	kf = 1;
	break;
      }
      if (x == 0 || x == 8 || y == 0 || y == 8) {
	if (st != STONE_WALL) {
	  fprintf(stderr, M_WALL_REQUIRED, x, y);
	  kf = 1;
	  break;
	}
	map[y * SIZE_X + x] = WALL;
      } else {
	char c;
	switch (st) {
	case STONE_STAR:
	  c = STAR;
	  bcnt[STAR]++;
	  if (ks++ < 3) {
	    break;
	  }
	  fprintf(stderr, M_TOO_MANY_STAR_BLOCKS, x, y);
	  kf = 1;
	  break;
	case STONE_NORMAL:
	  c = NORMAL;
	  bcnt[NORMAL]++;
	  break;
	case STONE_LEFT:
	  c = LEFT;
	  bcnt[LEFT]++;
	  break;
	case STONE_RIGHT:
	  c = RIGHT;
	  bcnt[RIGHT]++;
	  break;
	case STONE_SPACE:
	  c = SPACE;
	  break;
	case STONE_WALL:
	  c = WALL;
	  break;
	case STONE_PLAYER:
	  c = PLAYER;
	  if (!kp) {
	    kp = 1;
	    break;
	  }
	  fprintf(stderr, M_TOO_MANY_PLAYERS, x, y);
	  kf = 1;
	  break;
	default:
	  fprintf(stderr, M_UNKNOWN_CHARACTER, x, y);
	  kf = 1;
	  c = SPACE;
	}
	map[y * SIZE_X + x] = c;
      }
      if (kf) {
	break;
      }
    }
    if (fscanf(fp, "%1c", &ch) != 1 || ch != '\n') {
      fprintf(stderr, M_LINE_IS_TOO_LONG, y);
      kf = 1;
    }
    if (kf) {
      break;
    }
  }

  fclose(fp);

  if (!kf && kp < 1) {
    fprintf(stderr, M_MISSING_PLAYERS);
    kf = 1;
  }

  if (!kf && ks < 3) {
    fprintf(stderr, M_MISSING_STAR_BLOCKS);
    kf = 1;
  }

  if (!kf) {
    int i;
    ofst[0] = 0;
    for (i = 0; i < 4; i++) {
      ofst[i + 1] = ofst[i] + bcnt[i];
    }
    stones = ofst[4];
  }

  return kf;
}

void solved2()
{
  char *p;

  store_cpat();

  printf(M_SOLVED_IN, ttry);

  p = tpat;
  while (p != NULL) {
    print_map2(p);
    p = ((pat *)p)->prev;
  }
}

void solved()
{
  char wp[128];
  char wm[SIZE_XY];
  int xy, i;
  record *wc = currec;

  for (xy = 0; xy < SIZE_XY; xy++) {
    wm[xy] = map[xy];
  }
  for (i = 0; i < stones; i++) {
    wp[i] = cpat[i];
  }
  printf(M_SOLVED_IN, try);

  printf(M_BACK_TRACE);
  print_map();
  while (currec != rec) {
    recur_move();
    print_map();
  }

  for (xy = 0; xy < SIZE_XY; xy++) {
    map[xy] = wm[xy];
  }
  for (i = 0; i < stones; i++) {
    cpat[i] = wp[i];
  }
  currec = wc;
}

void set_player()
{
  int xy = SIZE_XY;

  while (xy--) {
    if (map[xy] == PLAYER) {
      pxy = xy;
      break;
    }
  }
}

void init_hash()
{
  int i = HASH_SIZE;
  char **p = htbl;

  while (i--) {
    *p++ = NULL;
  }
}

void init_cpat()
{
  int i;
  char c_ofst[4];
  int xy;

  c_ofst[0] = 0;
  c_ofst[1] = 0;
  c_ofst[2] = 0;
  c_ofst[3] = 0;
  for (xy = 0; xy < SIZE_XY; xy++) {
    if ((i = map[xy]) < 4) {
      cpat[ofst[i] + c_ofst[i]] = xy;
      c_ofst[i]++;
    }
  }
}

void main(argc, argv)
     int argc;
     char *argv[];
{
  int t;

  switch (argc) {
  case 4:
    if (sscanf(argv[3], "%u", &t) == 1 && t <= MAX_BOUND) {
      max_bound = t;
    } else {
      fprintf(stderr, M_MAX_BOUND_ERR, argv[0]);
      exit(1);
    }
  case 3:
    if (sscanf(argv[2], "%u", &t) == 1 && t <= MAX_TRY) {
      max_try = t;
    } else {
      fprintf(stderr, M_MAX_TRY_ERR, argv[0]);
      exit(1);
    }
  case 2:
    if (load_map(argv[1])) {
      exit(1);
    }
    break;
  default:
    printf(M_USAGE, argv[0]);
    exit(1);
  }

  printf(M_MAP_FILE, argv[1]);
  printf(M_MAX_TRY, max_try);
  printf(M_MAX_BOUND, max_bound);
  printf("\n");

  printf(M_QUESTION);
  print_map();

  fprintf(stderr, M_MOVABLE_STAR_BLOCKS,   bcnt[0], ofst[0]);
  fprintf(stderr, M_MOVABLE_NORMAL_BLOCKS, bcnt[1], ofst[1]);
  fprintf(stderr, M_MOVABLE_LEFT_BLOCKS,   bcnt[2], ofst[2]);
  fprintf(stderr, M_MOVABLE_RIGHT_BLOCKS,  bcnt[3], ofst[3]);
  fprintf(stderr, M_MOVABLE_BLOCKS, stones);
  fprintf(stderr, "\n");

  psiz = (PAT_HEAD + stones + PTR_MASK) & ~PTR_MASK;
  fprintf(stderr, M_ALLOC_SIZE, psiz * MAX_PAT);
  if ((pats = malloc(psiz * MAX_PAT)) == NULL) {
    fprintf(stderr, M_ALLOC_ERR);
    exit(1);
  }
  npat = pats;
  init_hash();
  init_cpat();
  patcnt = 0;
  set_player();
  currec = rec;
  try = 1;
  rpat[0] = NULL;
  store_cpat();

  move();

  printf(M_PATTERN, (int)((long int)npat - (long int)pats) / psiz);
}