/////////////////////////////////////////////////////////////////////
//Artificial Intelligence I
//8-puzzle problem solver using search algrithms
//IDS, A* with "tiles out of place" and A* with "manhattan distance".
//includes simple user interface
//written by Gerson Paulo, 10/8/2005
//written in Ansi C++ and best compiled by Borland C++ 3.1 for DOS
/////////////////////////////////////////////////////////////////////
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <dos.h>
#include <math.h>
#include <conio.h>
#define max_number_of_states_there_can_be_at_any_deep 500
FILE *report;
//transfer k th memory location of a[][][] to b[][]
void t_1(int k, int a[4][3][3], int b[3][3]){
int i,j;
for(i=0;i<3;i++)for(j=0;j<3;j++)b[i][j]=a[k][i][j];
}
//transfer k th memory location of a[][][] to b[][]
void t_2(int k, int a[max_number_of_states_there_can_be_at_any_deep][3][3], int b[3][3]){
int i,j;
for(i=0;i<3;i++)for(j=0;j<3;j++)b[i][j]=a[k][i][j];
}
//transfer k th memory location of a[][][] to b[][]
void i_t_1(int b[3][3], int k, int a[4][3][3]){
int i,j;
for(i=0;i<3;i++)for(j=0;j<3;j++)a[k][i][j]=b[i][j];
}
//transfer k th memory location of a[][][] to b[][]
void i_t_2(int b[3][3], int k, int a[max_number_of_states_there_can_be_at_any_deep][3][3]){
int i,j;
for(i=0;i<3;i++)for(j=0;j<3;j++)a[k][i][j]=b[i][j];
}
//prints the puzzle board on the screen
void display_tiles(int a[3][3]){
int i,j;
for(i=0;i<3;i++){
printf("\n"); fprintf(report,"\n");
for(j=0;j<3;j++)
if(a[i][j]==0){
fprintf(report," ");
printf(" ");}else {
fprintf(report,"%d ",a[i][j]);
printf("%d ",a[i][j]);}
}
}
//calculates number of the tiles out of place
// a[][] is current puzzle board, b[][] is the goal
int tiles_out_of_place(int a[3][3], int b[3][3]){
int i,j,k=0;
for(i=0;i<3;i++) for(j=0;j<3;j++) if(a[i][j]!=0) if(a[i][j]!=b[i][j]) ++k;
return k;
}
//finds coordinates of a given tile on a puzzle board
//a[][] is the puzzle board
//b[][] is the tile to be found on the puzzle board
//l[][] is the coordinate vector that will be returned to the function calling this func
void find_coordinate_of_a_tile(int a[3][3], int b, int l[2]){
int i,j;
for(i=0;i<3;i++)for(j=0;j<3;j++) if(a[i][j]==b) {l[0]=i;l[1]=j;return;}
}
//calculates the total manhattan distance value of the tiles on a puzzle board
//a is current allocation
//b is goal allocation
int manhattan_distance(int a[3][3], int b[3][3]){
int i,j,l[2],m[2],t=0;
for(i=0;i<3;i++){
for(j=0;j<3;j++)
if(a[i][j]!=0){
m[0]=i;m[1]=j;
find_coordinate_of_a_tile(b,a[i][j],l);
m[0]-=l[0];m[1]-=l[1];
if(m[0]<0) m[0]*=-1;if(m[1]<0) m[1]*=-1;
t+=(m[0]+m[1]);
}
}
return t;
}
//keystroke request
void press_a_key(void){
char a;
printf("\nPress any key to continue, ESC to exit");
fprintf(report,"\nPress any key to continue, ESC to exit");
a=getch();
if(a==27) exit(0);
}
//returns a random 1 or 0
int custom_random(void){
double a,b,c;
int i,k,l;
k=rand();
l=rand();
a=0.0;
b=0.0;
for(i=0;i<k;i++) a+=1.0*rand();
for(i=0;i<l;i++) b+=1.0*rand();
c=cos(a)*sin(b);
if(c<0.0) return 0;else return 1;
}
int pick_a_number_between_0_to_3(void){
double a,b,c;
int i,k,l;
k=rand();
l=rand();
a=0.0;
b=0.0;
for(i=0;i<k;i++) a+=1.0*rand();
for(i=0;i<l;i++) b+=1.0*rand();
c=cos(a)*sin(b);
if(c<-0.5) return 0;else
if(c>=-0.5&c<0.0) return 1;else
if(c>=0.0&c<0.5) return 2;else
if(c>=0.5&c<=1.0) return 3;
return 0;
}
//copies a[][] into b[][] a-->b
void copy_series(int a[3][3],int b[3][3]){
int i,j;
for(i=0;i<3;i++)for(j=0;j<3;j++) b[i][j]=a[i][j];
}
//randomly creates a new state from a given {a[3][3]} state
//new state will be in b[3][3]
void randomly_create_a_new_state_from_a_given_state(int a[3][3],int b[3][3]){
int i,j,l[2],xr,yr,t;
copy_series(a,b);
find_coordinate_of_a_tile(b,0,l);
do{
xr=l[0];
yr=l[1];
if(custom_random()==0)
{if(custom_random()==0)--xr;else ++xr;}
else
{if(custom_random()==0)--yr;else ++yr;}
}while(xr<0||xr>2||yr<0||yr>2);
t=b[xr][yr];
b[xr][yr]=0;
b[l[0]][l[1]]=t;
}
//expands a state and puts results into b[][][]
//b can have maximum 4 different state:right,left,up,down
//non-existing states have number -1 in their memory locations
void expand_a_state(int a[3][3],int b[4][3][3]){
int i,j,k;
int c[3][3],l[2];
//clear up b[][][]
for(i=0;i<4;i++)for(j=0;j<3;j++)for(k=0;k<3;k++) b[i][j][k]=-1;
//find coordinates of the space
find_coordinate_of_a_tile(a,0,l);
if(l[0]!=0) {copy_series(a,c);c[l[0]][l[1]]=c[l[0]-1][l[1]];c[l[0]-1][l[1]]=0;i_t_1(c,0,b);}
if(l[0]!=2) {copy_series(a,c);c[l[0]][l[1]]=c[l[0]+1][l[1]];c[l[0]+1][l[1]]=0;i_t_1(c,1,b);}
if(l[1]!=0) {copy_series(a,c);c[l[0]][l[1]]=c[l[0]][l[1]-1];c[l[0]][l[1]-1]=0;i_t_1(c,2,b);}
if(l[1]!=2) {copy_series(a,c);c[l[0]][l[1]]=c[l[0]][l[1]+1];c[l[0]][l[1]+1]=0;i_t_1(c,3,b);}
}
//expands all states of a[][][] into b[][][]
void expand_all_states_at_deep_x(int a[max_number_of_states_there_can_be_at_any_deep][3][3],int b[max_number_of_states_there_can_be_at_any_deep][3][3]){
int i,j,k,c[4][3][3],t[3][3],l,m;
k=0;
for(i=0;i<max_number_of_states_there_can_be_at_any_deep;i++)
if(a[i][0][0]!=-1){
t_2(i,a,t);
expand_a_state(t,c);
for(j=0;j<4;j++) if(c[j][0][0]!=-1){
++k;
for(l=0;l<3;l++)for(m=0;m<3;m++) b[k][l][m]=c[j][l][m];
}
}
}
void clear_an_IDS_layer(int a[max_number_of_states_there_can_be_at_any_deep][3][3]){
int i,j,k;
//clear memory
for(i=0;i<max_number_of_states_there_can_be_at_any_deep;i++)
for(j=0;j<3;j++)
for(k=0;k<3;k++)
a[i][j][k]=-1;
}
//returns 1 if equal, otherwise 0
int compare_two_states(int a[3][3],int b[3][3]){
int i,j;
for(i=0;i<3;i++)for(j=0;j<3;j++)if(a[i][j]!=b[i][j]) return 0;
return 1;
}
//returns 1 if any one of states equal the goal, otherwise 0
int compare_all_states_in_a_layer_with_goal_state(int a[max_number_of_states_there_can_be_at_any_deep][3][3],int b[3][3]){
int i,t[3][3];
for(i=0;i<max_number_of_states_there_can_be_at_any_deep;i++)
if(a[i][0][0]!=-1)
{
t_2(i,a,t);
if(compare_two_states(t,b)==1) return 1;
}
return 0;
}
void main(void){
int goal[3][3],//goal state
start[3][3],//start states, that will be determined randomly
expanded_states[4][3][3],
temporary[3][3],//for temporary use
d,mvs,i,j,k,l[4],m,n,
current_layer_of_IDS[max_number_of_states_there_can_be_at_any_deep][3][3],
next_layer_of_IDS[max_number_of_states_there_can_be_at_any_deep][3][3],
t[3][3];
char a;
if((report=fopen("c:\\report.wri","wt"))==NULL) {
clrscr();
printf("File 'c:/report.wri' can't be created");
getch();
exit(0); }
fprintf(report,"\n\n\nArtificial Intelligence, 8-puzzle solver\n\nWritten by Atilla Demiray\n\n\n\n");
do{
n=0;
for(i=0;i<3;i++)for(j=0;j<3;j++) goal[i][j]=i*3+j;//create a goal
//clear screen and keyboard buff
clrscr();while(kbhit()) getch();
//initialize randomizer
randomize();
printf("\n\n\nHow many random moves has to be made\nto create Start States from the Goal state = ");
fprintf(report,"\n\n\nHow many random moves has to be made\nto create Start States from the Goal state = ");
scanf("%d",&mvs);
fprintf(report,"%d",mvs);
do{
clrscr();
printf("\n\nPlease wait. A start state is randomly being created in %d moves",mvs);
fprintf(report,"\n\nPlease wait. A start state is randomly being created in %d moves",mvs);
copy_series(goal,temporary);
for(j=0;j<mvs;j++) {
randomly_create_a_new_state_from_a_given_state(temporary,start);
copy_series(start,temporary);
}
clrscr();
if(n==0){
printf("\n\n\nFirst, A* manhattan distance algorithm will be used to search the Goal\n");
fprintf(report,"\n\n\nFirst, A* manhattan distance algorithm will be used to search the Goal\n");
}
else
if(n==1){
printf("\n\n\nNow A* tiles out of place algorithm will be used to search the Goal\n");
fprintf(report,"\n\n\nNow A* tiles out of place algorithm will be used to search the Goal\n");
}
else
if(n==2){
printf("\n\n\nFinaly IDS algorithm will be used to search the Goal\n");
fprintf(report,"\n\n\nFinaly IDS algorithm will be used to search the Goal\n");
}
press_a_key();
clrscr();
printf("\n\n\nThe following are the start and the goal states.\n\n");
fprintf(report,"\n\n\nThe following are the start and the goal states.\n\n");
printf("Start State:\n");
fprintf(report,"Start State:\n");
display_tiles(start);
printf("\n\n\nGoal State:\n");
fprintf(report,"\n\n\nGoal State:\n");
display_tiles(goal);
printf("\n\nPress any key to start the search");getch();clrscr();
fprintf(report,"\n\nPress any key to start the search");
copy_series(start,temporary);
//IDS search
if(n==2){
clear_an_IDS_layer(current_layer_of_IDS);
i_t_2(start,0,current_layer_of_IDS);
d=0;
//start search
while(1){
clrscr();
printf("\nDeep=%d",++d);
fprintf(report,"\nDeep=%d",d);
clear_an_IDS_layer(next_layer_of_IDS);
expand_all_states_at_deep_x(current_layer_of_IDS,next_layer_of_IDS);
printf("\n\nExpanded states:\n");
fprintf(report,"\n\nExpanded states:\n");
for(i=0;i<max_number_of_states_there_can_be_at_any_deep;i++)
if(next_layer_of_IDS[i][0][0]!=-1){
t_2(i,next_layer_of_IDS,t);
display_tiles(t);
printf("\n");fprintf(report,"\n");
}
if(compare_all_states_in_a_layer_with_goal_state(next_layer_of_IDS,goal)==1){
//game over
printf("\nOne state in deep %d matches the goal state, GAME OVER !\n\n",d);
fprintf(report,"\nOne state in deep %d matches the goal state, GAME OVER !\n\n",d);
press_a_key();
break;
}
else{
for(i=0;i<max_number_of_states_there_can_be_at_any_deep;i++)
for(j=0;j<3;j++)for(k=0;k<3;k++)
current_layer_of_IDS[i][j][k]=next_layer_of_IDS[i][j][k];
printf("\nNone of the states in deep %d isn't equal to the goal state\n\n",d);
fprintf(report,"\nNone of the states in deep %d isn't equal to the goal state\n\n",d);
press_a_key();
}
}
}
else
{//A* searches
do{
printf("State to be expanded:");
fprintf(report,"\n\nState to be expanded:");
display_tiles(temporary);
expand_a_state(temporary,expanded_states);
printf("\n\nExpanded branches:");
fprintf(report,"\n\nExpanded branches:");
for(i=0;i<4;i++) l[i]=-1;
j=100;
for(i=0;i<4;i++)
if(expanded_states[i][0][0]!=-1){
t_1(i,expanded_states,t);
display_tiles(t);
if(n==0)k=manhattan_distance(t,goal);
else
k=tiles_out_of_place(t,goal);
l[i]=k;
if(k<j) {j=k;m=i;}
if(n==0){
printf(" Manhattan distance=%d\n",k);
fprintf(report," Manhattan distance=%d\n",k);
}else{
printf(" Tiles out of place=%d\n",k);
fprintf(report," Tiles out of place=%d\n",k);
}
}
if(n==0){
printf("\nSmallest Manhattan Distance is %d",j);
fprintf(report,"\nSmallest Manhattan Distance is %d",j);
}else{
printf("\nSmallest number of tiles out of place is %d",j);
fprintf(report,"\nSmallest number of tiles out of place is %d",j);
}
if(j==0){ printf("\n\n\n GAME OVER !\n"); fprintf(report,"\n\n\n GAME OVER !\n");}
k=0;for(i=0;i<4;i++)if(l[i]==j) ++k;
if(k>1){
do{i=pick_a_number_between_0_to_3();m=i;}while(l[i]!=j);
}
printf("\nPress 'SPACE' key to continue, 'ESC' to exit, 'N' to skip this search");
fprintf(report,"\nPress 'SPACE' key to continue, 'ESC' to exit, 'N' to skip this search");
a=getch();
if(a==27) exit(0);
if(a=='n'||a=='N') break;
t_1(m,expanded_states,temporary);
clrscr();
}while(j!=0);
}
}while(++n<3);
a='?';
do{
clrscr();
printf("Would you like to do it again? (Y/N)");
fprintf(report,"Would you like to do it again? (Y/N)");
a=getch();
}while(!(a=='y'||a=='Y'||a=='n'||a=='N'));
}while(a=='y'||a=='Y');
fclose(report);
}//The End