// n-puzzle   for AI class mahidol 2012
//    Prabhas Chongstitvatana     29 Oct 2012

// list is a linked list of cells. each cell contains
//    info,link    link == 0 at the end of list
//    index to a cell is never 0
//    a list has a header cell with head,tail  pointed to the
//    head and the tail of a list.  so that inserting a new
//    item at the head or the end of list is fast.

//    a buffer is built from a list
//    search strategy manages order of items in list
//    two more fields are added to the cell
//       parent -- for tracing the path
//       hv     -- heuristic value

//  pool of cell is never released.

// board is an array of char, contained 1..N with 0 as space
//    each board is allocated from bpool[.] size N
//    board id is the index into this pool
//    a new board is created for a new state

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

#define   MAXCELL   	200000		// for list
#define   MAXB			300000		// for board
#define   N				9			// size of puzzle
#define   N2			3			// N = N2 * N2

//   operations on list
#define   head(t)  		cell[t]
#define   tail(t)  		cell[t+1]
#define   puthead(t,a)  cell[t] = (a)
#define   puttail(t,a)  cell[t+1] = (a)

//   operations on extended cell
#define   parent(t)       cell[t+2]
#define   hv(t)           cell[t+3]
#define   putparent(t,a)  cell[t+2] = (a)
#define   puthv(t,a)      cell[t+3] = (a)

//   operations on board
#define	  putb(bid,i,v)		bpool[(bid+i)] = (v)
#define	  getb(bid,i)		bpool[(bid+i)]

int  cell[MAXCELL], freecell;		// pool of cell
char bpool[MAXB];					// pool of board
int  freeb;
int  xset[4];						// set of expanded boards
int  ss;							// state-space list of board
int  buf;							// buffer
int  current;						// current board/state
int  goalnode;
int  goalboard, startboard;
int  cnt, cnt2, cnt3;						// count number of move

int goalpattern[] = {1,2,3,4,5,6,7,8,0};
int startpattern[] = {1,2,3,4,0,5,6,7,8};

// -----------list functions --------

int newcell(int info, int link){
    int a;
    if( freecell > (MAXCELL-2)){
        printf("run out of cell space\n");
        printf("cnt %d\n",cnt);
        exit(0);
    }
    a = freecell;
    freecell += 4;
    puthead(a,info);
    puttail(a,link);
    putparent(a,current);
    return a;
}

int newlist(void){
    return newcell(0,0);
}

// insert a cell a into the list t
void inserthead(int t, int a){
    int b;
    b = head(t);
    if( b == 0 ){		// empty list
        puthead(t,a);
        puttail(t,a);
    }else{
        puthead(t,a);
        puttail(a,b);
    }
}

//  must handle last node case
int removehead(int t){
    int a;
    a = head(t);
    if( a != 0 ){
        puthead(t,tail(a));
        puttail(a,0);
        if( tail(t) == a ) 	// the last node
            puttail(t,0);
    }
    return a;
}

// insert a at the end of list t
void insertback(int t, int a){
    int b;
    if( head(t) == 0 ){	// empty list
        puthead(t,a);
        puttail(t,a);
    }else{
        b = tail(t);
        puttail(b,a);
        puttail(t,a);
    }
}

// insert a into t, order (ascending) by heuristic value
void insertsort(int t, int a){
    int b, c, h;
    c = t;
    b = head(t);
    if( b == 0 ){	// empty list
        puthead(t,a);
        puttail(t,a);
    }else{
        h = hv(a);
        while( tail(b) != 0 && h < hv(b) ){
            c = b;
            b = tail(b);
        }
        // b is the last node or h >= hv(b)
        if( h < hv(b) ){	// insert at front
            puttail(a,b);
            puttail(c,a);
        }else{				// insert at back
            puttail(b,a);
            if( tail(t) == b )
                puttail(t,a);	// update header
        }
    }
}

void printlist(int t){
    t = head(t);
    while(t != 0){
        printf("%d:",head(t));
        t = tail(t);
    }
    printf("\n");
}

// example of use of list
int createlist(void){
    int i,a,t;
    t = newlist();
    for(i = 1; i < 10; i++){
        a = newcell(i,0);
        inserthead(t,a);
    }
    return t;
}

// -------- board functions ----------

int newboard(void){
    int bid;
    if( freeb > (MAXB - N)){
        printf("run out of board space\n");
        printf("cnt %d\n",cnt);
        exit(0);
    }
    bid = freeb;
    freeb += N;
    return bid;
}

// make a new board and instantiate it with pattern
int makeboard(int *pattern){
    int i, b;
    b = newboard();
    for(i = 0; i < N; i++)
        putb(b,i,pattern[i]);
    return b;
}

void printboard(int bid){
    int i,j;
    j = 0;
    for(i = 0; i < N; i++){
        printf("%d ", getb(bid,i));
        j++;
        if( j % N2 == 0 ) printf("\n");
    }
    printf("\n");
}

// -------- move tile on a board ------------

// return coordinate x,y of void tile
void findzero(int bid, int *x, int *y){
    int i;
    for(i = 0; i < N; i++)
        if( getb(bid,i) == 0 ) break;
    *y = i % N2;
    *x = i / N2;
}

// copy board b2 to b1
void copyboard(int b1, int b2){
    int i;
    for(i = 0; i < N; i++)
        putb(b1,i,getb(b2,i));
}

// swap tile  x1,y1 with x2,y2 of a board
void swaptile(int bid, int x1, int y1, int x2, int y2){
    int tmp, t1, t2;
    t1 = x1*N2+y1;			// convert x,y to offset
    t2 = x2*N2+y2;
    tmp = getb(bid,t1);
    putb(bid,t1,getb(bid,t2));
    putb(bid,t2,tmp);
}

//  move operations, return a new board, 0 if not move

int moveup(int bid, int i, int j){
    int b;
    if( i == 0 ) return 0;		// cannot move
    b = newboard();
    copyboard(b,bid);
    swaptile(b, i-1,j, i,j);
    return b;
}

int movedown(int bid, int i, int j){
    int b;
    if( i == N2-1 ) return 0; // cannot move
    b = newboard();
    copyboard(b,bid);
    swaptile(b, i,j, i+1,j);
    return b;
}

int moveleft(int bid, int i, int j){
    int b;
    if( j == 0 ) return 0;		// cannot move
    b = newboard();
    copyboard(b,bid);
    swaptile(b, i,j-1, i,j);
    return b;
}

int moveright(int bid, int i, int j){
    int b;
    if( j == N2-1 ) return 0; 	// cannot move
    b = newboard();
    copyboard(b,bid);
    swaptile(b, i,j, i,j+1);
    return b;
}

// ------------ search ---------------

//  try all moves, keep result in xset[.]
void expand(int bid){
    int zi, zj;
    findzero(bid,&zi,&zj);
    xset[0] = moveup(bid,zi,zj);
    xset[1] = movedown(bid,zi,zj);
    xset[2] = moveleft(bid,zi,zj);
    xset[3] = moveright(bid,zi,zj);
}

// check equality of board b1 and b2, return 1 if equal
int equalboard(int b1, int b2){
    int i;
    if( b1 == b2 ) return 1;
    if( b1 == 0 ) return 0;
    if( b2 == 0 ) return 0;
    for(i = 0; i < N; i++)
        if( getb(b1,i) != getb(b2,i) ) return 0;
    return 1;
}

// check bid exists in ss and buffer
int dup(int bid){
    int s;
    if( ss != 0){
        s = head(ss);
        while( s != 0 ){
            if( equalboard(head(s),bid) ) return 1;
            s = tail(s);
        }
    }
    if( buf != 0 ){
        s = head(buf);
        while( s != 0 ){
            if( equalboard(head(s),bid) ) return 1;
            s = tail(s);
        }
    }
    return 0;
}

// sum of distance of each tile from goal
int heuristicfun(int bid){
    int dx, dy, sx, sy;
    int x1, y1, x2, y2;
    int i, t;
    sx = 0;
    sy = 0;
    for(i = 0; i < N; i++){
        t = (int)getb(bid,i);
        if( t != 0 ){
            x1 = i / N;			// board position (x,y)
            y1 = i % N;
            t = t - 1;			// first position is tile 1
            x2 = t / N;			// goal tile position
            y2 = t % N;
            dx = x1 > x2 ? (x1-x2) : (x2-x1);
            dy = y1 > y2 ? (y1-y2) : (y2-y1);
            sx += dx;
            sy += dy;
        }
    }
    return sx + sy;
}

// update buffer with xset[.]
//    put them in front
//    must check for duplication to prevent loop
//    both in the existing state and in the buffer

//  put xset[.] in front, dept-first-search
void updatebufferDFS(void){
    int i;
    for(i = 3; i >= 0; i--)
        if(xset[i] != 0 && !dup(xset[i]))
            inserthead(buf,newcell(xset[i],0));
}

//  put xset[.] at back, breath-first-search
void updatebufferBFS(void){
    int i;
    for(i = 3; i >= 0; i--)
        if(xset[i] != 0 && !dup(xset[i]))
            insertback(buf,newcell(xset[i],0));
}

// put xset[.] by order of heuristic function
void updatebufferHeu(void){
    int i, a;
    for(i = 3; i >= 0; i--)
        if(xset[i] != 0 && !dup(xset[i])){
            a = newcell(xset[i],0);
            puthv(a,heuristicfun(xset[i]));
            insertsort(buf,a);
        }
}

// ------------- main state-space search ----------

// check expanded set (xset[.]) for goal
int isgoal(void){
    int i;
    for(i = 0; i < 4; i++)
        if( equalboard(xset[i],goalboard) )	return 1;
    return 0;
}

// to prevent super long running time
// the loop is limited at 10000
void search(void){
    inserthead(buf, newcell(startboard,0));
    while( head(buf) != 0 ){
        if( cnt++ > 10000 ) break;	// limit loop
        current = removehead(buf);
        inserthead(ss,current);
        expand(head(current));
        if( isgoal() )
            break;
        updatebufferHeu();
    }
}

// print state-space as order of search
//   at most 50 states from newest
void printss(void){
    int bid, a;
    int k = 50;
    a = head(ss);
    while( a != 0 && k > 0 ){
        printboard(head(a));
        a = tail(a);
        k--;
    }
}

// print path from goal to start
//   at most 50 states from newest
void printpath(void){
    int a;
    int k = 0;
    printboard(goalboard);
    printboard(head(current));
    a = parent(current);
    while( a != 0 && k < 50 ){
        printboard(head(a));
        a = parent(a);
        k++;
    }
    while( a != 0 ){
        a = parent(a);
        k++;
    }
    cnt2 = k;
}

int main(void){
    freecell = 2;
    freeb = N;
    cnt = 0;
    ss = newlist();
    buf = newlist();
    goalboard = makeboard(goalpattern);
    startboard = makeboard(startpattern);
    current = 0;			// parent of root node
    search();
    printss();
//	printpath();
    printf("no. of nodes explored %d, no. of move %d\n",cnt,cnt2);
    return 0;
}