/* POTM ENTRY : shufflemania            */
/* Author : Stan Peijffers              */
/* E-mail : s.peijffers@ns-nl.att.com   */

/*
 
Shufflemania is based on hybrid search. It contains 2 search algoritms 
that (recursively) call each other.

The first search algoritm is an Iterative Deepening A* (IDA*) Algorithm.
This is a well known algoritm initially developped by Korf 
(ref Artificial Intelligence 27 (1985)).

It has the following characteristics :

- depth-first search using an evaluation function f*
 
  f* = g* + h*
 
  where g* = number of moves sofar
        h* = (underestimate of the) number of moves to reach goal
           = sum of Manhattan distances
 
- looks for an optimal solution
- does not eliminate duplicate positions
- requires little memory (it is a recursive algoritm that only uses
  stack space)
- rather CPU intensive

The second search algoritm is a variant of the A* algorithm 
(as described in any book on heuristic search).

It has the following characteristics :

- heuristic search using an evaluation function f* that systematically
  overestimates the distance to the goal
  
  f* = g* + a.h*

  where g* = number of moves sofar
        h* = (overestimate of the) number of moves to reach goal
        a  = factor that increases weigth of h* as the search goes deeper.

  Note that the original A* algorithm works with a h* function that
  always UNDERestimates the distance to the goal and has an "a" factor
  that DEcreases the weight of h* as the search goes deeper.

- The advantage of using an h* function that does not have to 
  underestimate the distance to the goal (typically h* is the sum of
  the Manhattan distances) is that the h* function can be tailored
  to steer the search into a particular direction. 
  The h* function used is the following :

  h* = sum over all tiles of "long" distances, 

  where "long" distance is dependent on 
  the number of moves (as opposed to distance) to make to get the
  tile to the goal.

  This dependency takes into account the actual distance to the goal,
  and this dependency is non-linear, such that higher distances 
  are favored more than lower distances. (It is indeed rather wasteful
  to spend time in placing tiles at the correct place when there are
  still many tiles far away from their final place).

  Another dependency which is factored in is the degree of mobility
  of a tile. There are 3 different levels of mobility : corner tiles
  (A,E, etc), border tiles and central tiles. The dependency on the
  h* function is such that corner tiles are more mobile (i.e moved
  more quickly) than border tiles, which are more mobile than
  central tiles. The net result of this is that the algorithm will
  first of all attempt to get corner tiles in place before border
  tiles, before central tiles.

- does not strictly expand nodes on a best-first basis.
- does not use a single queue, rather a set of queues.
- performs a substantial amount of pruning

  + solutions that deviate too much from the best solution sofar
    are pruned.
  + solutions that will not be able to improve on the currently
    best solution are pruned 
    (To this end a second h* function based on Manhattan distances
     is maintained as well, but this second h* function does
     not steer the search. It is only used for pruning).

- When memory becomes full, the most-promising position is used
  as the starting point for a new search.

  As a consequence of the above limitations :
  does not search for optimal solutions 
  (but recognizes an optimal solution when it sees one).

- does not eliminate duplicate positions
  (only avoids sequences of moves that would generate duplicates
   such as lr, du, etc)

- requires a lot of memory for the queues

- prime characteristics of the algoritm are : speed and the possibility
  of generating long sequences of moves leading to (sub)optimal
  solutions.


These 2 algoritms are complementary from a CPU and memory usage
viewpoint. 

The solution that was adopted is a hybrid search based on the above 2 
algoritms where the IDA* algorithm is used at the top of the search
tree and the A* algorithm used at the bottom of the search tree.
This approach has been mentioned in "Heuristics : Intelligent Search
Strategies for Computer Problem Solving" By Judea Pearl.

[Note : an interesting article describing a hybrid search method with
 A* used at the top and IDA* used at the bottom is 
 "Effective use of memory in iterative deepening search" by
 Sarkar, Chakrabarti, Ghose, De Sarkar - Information Processing Letters
 42(1992).]

The depth d0 at which the IDA* algoritm stops and hands over control
to the A* algorithm is fixed and is a linear function of the 
"complexity" of the initial problem (complexity = number of misplaced
tiles). The upperbound for d0 is 30. 
This means that in practice problems with an optimal solution less than or
a little over 30 moves will always be found.

In a number of instances the A* algorithm calls the IDA* algorithm 
(and the associated A* algorithms) again
lower in the search tree. The IDA* algorithm is then called
at the point where the next higher IDA* algorithm was stopped.
This happens in 3 cases :

1. A* detects a new solution which is an improvment over the currently
   best solution. IDA* is called to see whether it is not possible to
   still improve the solution.

2. A* has found too many "promising" intermediate solutions (i.e queue
   overflow). This is an interesting situation in which an IDA* search
   may uncover good solutions. 
   (Note that in "normal" situations the queue overflow will not 
    happen because of the substantial amount of pruning in A*).

3. A* has not found a solution at all. i.e all examined positions 
   are worse than the starting position. 
   This happens e.g in cases where all tiles are in place except
   for 2 that need to be swapped. 

The maximum depth of recursive calls to the IDA* algorithm is limited 
to 4.

Some other characteristics of the program :

- The algorithm stops when the 10 minute limit is reached
  (unless an optimal solution is found by either the IDA* or the
   A* algoritm).
  
  A time check is made at anytime the A* algorithm is started.

- The handover point between IDA* and A* is not exactly d0, but 
  the first "negative" move before d0 is reached. This is done 
  to avoid working with locally optimized solutions detected by
  IDA*.

*/

#include "stdio.h"

#include   /* for the TMS structure */
#define CLK_TCK 100     /* Note: this may be different on YOUR box, you
                           might find the value of HZ in YOUR param.h, but
                           it's gotta be 100 when you ship your entry!
                           Alternatively, use sysconf to deduce CLK_TCK -
                           this approach should work on both systems!    */

/* location of center */
#define center 12

#define LEFT	0
#define RIGHT	1
#define UP	2
#define	DOWN	3
#define TRANS	4

#define SOL_FND 0 	/* solution found */
#define ISOL_FND 1 	/* intermediate solution found */
#define NOSOL_FND 2 	/* no solution found */
#define NBSOL_FND 3 	/* no better solution found */

#define IDA_CONT 0 	/* continue IDA search */
#define IDA_STOP 1	/* stop IDA search */
#define IDA_TOUT 2	/* time out IDA search */

#define PSZ 5 		/* dimension of puzzle */
#define PSIZE 25	/* total size of puzzle */
#define POSSZ 5		/* size of puzzle representation (in words) */

#define NBR_MOVES 5	/* number of moves : lrudt */

#define NBR_PASS 2	/* number of passes */
#define NBR_LVL1 2	/* number of IDA levels (normal case) */
#define NBR_LVL 4	/* number of IDA levels (tricky case) */

#define SOME_HIGH_VAL 30000

#define NREIDA 0 	/* no reiteration of IDA */
#define REIDA1 1	/* reiteration of IDA reason 1 */
#define REIDA2 2	/* reiteration of IDA reason 2 */
#define REIDA3 3	/* reiteration of IDA reason 3 */

#define IDAMK 0		/* IDA position marked */
#define IDANMK 1	/* IDA position not marked */
#define IDAMKDUP 2	/* IDA position marked as a duplicate */

/* heuristics */

#define IDAMAXDP 31	/* depth d0 at which IDA stops */
#define IDAINCDP 10	/* increment to calculate new d0 for
 			   IDA searches lower in the tree */
#define GHPRUN 1000	/* pruning value used in A* algorithm.
			   = max deviation from best solution so far */
#define GHEPS 200	/* factor applied to h* in A* algorithm */
#define GHFVAL 100	/* factor applied to f* in A* algorithm */

/* representation of a "move" in recursive IDA algorithm */

typedef struct tmove {
 struct tmove *mdir_ptr;	/* pointer to previous "move" */
 int mpos[5];			/* representation of current position */
 int mspp;			/* position of space in mpos */
 int mdir;			/* direction by which current position 
				   reached = dulrt */
 int mval;			/* value f* of current position */
 int mmark;			/* mark : position already elaborated
				   by an A* search or not */
 } move;


/* 25x25 table showing Manhattan distances (generated) */

int manhtab[PSIZE*PSIZE] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,2,3,4,1,2,2,3,4,2,2,1,2,3,3,3,2,3,4,4,4,3,4,5,
1,0,1,2,3,2,1,2,3,4,3,2,1,2,3,4,3,2,3,4,5,4,3,4,5,
2,1,0,1,2,3,2,1,2,3,3,2,1,2,3,4,3,2,3,4,5,4,3,4,5,
3,2,1,0,1,4,3,2,1,2,3,2,1,2,3,4,3,2,3,4,5,4,3,4,5,
4,3,2,1,0,4,3,2,2,1,3,2,1,2,2,4,3,2,3,3,5,4,3,4,4,
1,2,3,4,5,0,1,2,3,4,1,2,1,2,3,2,3,2,3,4,3,4,3,4,5,
2,1,2,3,4,1,0,1,2,3,2,1,1,2,3,3,2,2,3,4,4,3,3,4,5,
3,2,1,2,3,2,1,0,1,2,3,2,1,2,3,4,3,2,3,4,5,4,3,4,5,
4,3,2,1,2,3,2,1,0,1,3,2,1,1,2,4,3,2,2,3,5,4,3,3,4,
5,4,3,2,1,4,3,2,1,0,3,2,1,2,1,4,3,2,3,2,5,4,3,4,3,
2,3,3,4,5,1,2,2,3,4,0,1,1,2,3,1,2,2,3,4,2,3,3,4,5,
3,2,3,4,5,2,1,2,3,4,1,0,1,2,3,2,1,2,3,4,3,2,3,4,5,
4,3,2,3,4,3,2,1,2,3,2,1,0,1,2,3,2,1,2,3,4,3,2,3,4,
5,4,3,2,3,4,3,2,1,2,3,2,1,0,1,4,3,2,1,2,5,4,3,2,3,
5,4,3,3,2,4,3,2,2,1,3,2,1,1,0,4,3,2,2,1,5,4,3,3,2,
3,4,3,4,5,2,3,2,3,4,1,2,1,2,3,0,1,2,3,4,1,2,3,4,5,
4,3,3,4,5,3,2,2,3,4,2,1,1,2,3,1,0,1,2,3,2,1,2,3,4,
5,4,3,4,5,4,3,2,3,4,3,2,1,2,3,2,1,0,1,2,3,2,1,2,3,
5,4,3,3,4,4,3,2,2,3,3,2,1,1,2,3,2,1,0,1,4,3,2,1,2,
5,4,3,4,3,4,3,2,3,2,3,2,1,2,1,4,3,2,1,0,5,4,3,2,1,
4,4,3,4,5,3,3,2,3,4,2,2,1,2,3,1,2,2,3,4,0,1,2,3,4,
5,4,3,4,5,4,3,2,3,4,3,2,1,2,3,2,1,2,3,4,1,0,1,2,3,
5,4,3,4,5,4,3,2,3,4,3,2,1,2,3,3,2,1,2,3,2,1,0,1,2,
5,4,3,4,5,4,3,2,3,4,3,2,1,2,3,4,3,2,1,2,3,2,1,0,1};

/* 25x25 table showing long distances (generated by the 
   following algorithm :

#include "stdio.h"

#define min(x,y)        (((x)>(y))?(y):(x))

#define get_x(loc)	((loc) % 5)
#define get_y(loc)	((loc) / 5)
#define indx(x,y)	(((y)*5) + (x))

#define PSIZE 25

int a1[PSIZE] = {
      12,8,4,8,12,8,4,2,4,8,4,2,0,2,4,8,4,2,4,8,12,8,4,8,12};
int a2[3*PSIZE] = 
      {0,0,6,12,18,0,4,8,14,20,6,8,12,16,22,12,14,16,20,24,18,20,22,24,28,
       0,0,5,10,15,0,3,6,11,16,5,6,9,12,17,10,11,12,15,18,15,16,17,18,21,
       0,0,4,8,12,0,2,5,9,13,4,5,7,10,14,8,9,10,12,15,12,13,14,15,17};

int mob[PSIZE] = {2,3,3,3,2,3,4,4,4,3,3,4,4,4,3,3,4,4,4,3,2,3,3,3,2};

#define center 12
#define DIST(loc1,loc2)	(abs(get_x(loc1) - get_x(loc2)) + abs(get_y(loc1) - get_y(loc2)))
#define XDIST(loc1,loc2) (abs(get_x(loc1) - get_x(loc2)))
#define YDIST(loc1,loc2) (abs(get_y(loc1) - get_y(loc2)))

main()
{
int ppos, piece, d1, d2;

for (piece=1; piece < PSIZE; piece++)
{
printf("\n");

for (ppos=0; ppos < PSIZE; ppos ++)
{
   
  d1 = DIST(ppos, piece-1);
  d2 = 0;
 
  if (d1 != 0)
   {
   d1 = a1[ppos]+1;
   d2 = a2[(mob[piece-1]-2)*PSIZE + indx(XDIST(ppos,piece-1),YDIST(ppos,piece-1))];
   d2 += 1;
   }
  printf("%d,", min(d1,d2));

}
}
}
 
*/

int brkltab[PSIZE*PSIZE] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,5,9,13,1,5,3,5,9,5,3,1,3,5,9,5,3,5,9,13,9,5,9,13,
1,0,1,6,11,4,1,3,5,9,5,3,1,3,5,9,5,3,5,9,13,9,5,9,13,
6,1,0,1,6,7,4,1,4,7,5,3,1,3,5,9,5,3,5,9,13,9,5,9,13,
11,6,1,0,1,9,5,3,1,4,5,3,1,3,5,9,5,3,5,9,13,9,5,9,13,
13,9,5,1,0,9,5,3,5,1,5,3,1,3,5,9,5,3,5,9,13,9,5,9,13,
1,4,5,9,13,0,1,3,5,9,1,3,1,3,5,6,5,3,5,9,11,9,5,9,13,
3,1,3,6,10,1,0,1,5,9,3,1,1,3,5,6,5,3,5,9,10,9,5,9,13,
6,3,1,3,6,5,1,0,1,5,5,3,1,3,5,8,5,3,5,8,11,9,5,9,11,
10,6,3,1,3,9,5,1,0,1,5,3,1,1,3,9,5,3,5,6,13,9,5,9,10,
13,9,5,4,1,9,5,3,1,0,5,3,1,3,1,9,5,3,5,6,13,9,5,9,11,
6,7,5,9,13,1,4,3,5,9,0,1,1,3,5,1,4,3,5,9,6,7,5,9,13,
6,5,5,8,11,3,1,3,5,9,1,0,1,3,5,3,1,3,5,9,6,5,5,8,11,
8,6,5,6,8,6,3,1,3,6,5,1,0,1,5,6,3,1,3,6,8,6,5,6,8,
11,8,5,5,6,9,5,3,1,3,5,3,1,0,1,9,5,3,1,3,11,8,5,5,6,
13,9,5,7,6,9,5,3,4,1,5,3,1,1,0,9,5,3,4,1,13,9,5,7,6,
11,9,5,9,13,6,5,3,5,9,1,3,1,3,5,0,1,3,5,9,1,4,5,9,13,
10,9,5,9,13,6,5,3,5,9,3,1,1,3,5,1,0,1,5,9,3,1,3,6,10,
11,9,5,9,11,8,5,3,5,8,5,3,1,3,5,5,1,0,1,5,6,3,1,3,6,
13,9,5,9,10,9,5,3,5,6,5,3,1,1,3,9,5,1,0,1,10,6,3,1,3,
13,9,5,9,11,9,5,3,5,6,5,3,1,3,1,9,5,3,1,0,13,9,5,4,1,
13,9,5,9,13,9,5,3,5,9,5,3,1,3,5,1,5,3,5,9,0,1,5,9,13,
13,9,5,9,13,9,5,3,5,9,5,3,1,3,5,4,1,3,5,9,1,0,1,6,11,
13,9,5,9,13,9,5,3,5,9,5,3,1,3,5,7,4,1,4,7,6,1,0,1,6,
13,9,5,9,13,9,5,3,5,9,5,3,1,3,5,9,5,3,1,4,11,6,1,0,1};

/* 5x25 table representing next positions (generated).
   -1 means : invalid */

int nexttab[5*PSIZE] = {
-1,1,-1,5,12,
0,2,-1,6,12,
1,3,-1,7,12,
2,4,-1,8,12,
3,-1,-1,9,12,
-1,6,0,10,12,
5,7,1,11,12,
6,8,2,12,-1,
7,9,3,13,12,
8,-1,4,14,12,
-1,11,5,15,12,
10,12,6,16,-1,
11,13,7,17,-1,
12,14,8,18,-1,
13,-1,9,19,12,
-1,16,10,20,12,
15,17,11,21,12,
16,18,12,22,-1,
17,19,13,23,12,
18,-1,14,24,12,
-1,21,15,-1,12,
20,22,16,-1,12,
21,23,17,-1,12,
22,24,18,-1,12,
23,-1,19,-1,12 };

int maxtime[NBR_PASS] = {10, 580}; /* time control : one for each pass */
int pass;

int solution[200]; 	/* current best solution */

/* a set of indices pointing to various points in "solution" 
   + counters for the number of transports in each part of 
   "solution" 
*/

int solix; 		/* index to end of ida solution 
			   and begin of A* solution */
int solix_tcnt;		/* number of transports in ida part of solution */

int solval;		/* length of solution (number of moves) */
int soltcnt;		/* number of transports in solution */

int solstart;		/* start of ida solution */
int solst_tcnt;		/* number of transports in part of solution 
			   preceeding start of ida solution */

/* a set of parameters which are used by the IDA algorithm. 
   There is an instance for each recursion level of IDA */

int minnval[NBR_LVL]; 	/* next minimum value for IDA */
int cutoff[NBR_LVL];	/* cutoff value for current iteration of iDA */
int fnd_sol[NBR_LVL]; 	/* minimum number of A* runs */
int maxdepth[NBR_LVL];	/* d0 */

int idalevel; 		/* recursion level of IDA */
 
int tghsol[200]; 	/* place to store (temporarily) the solution 
			   found by A* */

/* representation of a position used by the A* algorithm 
   = same representation as used in the IDA algorithm */
 
typedef struct {
 int compos[POSSZ];
 } tiles;

/* representation of initial position, position of space, and f* value */

int strt_position[POSSZ];
int strt_pos_sp;
int strt_valpos;
 
/* representation of position, position of space, and f* value 
   used at start of each pass */

int position[POSSZ];
int pos_sp;
int valpos;
int lastmove;

int nbr_mpp; 		/* number of misplaced tiles in the initial position */

int locked[PSIZE];	/* array of tiles which are locked during prepass */
                           

#define MAX_NQUE 50	/* maximum number of queues (A* alg) */
#define MAX_SQUE 10000	/* size of a queue (A* alg) */

int que_head[MAX_NQUE];	/* head of queue */
int que_tail[MAX_NQUE];	/* tail of queue */
int prunval[MAX_NQUE];	/* pruning values in each queue */

/* pointers to malloc-ed space for A* queues */

tiles *gh_pos;	/* space for position representations */
int *sp_pos;	/* space for space-positions */
int *feval;	/* space for f* values (f* = g* + a.h*) */
int *heval;	/* space for h* values */
int *geval;	/* space for g* values */
int *mov_dir;	/* space for move directions */
int *prev_que;	/* space for pointers to previous elements */

int start_que;	/* pointer to start of first queue */

int ifile;	/* file descriptor */
int mineval, bstque;	/* value and index of best position (in A* algo) */

int shcnt;	/* number of moves of solution found by A* algo */
int trancnt;	/* number of transports in solution found by A* algo */




main(argc,argv)
int argc;
char **argv;
{
int j;

  /* open input file */
  ifile = open(argv[1], 0);

  /* initialize */
  init_mat();

  /* if all tiles are in place (never know) -> exit */
  if (strt_valpos == 0) exit (0);

  /* calculate d0 for IDA search depth */
  maxdepth[0] = IDAMAXDP - (PSIZE-nbr_mpp+1)/2;

  /* There are 2 passes :
     - an initial pass (in which all correctly placed tiles are locked)
     - the main pass
     The initial pass is just a wild shot whose only purpose is to
     find quick solutions to tricky positions.
     Its effect is limited (but it doesn't hardly cost anything).
  */

  for (pass=((nbr_mpp<=16)?0:1); pass< NBR_PASS; pass++)
   {

    /* initialize position */
    for (j=0; j= maxtime[pass])
            return 1;
return 0;

}

init_mat()
{
int i,j;
char s[6];
int ppos,piece;

/* read input file */
 
for (j=0; j> ((ppos % POSSZ)*5)) & 0x1f)) != 0)
 {
  if (manhtab[piece*PSIZE+ppos] != 0)
   nbr_mpp++;
  else
   locked[ppos] = 1;

  strt_valpos += manhtab[piece*PSIZE+ppos];
 }

/* initialize value of solution to sime high value */

solval = SOME_HIGH_VAL; 
soltcnt = 0;

}


ida_search(pos, spp, oldval, lmove)
int (*pos)[];
int spp;
int oldval;
int lmove;
{
move initdir;
int i,ret;

/* initialize a "move" structure with its initial values */

initdir.mdir = lmove;
initdir.mmark = IDANMK;
initdir.mval = oldval;
initdir.mspp = spp;
for (i=0; immark == IDANMK)
     {
     mdir->mmark = IDAMK;
     if (mdir->mval != oldval)
      {
      break;
      }
     mdir = mdir->mdir_ptr;
     }
    else if (mdir->mmark == IDAMK)
     {
     break;
     }
    else
     {
      return IDA_CONT;
     }
   }


  /* mdir contains the position from which an A* search will be started.
     Mark it.
  */
  mdir->mmark = IDAMKDUP;

  /* depth - j is the length of the resulting intermediate solution
     from IDA.
  */

  idacnt = shcnt = depth-j;
  trancnt = 0;

  /* initialize the queue for the A* search */

  hval = init_que(mdir, solstart+shcnt);
  done = ISOL_FND;
  nbr_ghp=1;
  reida = NREIDA;

  /* The A* search continues as long as intermediate solutions are found */

  while (done == ISOL_FND)
   {

    done = gh_search(&que_in);

    /* A* search did not find a solution better than the current one. Return.*/
    if (done == NBSOL_FND)
     {
     return IDA_CONT;
     }

    /* A* search did not find a solution at all. Prepare an additional 
       IDA search.
    */

    if (done == NOSOL_FND)
        {
         reida = REIDA3;
         for (k=0; kmpos[k];
         pos_sp = mdir->mspp;
         valpos = mdir->mval - idacnt;
         lastmove = mdir->mdir;
         break;
        }

    /* A* search found an intermediate solution. Either
       - reinit the A* queue and restart the A* algorithm, or
       - prepare an additional IDA search, or
       - abandon the search and return
    */

    if (done == ISOL_FND)

      if (fnd_sol[idalevel] > nbr_ghp++)

       {
       sv_ghsol(que_in);
       reinit_que(que_in);
       }

      else
       {

       if (idalevel == 0)
        {
         reida = REIDA2;
         for (k=0; kmpos[k];
         pos_sp = mdir->mspp;
         valpos = mdir->mval - idacnt;
         lastmove = mdir->mdir;
         break;
        }
       else
        return IDA_CONT;
       }

    else
     {
     fnd_sol[idalevel] = nbr_ghp;
     break;
     }
   }
 
  /* temporarily save the A* solution (if there is one) */
  if (reida == REIDA3)
   trancnt = trascnt = 0;
  else
   {
    sv_ghsol(que_in);
    trascnt = trancnt;
   }

  /* count number of transports in the A* solution */
  if ((shcnt + solstart <= solval) || (reida))
   {
   tmdir = mdir;
   for (k=idacnt-1;k>=0;k--)
    {
     if (tmdir->mdir == TRANS)
      trancnt++;
     tmdir = tmdir->mdir_ptr;
    }
   }

  trascnt = trancnt - trascnt;

  /* If the solution found by A* is an improvment over the 
     currently best (either because of less moves, or because of
     less transport moves, then prepare an extra IDA search.
  */

  if (!reida)
  {
  if ((shcnt + solstart < solval) ||
      ((shcnt + solstart == solval) && (trancnt + solst_tcnt < soltcnt)))
   {

    if (shcnt + solstart < solval) 
     reida = REIDA1;

    solix = solstart;
    sv_idasol(mdir, idacnt);
    for (i=idacnt; i mpos[i];
    pos_sp = mdir->mspp;
    valpos = mdir->mval - idacnt;
    lastmove = mdir->mdir;
   }

  /* This check detects optimal solutions from the A* search.
     I.e. when the number of moves from A* is lower or equal to
     the estimated minimal number of moves, 
     then this has to be an optimal solution.
     Therfore, stop the search.
  */

  if (shcnt - idacnt <= hval + oldval - mdir->mval)
   {
    return IDA_STOP; 
   }
   }

  /* This is the time to restart an IDA search as prepared before */

  if (((((reida == REIDA1) && (nbr_ghp <= 1)) || 
        ((reida == REIDA2) && (nbr_ghp <= 2))) && (idalevel < NBR_LVL1-1)) ||
       ((reida == REIDA3) && (idalevel < NBR_LVL-1)))
    {

     solix = solstart;
     solstart += idacnt;
     solst_tcnt += trascnt;

     /* maxdepth (d0) is set to either the d0 value of the outer level
        IDA search (when REIDA3), or to the number of moves that had 
        been backed up from the previous IDA search + some increment
        (when !REIDA3).
     */
     maxdepth[++idalevel] = ((reida == REIDA3)?maxdepth[0]:(j + IDAINCDP));

     /* call IDA search again */
     ret = ida_search(position, pos_sp, valpos, lastmove);
     idalevel--;
     solstart -= idacnt;
     solst_tcnt -= trascnt;

     /* When this new IDA search finds a solution (this is checked by
        comparing solstart (start index of IDA search) and solix 
        (end index of IDA search), for the case REIDA1 the
        previous IDA solution still needs to be stored.
     */

     if ((solix != solstart) && (reida != REIDA1))
       {
       /* still store solution */
       solix = solstart;
       sv_idasol(mdir, idacnt);
       solix = solstart + idacnt;
       solix_tcnt = solst_tcnt + trascnt;
       }

     if (ret == IDA_TOUT) 
       return IDA_TOUT; 
     else /* IDA_STOP */
      if (idalevel < NBR_LVL1-1)
       return IDA_CONT; 
      else
       {
       return IDA_STOP;
       }
    }
   else
     return IDA_CONT;
}

/* The heart of the IDA algorithm */

df_search(pos, spp, oldval, dir, depth)
int (*pos)[];
int spp;
int oldval;
move *dir;
int depth;

{
move movdir, *tmdir;
int newval;
int nspp;
int d12old;
int d12new;
int i,k,ret;
int npiece;
int trascnt;


movdir.mdir_ptr = dir;

/* If d0 reached :
   - check time,
   - call more_search (A* and/or IDA again), only if 
     the current value equals the cutoff value, 
     otherwize the position was already uncovered
     during the previous call of df_search.
*/

if (depth == maxdepth[idalevel])
 {

  if (checktime())
     return IDA_TOUT;

  if (oldval == cutoff[idalevel])
    return more_search(oldval, dir, depth);
   else
    return IDA_CONT;
 }
else
 {

      for (i=0; imdir != TRANS) &&
             (i == (dir->mdir ^ 1)))
          continue;
         
         /* update new position */
 
         npiece = ((movdir.mpos[nspp/POSSZ] >> ((nspp%POSSZ)*5)) & 0x1f);

         movdir.mpos[spp/POSSZ] += (npiece << ((spp%POSSZ)*5));
         movdir.mpos[nspp/POSSZ] &= 
             (0xfe0fffff >> ((4 - (nspp%POSSZ))*5));


         /* calculate new f */

         d12old = manhtab[npiece*PSIZE+nspp];
         d12new = manhtab[npiece*PSIZE+spp];

         newval = oldval + 1 + d12new - d12old;

         /* If new f greater than the cutoff value,
            update the cutoff value for the next iteration
            (when needed), undo the last move and 
            continue with the next one.
         */

         if (newval > cutoff[idalevel])
          {
           if (newval < minnval[idalevel])
            minnval[idalevel] = newval;
           movdir.mpos[nspp/POSSZ] += (npiece << ((nspp%POSSZ)*5));
           movdir.mpos[spp/POSSZ] &=
             (0xfe0fffff >> ((4 - (spp%POSSZ))*5));
 
           continue;
          }

         /* store move information */
         movdir.mdir = i;
         movdir.mval = newval;
         movdir.mmark = IDANMK;
         movdir.mspp = nspp;

         /* check to see whether we found a solution */
         if (newval <= depth+1)
          {
           /* hit the goal */

           /* In this case :
              - save the solution,
              - count the number of transports
              - and stop the search.
           */

           solix = solstart;
           sv_idasol(&movdir, depth+1);
           solval = solix = solstart + depth + 1;

           trascnt = 0;
           tmdir = &movdir;
           for (k=depth;k>=0;k--)
            {
             if (tmdir->mdir == TRANS)
              trascnt++;
             tmdir = tmdir->mdir_ptr;
            }

           solix_tcnt = soltcnt = solst_tcnt + trascnt;

           return IDA_STOP;
          }
 

         /* call df_search recursively from new position */
         ret = df_search(movdir.mpos, nspp, newval, &movdir, depth+1);
 

         if (ret != IDA_CONT) return ret;

         /* restore nposition */

         movdir.mpos[nspp/POSSZ] += (npiece << ((nspp%POSSZ)*5));
         movdir.mpos[spp/POSSZ] &=
             (0xfe0fffff >> ((4 - (spp%POSSZ))*5));
 
       } /* for */
    return IDA_CONT;
   }
}

sv_idasol(mdir, dpth)
move *mdir;
int dpth;
{
int j;
          
           for (j=dpth-1; j>=0; j--)
            {
             solution[solix+j] = mdir->mdir;
             mdir = mdir->mdir_ptr;
            }                                       
     
}

init_que(mdir, gval)
move *mdir;
int gval;

{
int que_entry;
int i,f;
int ppos,piece;
int fval,hval;

/* set all queue pointers to zero */
for (f=0; fmpos[i];

sp_pos[que_entry] = mdir->mspp;

/* calculate f* */
 
fval = hval = 0;
for (ppos=0; ppos< PSIZE; ppos++)
 if ((piece = ((mdir->mpos[ppos / POSSZ] >> ((ppos % POSSZ)*5)) & 0x1f)) != 0)
 {
  hval += manhtab[piece*PSIZE+ppos];
  fval += brkltab[piece*PSIZE+ppos];
 }
 

mov_dir[que_entry] = mdir->mdir;
feval[que_entry] = GHFVAL * fval;
prev_que[que_entry] = 0;
heval[que_entry] = hval;
geval[que_entry] = gval;

/* set low water marks for best positions */
mineval = GHFVAL * fval;
bstque=1;

/* initialize pruning values in all queues to some high value */
for (i=0; i< MAX_NQUE; i++)
 prunval[i] = SOME_HIGH_VAL;

/* add this first element to the queue */
que_head[que_entry]++;
start_que = que_entry;
return hval;
}

reinit_que(que_in)
int que_in;
{
int que_entry,f,i;

/* set all queue pointers to zero */
for (f=0; f= geval[0])
     {
      que_tail[f]++;
      continue;
     }
 
    csp_pos = sp_pos[que_entry]; 

      /* for every possible move (udlrt) */

      for (i=0; i> ((nsp_pos%POSSZ)*5)) & 0x1f);


           d12old = manhtab[npiece*PSIZE+nsp_pos];
           old_d = brkltab[npiece*PSIZE+nsp_pos];
 
           d12new = manhtab[npiece*PSIZE +csp_pos];
           new_d = brkltab[npiece*PSIZE+csp_pos];

           /* calculate new queue */
           new_q = f + 1 + new_d - old_d;

           /* calculate new f* */
           new_f = feval[que_entry] + feval[que_entry]/GHEPS +
             GHFVAL*(new_d -old_d);

           /* did we find a solution (i.e new h* == 0)? */
           if (heval[que_entry] + d12new - d12old == 0)
            {
             /* hooray were done */

             /* If this solution is better or equally good than the
                best so far, count number of transports.
             */

             if (geval[que_entry] < geval[0])
              {

               tque = que_entry;
               trcnt = 0;
               while (prev_que[tque] != 0)
                {
                 if (mov_dir[tque] == TRANS)
                  trcnt++;
                 tque = prev_que[tque];
                }

               if (i== TRANS) trcnt++;
              }
 
             found_sol = 1;

             /* If solution is an improvment, either in terms of number
                of moves, or number of transports,
                store this last queue_entry as queue_entry 0.
             */

             if ((geval[que_entry]+1 < geval[0]) ||
                 ((geval[que_entry]+1 == geval[0]) && (trcnt < trcnt0)))
              { 
               /* add entry to queue 0 */

               trcnt0 = trcnt; 
               mov_dir[0] = i;
               prev_que[0] = que_entry;
               geval[0] = geval[que_entry]+1;
  
               *que_in = 0;
               break;

              }

            }

           /* If the new queue, exceeds number of available queues, 
              well ... just drop and continue.
           */
           if (new_q >= MAX_NQUE)
              continue;

           /* If the new queue lies before the current queue, put the
              entry in the current queue, since we want to traverse
              queues strictly from start to finish in a sequential
              order (for reasons of speed).
           */
           if (new_q < f)
            {
             new_q =f;
            }

           /* compare new g+h value with g+h value of the best solution so
              far. If greater, prune. 
           */
           nsolval = heval[que_entry] + d12new - d12old +geval[que_entry] + 1;

           if (nsolval > solval)
            continue;

           /* compare new f* value with the best f* value in this queue
              so far. If deviation is more than 1000, prune.
              This is a very tight heuristic.
           */
           if (new_f > prunval[new_q]+ GHPRUN) 
            continue;

           if (feval[que_entry] < prunval[new_q])
              prunval[new_q] = feval[que_entry];

           /* Now put this new position in its new queue position */

           /* If the new queue is full, just pick the next one */ 
           if(que_head[new_q] > MAX_SQUE-1)
            {

             while ((new_q++ < MAX_NQUE) && (que_head[new_q] > MAX_SQUE-1));

             /* If all queues are full, terminate search with either
                - SOL_FND if a solution was found
                - ISOL_FND if no solution found but there is a position
                  from which a new search can be started
                - NOSOL_FND if no solution found.
             */

             if (new_q >= MAX_NQUE)
              {
               if (found_sol)
                return SOL_FND;
 
               if (bstque != 1)
                {
                 *que_in = bstque;
                 return ISOL_FND;
                }
                else
                {
                 return NOSOL_FND;
                }

              }
 
            }

           /* add entry to queue */

           new_que = que_head[new_q]*MAX_NQUE+new_q;

         for (j=0; j> ((4 - (nsp_pos%POSSZ))*5));

         sp_pos[new_que] = nsp_pos;
 
           /* calculate new distances */
  
           heval[new_que] = heval[que_entry] + d12new - d12old;
           geval[new_que] = geval[que_entry] + 1;

           mov_dir[new_que] = i;
           feval[new_que] = new_f;
           prev_que[new_que] = que_entry;

           /* keep track of best position  */
           if (new_f < mineval)
            {
             mineval = new_f;
             bstque = new_que;
            } 

           que_head[new_q]++;

      }

   que_tail[f]++;
  } /* while */

  que_head[f] = que_tail[f] = 0;

 } /* for */

/* If all queues have been handled, return
   - SOL_FND if a solution has been found
   - NBSOL_FND/NOSOL_FND if no solution found
*/

if (found_sol)
 return SOL_FND;
else
 if (pass == 0)
  return NOSOL_FND;
  else
  return NBSOL_FND;
} 

sv_ghsol(que)
int que;
{
int i;
int que_in;

/* save A* solution in tghsol, and in the process count number
   of transports.
*/

que_in = que;

for (i=geval[que_in] - solstart -1; i>= shcnt; i--)
{
 tghsol[i] = mov_dir[que_in];
 if (tghsol[i] == TRANS)
  trancnt++;

 que_in = prev_que[que_in];
 
}

shcnt = geval[que] - solstart;

}