N-Queen Problem (2)

N Queen problem is a classic constraint satisfaction problem based on chess game.
The idea is how to put N numbers of Queen in N x N chessboard without giving them any chance to kill each other in one turn.

This post is a continuation from my previous post (click here).

Here is another version of algorithm, written by my friend, Daniel Handoko. This post is published by his approval.

<pre>// N Queen Problem : versi 6 by Daniel Handoko
// Results are displayed with graphic

#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();
};
</pre>