| IQ Test -- An example of A* Heuristic Search |
|
|
|
#define pgm_id "IQ_TEST MSC 6.0 Version of 08/14/11 for gcc and Linux" /* An experimental A* heuristic state space search. *................................................................... * * Written on: January 29, 1986 * * by: R. J. Brown * 5225 NW 27 Court * Margate, FL 33063 * (305) 979-1567 * * For: CAP 6600, Artificial Intelligence * * Under: Dr. Frederick Hoffman, Chairman * Mathematics Department, Graduate Division * Florida Atlantic University * Boca Raton, FL 33431 * (305) 393-3345 * * Ownership: I hereby place this program into the * Public Domain. * * Edited: 25 years later on Sun Aug 14 19:08:56 EDT 2011 * by rj@elilabs.com to bring up to date using ANSI * prototypes, and to provide the above email address * for the author (me). This file is also available at: * http://www.elilabs.com/~rj/iq_test.c.html * *....................................................................... * * This program implements an A* heuristic state space search of * the solution tree for an "IQ test" puzzle that is sold at roadside * souveneer stands. The puzzle appears as follows: * * _ * / \ * / * \ * / * * \ * / * . * \ * / * * * * \ * / * * * * * \ * `-----------' * * The asterisks (*) represent pegs, and the dot (.) represents * an empty hole. The empty hole may initially be anywhere, but only * one empty hole is permitted. A move consists of jumping a peg over * an adjacent peg and landing in a hole, removing the peg thus jumped * over in the process; every move therefore decreases the number of * active pegs by one. The goal is to end up with only one peg on * the board. * * The state space representation choosen is to use the lower * diagonal of a boolean array to represent the board, with a true * value meaning that a peg is present, and a false value meaning * that an empty hole is there. * * The board is represented as follows: * * 0 * * 1 * * * 2 * . * * 3 * * * * * 4 * * * * * * 0 1 2 3 4 * * Where the (0,0) location represents the top of the triangle. * The correspondence with the actual board should be obvious. * * An adjacent location Q in any of the six directions may be * represented by a vector addition of the initial peg's coordinates * P with any vector from the set M = +/- { X, Y, Z }, where X = (1,0), * Y = (0,1), and Z = (1,1) = X+Y given that the constraint of index * set membership is satisfied: we do not want to move off of the board! * * Since there are 15 positions on the board, and 16 bits in a * computer word, we can represent an entire board configuration * with a single integer interpreted as a bit string. The addressing * function is: * Bd(j,k) = BD( (j*(j+1))/2 + k ) * * where BD is a one dimensional array. (Reference: Knuth, D.E., 1968. * "The art of computer programming", Vol. 1, p 297, eqn (8), * Addison Wesley, Reading, Mass.) * * To address a given bit position in the array, a mask is generated * with all bits set to zero except the addressed position. * */ #include <stdlib.h> /* operating system i/o interface */ #include <stdio.h> /************************************************************************ * * type and constant definitions * ************************************************************************/ #define loop for(;;) /* indefinite looping directive */ #define FOOBAR -1 /* messed up result */ #define nil 0L /* the pointer to nowhere... */ #define min(x,y) ((x)<(y)?(x):(y)) /* minimum of two values macro */ #define ALL_PEGS (board)0x7fff /* a board with all holes pegged */ typedef int word; /* a machine word */ typedef char byte; /* a machine byte */ typedef char* ptr; /* a machine address */ typedef word locn; /* the representation of a board location */ #define NMOVES 6 /* the number of possible moves from anywhere */ typedef word board; /* the representation of a board configuration */ #define NHOLES 15 /* the number of holes in the board */ #define BDSZ 5 /* length of a side of the board */ typedef char index; /* an index set member, e.g. x or y component */ typedef int boolean; /* true/false logical indicator */ #define FALSE 0 /* boolean false value */ #define TRUE !FALSE /* boolean true value */ typedef int cost; /* the representation of a path cost */ typedef int** link; /* a pointer to a node */ typedef struct { /* a node in the search tree */ link father; /* the link back to the father of this node */ cost g, /* actual cost from start to here */ f; /* cost estimate from start to goal thru here */ board bd; /* the current state of the board */ } node; typedef union { /* utility definition for type conversion */ locn l; struct { index k,j; } c; } xylocn; #define Hole(x,y) (((y)<<8)|((x)&0xff)) /* form hole location from x,y */ #define X Hole( 1, 0) /* the primitive motion step elements */ #define _X Hole(-1, 0) #define Y Hole( 0, 1) #define _Y Hole( 0,-1) #define Z Hole( 1, 1) #define _Z Hole(-1,-1) locn M[ NMOVES ] = { X, _X, Y, _Y, Z, _Z }; /* the possible moves */ /************************************************************************ * * dynamic memory management functions * ************************************************************************/ void release(char* x) { /* return old memory for recycling */ free(x); } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ char *allocate(int num, int siz) { /* dynamic memory allocator */ char *result=calloc((unsigned)(num),(unsigned)(siz)); if(result) return(result); printf("OUT OF MEMORY IN allocate!\n"); exit(-1); } /************************************************************************ * * state space implementation functions * ************************************************************************/ int holes(board bd) { /* count the empty holes in a board */ int result=bd&1; while(bd=(bd>>1)) result+=bd&1; return(NHOLES-result); } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ index x(locn p) { /* get x component of location vector */ xylocn xy; xy.l=p; return(xy.c.j); } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ index y(locn p) { /* get y component of location vector */ xylocn xy; xy.l=p; return(xy.c.k); } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ locn hole(index x, index y) { /* generate a location given x & y */ xylocn xy; xy.c.j=x; xy.c.k=y; return(xy.l); } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ boolean legal_locn(locn p) { /* test for legal board location */ index xp=x(p), /* the x position */ yp=y(p); /* the y position */ boolean result=TRUE; /* the result to return */ if( xp < 0 ) result=FALSE; /* x must be positive */ if( yp < 0 ) result=FALSE; /* so must y */ if( yp >= BDSZ ) result=FALSE; /* y can't be too big */ if( xp > yp ) result=FALSE; /* neither can x */ return(result); /* return the desired result */ } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ locn move(locn pos, locn dir) { /* move in direction 'dir' from * position 'pos' and return * location of the result */ locn result; /* where the answer goes */ result= hole(x(pos)+x(dir),y(pos)+y(dir)); /* figure trial result */ if(!legal_locn(pos)) result=FOOBAR; /* reject if bad pos... */ if(!legal_locn(result)) result=FOOBAR; /* ...or if bad result */ return(result); /* return correct result */ } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ board mask(locn p) { /* return the mask for a position */ index j=y(p), k=x(p); return(1<<(j*(j+1)/2+k)); } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ board pos(board bd, locn p) { /* return the value of a position */ return( bd & mask(p) ); } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ boolean vacant(board bd, locn p) { /* true if position is empty hole */ return( ! pos(bd,p) ); } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ boolean occupied(board bd, locn p) {/* true if position has a peg in it */ return( ! vacant(bd,p) ); } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ void show_bd(board bd) { /* display board on stdout */ int i,j,k; /* local loop counters... */ printf("\n"); /* new line before board */ for(k=BDSZ;k>=0;k--) printf(" "); /* tab over */ printf(" -\n"); /* put the top on it */ for(k=BDSZ;k>=0;k--) printf(" "); /* tab over */ printf("/ \\"); /* do rest of top */ for(i=BDSZ-1;i>=0;i--) { /* for all rows in the board... */ printf("\n"); /* start a new line */ for(k=i;k>=0;k--) printf(" "); /* space over appropriatly... */ printf("/ "); /* put a border around board */ for(j=i;j<BDSZ;j++) { /* for all holes... */ if(occupied(bd,hole(i,j))) printf("* "); /* display a star */ else printf(". "); /* or dot as needed */ } printf("\\"); /* put right border on it */ } printf("\n `-----------'\n"); /* put bottom border on it */ } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ board place(board bd, locn p) { /* place a peg at location p */ return( bd | mask(p) ); } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ board remove_peg(board bd, locn p) { /* remove a peg from location p */ return( bd & ~mask(p) ); } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ boolean goal_state(board bd) { /* test board for goal state */ while(!((bd=bd<<1)&0x8000)); /* slide bits 'till sign flips */ return(!(bd&0x7fff)); /* then once more. if zero, then * only one peg was left on board, * so we've solved the puzzle !!! */ } /************************************************************************ * * functions to expand all moves from a given position * ************************************************************************/ board make_move( /* try to make a move from position p in * direction m, given board bd. return new * board configuration, or FALSE if move could * not be made. */ board bd, /* board configuration before move */ locn p, /* location of peg to try to move */ locn m) { /* direction to try jump peg in */ locn p1; /* location one peg hole away (peg to jump) */ locn p2; /* location two peg holes away (where to land) */ if(vacant(bd,p)) return(FALSE); /* can't move if no peg */ p2=move(p1=move(p,m),m); /* generate test holes */ if(!legal_locn(p2)) return(FALSE); /* can't move if not * to legal location */ if(occupied(bd,p2)) return(FALSE); /* can't move if * destination already * has a peg in it */ if(vacant(bd,p1)) return(FALSE); /* can't jump over empty * hole -- must have peg */ return( /* it's a valid move -- return */ place( /* the board configuration that */ remove_peg( /* results from making it. */ remove_peg(bd,p) /* remove the jumper peg */ ,p1) /* and its jumpee, then place */ ,p2) /* the jumper at the new hole, */ ); /* thus completing the move. */ } /************************************************************************ * * 'open' and 'closed' list management functions * ************************************************************************/ typedef struct { /* the form of an item on open or closed */ link next; /* pointer to the next item on the list */ node *data; /* pointer to the tree node for this item */ } listitem; /* the above structure is a list item */ listitem openhd,closedhd; /* the head list nodes */ listitem *open = &openhd, /* pointer to head of open items list */ *closed = &closedhd; /* pointer to head of closed items list */ /*......................................................................*/ void put_on_list( /* put a node on a list */ listitem* l, /* pointer to list head */ node* n) { /* pointer to node to put on list */ listitem *p,*q; /* pointers that move down the list */ loop { /* loop to scan thru the list */ if((p=(l->next))!=nil) { /* at end of list ??? */ if( (p->data)->f > n->f ) { /* no, right place yet? */ q=allocate(1,sizeof(listitem)); /* yes, alloc list item */ q->next=p; /* link it to successor */ l->next=q; /* predec'r links to it */ q->data=n; /* hook up to the node */ return; /* we're done !!! */ } } else { /* at end of list */ q=allocate(1,sizeof(listitem)); /* allocate list item */ q->next=p; /* link it to successor */ l->next=q; /* predec'r links to it */ q->data=n; /* hook up to the node */ return; /* we're done !!! */ } l=p; /* point to next item and loop */ } } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ node* found_on_list( /* determine if a node is on a list */ listitem* l, /* points to head of list to search */ board bd) { /* board configuration to match */ while((l=l->next)!=nil) { /* look til there ain't no more */ if(l->data->bd==bd) { /* compare board configurations */ return(l->data); /* if same, return ptr to node */ } } return(nil); /* we looked high & low, and it's * just not there. return false! */ } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ void put_on_open(node* n) { /* put a node on the open list */ put_on_list(open,n); /* call more general routine */ } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ void put_on_closed(node* n) { /* put a node on the closed list */ put_on_list(closed,n); /* call more general routine */ } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ node* take_off_open() { /* take a node off of open */ listitem *p=open->next, /* private temporary pointer */ *result=p->data; /* trial return value */ if(p==nil) return(nil); /* if empty list, return empty handed! */ open->next=p->next; /* else remove node from list */ release((ptr)p); /* release its list item storage */ return(result); /* return with success node pointer! */ } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ node* found_on_open(board bd) { /* try to find node on open list */ return(found_on_list(open,bd)); /* call more general routine */ } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ node* found_on_closed(board bd) { /* try to find node on closed list */ return(found_on_list(closed,bd)); /* call more general routine */ } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ node* old_node(node* n) { /* determine if a node already * exists with the same configuration */ node* p; /* private pointer */ if(p=found_on_open(n->bd)) return(p); /* is it on open ??? */ if(p=found_on_closed(n->bd)) return(p); /* how about closed ??? */ return(nil); /* not nowhere !!! */ } /************************************************************************ * * the heuristic function that guides the search * ************************************************************************/ cost h(board bd) { /* determine the estimated cost to goal */ return(-2*holes(bd)); /* no estimate for now, * use depth first search * for testing. */ } void tell_about_h() { /* describe heuristic function being used */ printf("\n\t Heuristic is presently twice the number of empty"); printf("\n\tholes on the board. This produces a pure depth-first"); printf("\n\tsearch strategy.\n\n"); } /************************************************************************ * * functions to expand all moves from a given position * ************************************************************************/ node* make_node( /* make a node for a board */ node* father, /* whose father is father */ board bd) { /* and whose board is bd */ node* p=allocate(1,sizeof(node)); /* allocate the memory for it */ p->father=father; /* initialize the father link */ p->bd=bd; /* initialize the board state */ if(father) { p->g=father->g+1; /* enter cost from start to here */ } else p->g=0; /* or zero if start node */ p->f=p->g+h(bd); /* enter heuristic cost to goal */ return(p); /* return pointer to new node */ } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ boolean expand_peg( /* make all possible moves for a peg */ node* father, /* the state before the move */ locn p) /* which peg to try to move */ { int i; /* loop counter */ board newbd; /* the board after the move */ board bd=father->bd; /* board before any moves */ node* n; /* a node from expansion */ node* q; /* an old node with the same * board configuration. */ boolean result=FALSE; /* private result indicator */ for(i=NMOVES;i;i--) { /* try all possible moves */ if(newbd=make_move(bd,p,M[i-1])) { /* is this a legal move ??? */ n=make_node(father,newbd); /* yes, make a node for it */ result=TRUE; /* say a valid move exists */ if(q=old_node(n)) { /* does it match an old one? */ q->f=min(q->f,n->f); /* yes, take minimum cost */ release((ptr)n); /* discard duplicate node */ } else { /* no, its a whole new thing */ put_on_open(n); /* put it on the open list */ } } } return(result); /* return whether any moves existed */ } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ void bar_graph(int n) { /* display a bar graph indicator */ int i; for(i=n;i;i--) fprintf(stderr,"*"); for(i=n;i<NHOLES;i++) fprintf(stderr,"."); for(i=NHOLES;i;i--) fprintf(stderr,"\b"); } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ boolean expand_board( /* make all possible moves from a * given board configuration. */ node* father) { /* the board configuration to * make the moves from. */ index x,y; /* the (x,y) coordinates of the * peg to try to move. */ boolean r=FALSE; /* private result inicator */ bar_graph(holes(father->bd)); /* display depth indicator... */ for(x=0;x<BDSZ;x++) /* for all rows */ for(y=x;y<=BDSZ;y++) /* and collumns, */ r=expand_peg(father,hole(x,y)); /* expand a peg. */ return(r); /* indicate whether any valid moves existed */ } /************************************************************************ * * initialization to place all valid starting positions on open * ************************************************************************/ void open_start_nodes() { /* place all legal starting board * configurations on the open list */ index i,j; /* private counters to loop thru board */ node* p; /* private pointer to current node */ for(i=BDSZ/2;i<BDSZ;i++) { /* for all rows in the * top half of the board * (we can skip the rest * of it because of * symetry)... */ for(j=i;j<BDSZ-(i!=BDSZ-1);j++) { /* for all holes in that * row except the right * edge (eliminated by * symetry) ... */ p=allocate(1,sizeof(node)); /* allocate a node */ p->father=nil; /* say it has no father */ p->bd=remove_peg(ALL_PEGS,hole(i,j)); /* remove one peg */ p->g=0; /* no cost to get here */ p->f=p->g+h(p->bd); /* figure cost to goal */ put_on_open(p); /* put it on open list */ } } } /************************************************************************ * * the A* search algorithm itself !!! * ************************************************************************/ link a_star() { /* search the move tree for an optimal solution */ node* n; /* private node pointer */ open_start_nodes(); /* place all valid starting * positions on the open list */ while(n=take_off_open()) { /* get from open if any left */ put_on_closed(n); /* put it on closed */ if(goal_state(n->bd)) return(n); /* if a goal, we're done! */ expand_board(n); /* else try again... */ } return(nil); /* unsolvable problem, puke !!! */ } /************************************************************************ * * display the solution (with statistics later...) * ************************************************************************/ void print_result(node *n) { /* display solution to puzzle */ if(!n->father) { /* are we at the root yet ??? */ printf("\n*** SOLVED!\n"); /* yes, say we did it !!! */ show_bd(n->bd); /* say how we got here !!! */ return(n); /* back-track... */ } else { /* not at root yet */ print_result(n->father); /* dig deeper */ show_bd(n->bd); /* say how we got here !!! */ return(n); /* keep un-nesting... */ } } /************************************************************************ * * main line program entry point, etc. * ************************************************************************/ void banner(char* id) { /* display program identification */ printf("\n%s",id); printf("\nWritten by R. J. Brown, Florida Atlantic University"); printf("\nThis Program is in the Public Domain.\n"); printf("\n\t This program implements an A* heuristic state space"); printf("\n\tsearch of the solution tree for an \"IQ test\" puzzle"); printf("\n\tthat is sold at roadside souveneer stands.\n"); } /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ int main( /* program starts here */ int nargs, /* number of arguments */ char *args[]) { /* the argumant strings */ banner(pgm_id); /* display program identification */ tell_about_h(); /* describe heuristic function */ fprintf(stderr,"\nSearch Depth Gauge:\n"); /* bar graph title */ print_result(a_star()); /* find & display the solution */ printf("\nQ. E. D.\n"); /* done! */ }
rj@gehazi ~/iq_test $ gcc -w -o iq_test iq_test.c
rj@gehazi ~/iq_test $ ./iq_test
IQ_TEST MSC 6.0 Version of 08/14/11 for gcc and Linux
Written by R. J. Brown, Florida Atlantic University
This Program is in the Public Domain.
This program implements an A* heuristic state space
search of the solution tree for an "IQ test" puzzle
that is sold at roadside souveneer stands.
Heuristic is presently twice the number of empty
holes on the board. This produces a pure depth-first
search strategy.
Search Depth Gauge:
*************..
*** SOLVED!
-
/ \
/ * \
/ * * \
/ . * * \
/ * * * * \
/ * * * * * \
`-----------'
-
/ \
/ * \
/ * * \
/ * * * \
/ . * * * \
/ . * * * * \
`-----------'
-
/ \
/ * \
/ * * \
/ * * * \
/ . * * * \
/ * . . * * \
`-----------'
-
/ \
/ * \
/ * * \
/ * * * \
/ . * * * \
/ * . * . . \
`-----------'
-
/ \
/ * \
/ . * \
/ . * * \
/ * * * * \
/ * . * . . \
`-----------'
-
/ \
/ * \
/ . * \
/ * * * \
/ * . * * \
/ * . . . . \
`-----------'
-
/ \
/ * \
/ * * \
/ . * * \
/ . . * * \
/ * . . . . \
`-----------'
-
/ \
/ * \
/ * * \
/ . * . \
/ . . . * \
/ * . * . . \
`-----------'
-
/ \
/ . \
/ * . \
/ . * * \
/ . . . * \
/ * . * . . \
`-----------'
-
/ \
/ . \
/ * * \
/ . * . \
/ . . . . \
/ * . * . . \
`-----------'
-
/ \
/ . \
/ * . \
/ . . . \
/ . * . . \
/ * . * . . \
`-----------'
-
/ \
/ . \
/ * . \
/ * . . \
/ . . . . \
/ * . . . . \
`-----------'
-
/ \
/ . \
/ . . \
/ . . . \
/ * . . . \
/ * . . . . \
`-----------'
-
/ \
/ . \
/ . . \
/ * . . \
/ . . . . \
/ . . . . . \
`-----------'
Q. E. D.
rj@gehazi ~/iq_test $
|
|
