Robert Setiadi Web Site - N Queen Problem (2)

// N Queen Problem : versi 6 by Daniel Handoko
// Hasil ditampilkan dengan menggunakan grafik

#include<stdio.h>
#include<iostream.h>
#include<conio.h>
#include<dos.h>
#include<graphics.h>
#include<stdlib.h>

int jml,x,y,level,level1,queen[51],posx,posy;
char row[51];
long double waktu[51],waktuasli[51];
unsigned long solusi,backtrack;
struct time t1,t2;
FILE *pf;

void initialize(void)
{for(x=1;x<=jml;x++){queen[x]=0;row[x]=0;}
 level=0;solusi=0;backtrack=0;
};

void graph(void)
{int a = DETECT,b,y;
 initgraph(&a,&b,"");
 y=getmaxy()-(getmaxy()*1/4);
 setcolor(4);moveto(1,y);
 for(a=1;a<=jml;a++)
	{lineto(a*10,y-waktuasli[a]);}
 getch();
 closegraph();
}

void saving(void)
{int i;
 if((pf=fopen("data.txt","w"))==NULL)
	{printf("KESALAHAN : file tidak dapat dibuka !!!\7n");
	 exit(1);
	}
};

void mark(void)
{int phi;
 for(x=1;x<=jml;x++){row[x]=0;}
 for(y=1;y<level;y++)
	{row[queen[y]]=1;phi=level-y;
	 if(queen[y]-phi>=0){row[queen[y]-phi]=1;}
	 if(queen[y]+phi<=jml){row[queen[y]+phi]=1;}
	}
};
void marking(void)
{int phi;
 for(x=1;x<=jml;x++){row[x]=0;}
 for(y=1;y<level1;y++)
	{row[queen[y]]=1;phi=level1-y;
	 if(queen[y]-phi>=0){row[queen[y]-phi]=1;}
	 if(queen[y]+phi<=jml){row[queen[y]+phi]=1;}
	}
};
void back(void)
{char find;
 do
 {for(x=1;x<=jml;x++){row[x]=0;}
  find=0;level--;mark();
  row[queen[level]]=1;
  for(x=queen[level];x<jml;x++)
  {if(row[x]==0)
	{queen[level]=x;
	 find=1;break;
	}
  }
 }while(find==0);
};

void control(void)
{int i=0;
 char find=0;
 do{level++;find=0;
	mark();
	for(i=1;i<=jml;i++)
		{if(row[i]==0)
			{queen[level]=i;
			 find=1;
			 if(level==jml)solusi++;
			 break;
			}
		}
	if(find==0){backtrack++;back();}
 }while(solusi==0);
};

void TimeCount(char pil)
{struct time t;
 float count;
 if(pil==3)
	{count=((t2.ti_hour*3600)+(t2.ti_min*60)+(t2.ti_sec)+(t2.ti_hund*0.01))-
		   ((t1.ti_hour*3600)+(t1.ti_min*60)+(t1.ti_sec)+(t1.ti_hund*0.01));
	 waktu[jml]=count;
	}
 else gettime(&t);
 if(pil==1) t1=t;
 if(pil==2) t2=t;
}

void main(void)
{int i,b;
 long double get=0;
 saving();
 do{clrscr();
	printf("jumlah queen [4..50] : ");scanf("%d",&jml);
 }while(jml<4 || jml>50);
 b=jml;jml=3;
 do{
	jml++;
	backtrack=0;solusi=0;
	printf("Processing...");
	TimeCount(1);control();TimeCount(2);TimeCount(3);
	for(i=1;i<=jml;i++){get=get+waktu[i];waktuasli[jml]=get;}
	gotoxy(1,wherey());clreol;
	printf("%d Queen = %3.2Lf detik, %lu Backtrack\n",jml,get,backtrack);
	fprintf(pf,"%d Queen = %3.2Lf detik, %lu Backtrack\n",jml,get,backtrack);
	get=0;
 }while(b>jml);
 getch();graph();
};