```
/* This program performs iterative-deepening A* on the sliding tile
puzzles, using the Manhattan distance evaluation function. It was
written by Richard E.  Korf, Computer Science Department, University
of California, Los Angeles, Ca.  90024.

This program implements a slight modification over the original
version: time is accounted for every instance solved and various stats
about time are provided while the test set is being solved */

#include <stdio.h>                                   /* standard I/O library */
#include <string.h>                                                /* memcpy */
#include <sys/time.h>                                       /* time handling */
#include <unistd.h>                                         /* time handling */

#define NUMBER 100               /* number of problem instances to be solved */
#define X 4                                    /* squares in the x dimension */
#define SIZE 16                                   /* total number of squares */

int s[SIZE];                       /* state of puzzle: tile in each position */

struct operators
{int num;                                 /* number of applicable oprs: 2..4 */
int pos;} oprs[SIZE];    /* position of adjacent tiles for each position */

int increment [SIZE] [SIZE] [SIZE];    /* incr eval func: tile, source, dest */

int thresh;                                       /* search cutoff threshold */
double generated;                /* number of states generated per iteration */
double total;                            /* total number of states generated */

/* INITOPS initializes the operator table. */

initops ()

{int blank;                                   /* possible positions of blank */

for (blank = 0; blank < SIZE; blank++)  /* for each possible blank position */
{oprs[blank].num = 0;                               /* no moves initially */
if (blank > X - 1)                                       /* not top edge */
oprs[blank].pos[oprs[blank].num++] = blank - X;       /* add a move up */
if (blank % X > 0)                                      /* not left edge */
oprs[blank].pos[oprs[blank].num++] = blank - 1;     /* add a move left */
if (blank % X < X - 1)                                 /* not right edge */
oprs[blank].pos[oprs[blank].num++] = blank + 1;    /* add a move right */
if (blank < SIZE - X)                                 /* not bottom edge */
oprs[blank].pos[oprs[blank].num++] = blank + X;}}   /* add a move down */

/* INIT pre-computes the incremental evaluation function table. For a
given tile moving from a given source position to a given destination
position, it returns the net change in the value of the Manhattan
distance, which is either +1 or -1.  */

init (increment)

int increment [SIZE] [SIZE] [SIZE];/* incr eval function: tile, source, dest */

{int tile;                                               /* tile to be moved */
int source, dest;                       /* source and destination positions */
int destindex;                       /* destination index in operator table */

for (tile = 1; tile < SIZE; tile++)                   /* all physical tiles */
for (source = 0; source < SIZE; source++)   /* all legal source positions */
for (destindex = 0; destindex < oprs[source].num; destindex++)
/* legal destinations of source */
{dest = oprs[source].pos[destindex];    /* dest is new blank position */
increment[tile][source][dest]  = abs((tile % X) - (dest % X))
- abs((tile % X) - (source % X))
+ abs((tile / X) - (dest / X))
- abs((tile / X) - (source / X));}}

/* INPUT accepts an initial state from the terminal, assuming it is
preceded by a problem number. It stores it in the state vector and
returns the position of the blank tile. */

input (s)

int s[SIZE];                                                 /* state vector */

{int index;                                       /* index to tile positions */
int blank;                                        /* position of blank tile */

scanf ("%*d");                                  /* skip over problem number */
for (index = 0; index < SIZE; index++)                 /* for each position */
{scanf ("%d", &s[index]);                  /* input tile in that position */
if (s[index] == 0) blank = index;}     /* note blank position in passing */
return (blank);}

/* MANHATTAN returns the sum of the Manhattan distances of each tile,
except the blank, from its goal position. */

manhattan (s)

int s[SIZE];                                                        /* state */

{int value;                                                   /* accumulator */
int pos;                                                   /* tile position */

value = 0;
for (pos = 0; pos < SIZE; pos++)
if (s[pos] != 0)            /* blank isn't counted in Manhattan distance */
value = value + abs((pos % X) - (s[pos] % X))            /* X distance */
+ abs((pos / X) - (s[pos] / X));           /* Y distance */
return(value);}

/* SEARCH performs one depth-first iteration of the search, cutting
off when the depth plus the heuristic evaluation exceeds THRESH. If
it succeeds, it returns 1 and records the sequence of tiles moved in
the solution.  Otherwise, it returns 0 */

search (blank, oldblank, g, h)

int blank;			                /* current position of blank */
int oldblank;			               /* previous position of blank */
int g;                                            /* current depth of search */
int h;	                           /* value of heuristic evaluation function */

{ int index;                                    /* index into operator array */
int newblank;                               /* blank position in new state */
int tile;                                              /* tile being moved */
int newh;                             /* heuristic evaluation of new state */

for (index = 0; index < oprs[blank].num; index++)     /* for each appl opr */
if ((newblank = oprs[blank].pos[index]) != oldblank) /*not inv last move */
{tile = s[newblank];            /* tile moved is in new blank position */
newh = h + increment[tile][newblank][blank];   /* new heuristic est */
generated++;                                 /* count nodes generated */
if (newh+g+1 <= thresh)                    /* less than search cutoff */
{s[blank] = tile;                               /* make actual move */
if ((newh == 0) ||                     /* goal state is reached or */
(search(newblank, blank, g+1, newh)))       /* search succeeds */
return (1);                                 /* exit with success */
s[newblank] = tile;}}       /* undo current move before doing next */
return (0);}                                          /* exit with failure */

/* Main program does the initialization, inputs an initial state, solves it,
and prints the solution. */

main ()

{
int success;                         /* boolean flag for success of search */
int blank;                                    /* initial position of blank */
int initeval;                       /* manhattan distance of initial state */
int problem;                                           /* problem instance */
int index;                                      /* index to tile positions */
long totalTime = 0;       /* time elapsed for solving the whole test suite */

struct timeval stv,etv;
struct timezone stz,etz;
float thistime;
float totaltime=0.0;

initops ();                                   /* initialize operator table */
init (increment);                        /* initialize evaluation function */

for (problem = 1; problem <= NUMBER; problem++){ /* for each initial state */
blank = input(s);                                 /* input initial state */
gettimeofday (&stv,&stz);
thresh = initeval = manhattan(s);      /* initial threshold is initial h */
total = 0;                           /* initialize total nodes generated */

do{                    /* depth-first iterations until solution is found */
generated = 0;            /* initialize number generated per iteration */
success = search (blank, -1, 0, initeval);           /* perform search */
fflush(stdout);       /* flush output buffer to see progress of search */
total = total + generated;    /* keep track of total nodes per problem */
thresh += 2;}                     /* threshold always increases by two */
while (!success);                             /* until solution is found */

gettimeofday (&etv,&etz);
if (etv.tv_usec>stv.tv_usec){
thistime=(etv.tv_sec-stv.tv_sec)+(etv.tv_usec-stv.tv_usec)/1000000.0;}
else{
thistime=(etv.tv_sec-stv.tv_sec)+(1000000.0+etv.tv_usec-stv.tv_usec)/1000000.0;}

totaltime+=thistime;

printf ("%d %d %10.f %2.2f/%2.2f (%2.2f)\n", problem, thresh-2, total,
thistime,totaltime,totaltime/(problem*1.0));}}

```