// n-puzzle   for AI class mahidol 2012
//    Prabhas Chongstitvatana     16 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.

//  pool of cell is never released.

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

#define   MAXCELL   	50000		// 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 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  goalboard, startboard;
int  cnt;							// 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 += 2;
    puthead(a,info);
    puttail(a,link);
    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;
}

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");
    }
}

// -------- 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;
}

// update buffer with xset[.]
//    put them in front
//    must check for duplication to prevent loop
//    both in the existing state and in the buffer
void updatebufferDFS(void){
    int i;
    for(i = 3; i >= 0; i--)
        if(xset[i] != 0 && !dup(xset[i]))
            inserthead(buf,newcell(xset[i],0));
}

// ------------- 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){
    int a;
    inserthead(buf, newcell(startboard,0));
    while( head(buf) != 0 ){
        cnt++;
        if( cnt > 10000 ) break;	// limit loop
        a = removehead(buf);
        inserthead(ss,a);
        expand(head(a));
        if( isgoal() )
            break;
        updatebufferDFS();
    }
}

// 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));
        printf("\n");
        a = tail(a);
        k--;
    }
}

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