Robert Setiadi Web Site - N Queen Problem (1)

// N Queen Problem : versi 8  by Robert Setiadi
// This code is able to generate all pattern combinations
// and display the backtracking counter.

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <iomanip.h>
#include <math.h>
#include <dos.h>

int jawab[1001];
char boleh[1001];
int posisi,i,j,n,counter,tampil;
unsigned long int jback;
struct time t1,t2;
unsigned long kemungkinan;
char kmb,pertama,terus;

void generate_sah() {
   int i,dx;
   for(i=1;i<=n;i++) boleh[i]=1;
   for(i=1;i<posisi;i++) {
      boleh[jawab[i]]=0;dx=posisi-i;
      if(jawab[i]-dx>=1) boleh[jawab[i]-dx]=0;
      if(jawab[i]+dx<=n) boleh[jawab[i]+dx]=0;
   }
}

void waktu(char tanda) {
    struct time t;
    if(tanda==3) {
       printf("Starting time : %2d:%02d:%02d.%02d\n",
                  t1.ti_hour, t1.ti_min, t1.ti_sec, t1.ti_hund);
       printf("Current time  : %2d:%02d:%02d.%02d\n",
                  t2.ti_hour, t2.ti_min, t2.ti_sec, t2.ti_hund);
    }
    else gettime(&t);
    if(tanda==1) t1=t; if(tanda==2) t2=t;
}

void main() {
   clrscr();
   cout<<"Artificial Intelligence : Queen Problem - version 8.0"<<endl
         <<"programmed by Robert Setiadi\n\n";
   do {
      cout<<"Please input number (4-1000) for N : ";
      cin>>n;
   } while (n<4 || n>1000);
   do {
      cout<<"Display all possible combinations (Y/N) ? ";
      kmb=getche();
   } while (!(kmb=='y' || kmb=='Y' || kmb=='n' || kmb=='N'));
   if(kmb=='n' || kmb=='N') pertama=1; else pertama=0;
   waktu(1);cout<<endl;
   for(i=1;i<=n;i++) jawab[i]=0;                       // initialization
   counter=0;posisi=1;kemungkinan=1;terus=1;jback=0;
   do {
      cout<<endl;
      do {
         if(jawab[posisi]>=n) {
            if(posisi!=1) jawab[posisi]=0;
            posisi--;
            counter--;
         }
         else {
            j=jawab[posisi]+1;
            generate_sah();
            while(!boleh[j] && j<=n) {
               j++;
            }
            if(j<=n) {
               jawab[posisi]=j;
               counter++;
               posisi++;
            }
            else {
               jawab[posisi]=0;
               posisi--;
               counter--;
               jback++;
            }
         }
         if(counter<n && counter>=0) terus=1; else terus=0;
         if(counter==-1 && !pertama) terus=0;
      } while(terus);
      if(counter==n) {
         waktu(2);
         tampil=0;
         if(!pertama) cout<<"Kemungkinan ke "<<kemungkinan<<" :\n";
         cout<<setiosflags(ios::left);
         for(i=1;i<=n;i++) {
            cout<<'Q'<<setw(4)<<i<<"=("<<setw(4)<<i<<','<<setw(4)<<jawab[i]<<")  ";
            tampil++;if(tampil>=4) { cout<<endl; tampil=0; }
         }
         if(!pertama) {
            cout<<"\nPress any key ... ";
            kmb=getch();
            cout<<endl;
            kemungkinan++;
            posisi=1;
            counter=0;
            for(i=1;i<n;i++) jawab[i]--;
         }
      }
   } while(counter!=-1 && !pertama);
   cout<<endl;
   if(!pertama) cout<<"Ada "<<(kemungkinan-1)<<" pola.";
   cout<<"\nJumlah backtracking = "<<jback<<" \n";waktu(3);
   cout<<"copyright(c)1999 by Robert Setiadi - All Rights Reserved\n";
}