ai_missplaced.c

/*
ARSHAD G ------------ 201601025
ROHAN S  ------------ 201601073
AI ASSIGNMENT - I ----------- 15 PUZZLE SOLVER USING  DISPLACED TILES HEURISTIC

*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 4

int mx[4] = {1,0,-1,0};
int my[4] = {0,1,0,-1};

int node_count = 0,node_count_cl = 0,path_count = 0;

int getInvCount(int arr[]){
	int inv_count = 0,i,j;
	for (i = 0; i < N * N - 1; i++)
	{
		for (j = i + 1; j < N * N; j++)
		{
			// count pairs(i, j) such that i appears
			// before j, but i > j.
			if (arr[j] && arr[i] && arr[i] > arr[j])
				inv_count++;
		}
	}
	return inv_count;
}

// find Position of blank from bottom
int findXPosition(int puzzle[N][N]){
	int i,j;
	// start from bottom-right corner of matrix
	for (i = N - 1; i >= 0; i--)
		for (j = N - 1; j >= 0; j--)
			if (puzzle[i][j] == 0)
				return N - i;
}

// This function returns true if given
// instance of N*N - 1 puzzle is solvable
int isSolvable(int puzzle[N][N]){
	// Count inversions in given puzzle
	int invCount = getInvCount((int*)puzzle);

	// If grid is odd, return true if inversion
	// count is even.
	if (N & 1)
		return !(invCount & 1);

	else	 // grid is even
	{
		int pos = findXPosition(puzzle);
		if (pos & 1)
			return !(invCount & 1);
		else
			return invCount & 1;
	}
}

typedef struct Node{
	int matrix[N][N];
	struct Node* next;
	struct Node* parent;
	int cost;
	int level;
	int x,y,par_cost;
}node;
node* front = NULL;
node* front_open = NULL;

void push(node* elem){
	node_count++;
	if(front == NULL)front = elem;
	else{
		node* temp = front;
		while(temp->next!=NULL && temp->next->cost < elem->cost)
			temp = temp->next;
		elem->next = temp->next;
		temp->next = elem;
	}
}

void push_open(node *elem){
	//printf("IM out");
	//node_count_cl++;
	if(front_open == NULL)front_open = elem;
	else{
		//printf("IM in");
		node* temp = front_open;
		while(temp->next!=NULL && temp->next->cost < elem->cost)
			temp = temp->next;
		elem->next = temp->next;
		temp->next = elem;
	}
}

void count_open_and_closed(){
	int c1=0,c2=0;
	if(front == NULL)printf("0 NODES REMAIN IN OPEN LIST\n");
	if(front_open == NULL)printf("0 NODES REMAIN IN CLOSED LIST\n");
	else{
		node* temp1 = front;
		node* temp2 = front_open;
		while(temp1->next!=NULL){c1++;
			temp1 = temp1->next;}
		while(temp2->next!=NULL){c2++;
			temp2 = temp2->next;}
		printf("%d NODES REMAIN IN OPEN LIST \n%d NODES REMAIN IN CLOSED LIST\n",c1,c2);
	}
}

node* getmin(){
	node* temp = front;
	front = front->next;
	return temp;
}

int caldif(int A[N][N],int B[N][N]){
	int cost = 0;
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			if(A[i][j] != B[i][j])cost++;
	return cost;
}



int get_openlist(node *ptr){
	node* temp = front_open;
	while(temp != NULL){
		if(caldif(temp->matrix,ptr->matrix) == 0)
			return 1;
		temp = temp->next; 
	}
	return 0;
}
int get_closedlist(node *ptr){
	node* temp = front;
	while(temp != NULL){
		if(caldif(temp->matrix,ptr->matrix) == 0){
			//temp->next = temp->next->next;
			return 1;}
		temp = temp->next; 
	}
	return 0;
}

int calman(int A[N][N],int B[N][N]){
	int p[N*N][2],q[N*N][2];
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++){
			p[A[i][j]][0] = i;
			p[A[i][j]][1] = j;
		} 
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++){
			q[B[i][j]][0] = i;
			q[B[i][j]][1] = j;
		} 
	int man = 0;
	for(int i=0;i<N*N;i++){
		man += abs(p[i][0]-q[i][0]) + abs(p[i][1]-q[i][1]);
	}
	return man;
}

int displacedtile(int A[N][N]){
	int cost = 0;
	int B[N][N] ={{1,2,3,4},
			   {5,6,7,8},
			   {9,10,11,12},
			   {13,14,15,0}};
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			if(A[i][j] != B[i][j]&& A[i][j])cost++;
	//cost += calman(A,B);
	return cost;
}

node* init(int par[N][N],int fin[N][N],int x,int y,int nx,int ny,int lev,node* parent,int heu_no){
	node* temp = (node*)malloc(sizeof(node));
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			temp->matrix[i][j] = par[i][j];
	int tp = temp->matrix[x][y];
	temp->matrix[x][y] = temp->matrix[nx][ny];
	temp->matrix[nx][ny] = tp;
	temp->level = lev;
	temp->x = nx;
	temp->y  = ny;
	temp->cost = 0;
	temp->parent = parent;
	temp->par_cost = 0;
	if(heu_no == 1)
		temp->cost =   calman(temp->matrix,fin);
	else
		temp->cost = displacedtile(temp->matrix);
	return temp;
}

int check(int x,int y){
	if(x >= 0 && x < N && y >=0 && y < N)return 1;
	return 0;
}

void printmat(int mat[N][N]){
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			printf("%d ",mat[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}	

void ppath(node* head){

	if(head == NULL)return;
	ppath(head->parent);
	printmat(head->matrix);
	path_count++;
}

void play(int initial[N][N],int fin[N][N],int x,int y,int h){
	front = init(initial,fin,x,y,x,y,0,NULL,h);
	front_open = init(initial,fin,x,y,x,y,0,NULL,h);

	while(front != NULL){
		node* top = getmin();
		node_count_cl++;
		if(caldif(top->matrix,fin) == 0){
			ppath(top);
			return;
		}

		for(int  i  = 0;i < 4;i++){
			if(check(top->x+mx[i],top->y+my[i])){
				
				//printf("%d running",i);
				node* chd = init(top->matrix,fin,top->x,top->y,top->x+mx[i],top->y+my[i],top->level+1,top,h);
				//push_open(chd);
				if(top->parent != NULL && caldif(top->parent->matrix,chd->matrix) == 0)continue;
				if(top->parent != NULL && (get_openlist(chd) == 1 || get_closedlist(chd)==1 )) {
				//	printf("INs");
					continue;}
				
				//chd->cost=chd->cost+0.3*(chd->parent->par_cost)+1;
				chd->cost=chd->cost + chd->parent->par_cost + 1;				
				chd->par_cost = chd->parent->par_cost+1;
				push(chd);
				//printmat(chd->matrix);
			}
			
		}
		//printf("%d \n",cst);
		push_open(top);
	}
}

int main(){

// 0) 25 - 35 sec 1) 1-3 sec 
	//int initial[N][N]={{1,2,3,4}, {5,6,7,8}, {13,10,11,12},{9,15,14,0}};

// 0) & 1) IMMEDIATELY
	int initial[N][N]={{5,1,7,3}, {9,2,11,4}, {13,6,15,8},{0,10,14,12}};

//NOT SOLVABLE
//	int initial[N][N]={{0,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,1}};
//	int initial[N][N]={{3,9,1,15},{14,11,4,6},{13,0,10,12},{2,7,8,5}};

//	int initial[N][N]={{1,2,7,3},{5,6,0,4},{9,10,11,8},{13,14,15,12}};


	int fin[N][N]={{1,2,3,4},{5,6,7,8}, {9,10,11,12}, {13,14,15,0}};
/*
//takes 30+ steps to solve 
int initial[N][N] = {{8,6,7},
{2,5,4},
{3,0,1}};
int fin[N][N] = {{1,2,3},
{4,5,6},
{7,8,0}};*/
	int x_c,y_c,i,j,heu;
	for(i=0;i<N;i++)
	    for(j=0;j<N;j++)
		if(initial[i][j] == 0)
		   {x_c =i;
		    y_c =j;
		    break;}
        if(isSolvable(initial)){
	   printf("THE PUZZLE IS SOLVABLE\n");
	   printf("THE BLANK IS AT %d %d\n\n",x_c,y_c);
	   //scanf("%d",&heu);
	   //printf("THIS MAY TAKE SOME TIME PLEASE WAIT\n");
 	   play(initial,fin,x_c,y_c,0);
	   printf("THE NO OF NODES ADDED TO OPEN LIST - %d CLOSED LIST - %d\n\n",node_count,node_count_cl);
	   printf("NO OF STEPS TAKEN TO CONVERGE %d\n\n",path_count-1);
	   count_open_and_closed();
	}
	else
	   printf("THE PUZZLE IS NOT SOLVABLE \n");

return 0;
	
}

/*
//takes 15+ steps to solve
{5,1,7,3}, 
{9,2,11,4}, 
{13,6,15,8},
{0,10,14,12}

//takes 20+ steps to solve
{1,2,3,4}, 
{5,6,7,8}, 
{13,10,11,12},
{9,15,14,0}


//takes 50+ steps
{1,10,15,4},{13,6,3,8},{2,9,12,7},{14,5,0,11}

//takes 60+ steps
{2,5,13,12},
			   {1,0,3,15},
			   {9,7,14,6},
			   {10,11,8,4}

//
{6,2,8,4},
{12,14,1,10}, 
{13,15,3,9}, 
{11,0,5,7}
//
{5,8,7,11}, 
{1,6,12,2}, 
{9,0,13,10},
{14,3,4,15}
{1,2,4},
			   {3,0,8},
			   {7,5,6}
{1,2,3},
			   {4,7,8},
			   {0,5,6}*/