/* Retrieved from http://ls5-www.informatik.uni-dortmund.de/~edelkamp/lectures/ki/software/IDAstar.c */ /* 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. */ #include /* standard I/O library */ #define NUMBER 100000 /* number of problem instances to be solved */ #define X 3 /* squares in the x dimension */ #define SIZE 9 /* 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[4];} 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. */ int input(int* s[SIZE]) { //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 (int * 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); } /* GENERATE generates a random solvable state. */ generate (state) int state[SIZE]; /* state vector */ {int blank; /* position of blank */ int index; /* index to tile positions */ int other; /* index of tile to swap with */ int temp; /* for swapping tiles */ int swaps; /* number of swaps to restore state to goal state */ do { for (index = 0; index < SIZE; index++) state[index] = index; /* initialize to goal state */ blank = 0; /* initial position of blank */ swaps = 0; /* initialize number of swaps */ for (index = SIZE-1; index > 0; index--) /* for each position except zero */ {other = rand() % (index + 1); /* random number between 0 and index */ if (other != index) /* if the two positions are different */ {temp = state[index]; state[index] = state[other]; /* swap the two tiles */ state[other] = temp; swaps++;} /* increment swap counter */ if (state[index] == 0) blank = index; /* keep track of blank position */ if (state[other] == 0) blank = other;} swaps = (swaps + blank % X + blank / X) % 2; /* parity of permutation */ } while (swaps == 1); /* until even permutation */ return blank; } /* 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 (int blank, int oldblank,int g,int h) { 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 */ s[newblank] = 0; if ((newh == 0) || /* goal state is reached or */ (search(newblank, blank, g+1, newh))) /* search succeeds */ return (1); /* exit with success */ s[newblank] = tile; s[blank] = 0;}} /* 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. */ float aver = 0; 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 */ initops (); /* initialize operator table */ init(increment); /* initialize evaluation function */ for (problem = 1; problem <= NUMBER; problem++) /* for each initial state */ {blank = generate(s); /* input initial state */ 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 */ // printf ("%d %10.f\n", thresh, generated); /* nodes per iteration */ fflush(stdout); /* print to file after each iteration */ total = total + generated; /* keep track of total nodes per problem */ thresh += 2;} /* threshold always increases by two */ while (!success); /* until solution is found */ printf ("%d %d %10.f\n", problem, thresh-2, total); aver += thresh-2; fflush(stdout);} printf("%f\n", (float) aver/ NUMBER); }