Program Backtracking N Queen

Satu lagi tugas kuliah...... Disuruh bikin program C++ Backtracking N Queen. dalam hal ini h Quenn/Ratu.


intinya bagaimana kita meletakkan 5 ratu di papan berukuran 5x5 tanpa ada yang saling 'memakan' (tidak bolah ada ratu lain pada diagonal, horizontal, dan vertikal....). Langsung aja ni programnya.

#include <iostream.h>
#include <conio.h>
#define N 5                                    /** ukuran papan catur */ 


void cetak(int letak[N][N]){
 int i,j; cout<<"SUSUNAN PELETAKAN\n\t";
 for(i=0; i<N; ++i){
  for(j=0; j<N; ++j)     
cout<<letak[i][j]<<" ";  
cout<<endl<<"\t";     }
cout<<"\n";} 


/** return true jika letak Ratu di [baris][kolom] diterima, jika tidak return false */
bool accept(int letak[N][N], int baris, int kolom){int i,j;  for (i=0; i<N; ++i){                /* check kolom */ 
 if (letak[baris][i]) return false;}   


  for (i=0; i<N; ++i){                        /* check baris */
   if (letak[i][kolom]) return false;} 


  for (i=baris, j=kolom; i>=0 && j>=0; i--, j--){   /* cek diagonal kiri keatas */  
   if (letak[i][j])return false;} 


  for (i=baris, j=kolom; i<N && j>=0; ++i, --j){   /* cek diagonal kiri kebawah */
   if (letak[i][j])return false;} 


  for (i=baris, j=kolom; i>=0 && j<N; i--, ++j){   /* cek diagonal kanan keatas */ 
   if (letak[i][j])return false;} 


for (i=baris, j=kolom; i<N && j<N; ++i, ++j){ /* cek diagonal kanan kebawah */ 
   if (letak[i][j])return false;} 


return true;             /* return true jika semua test lewat */} 


void solve_letak(int letak[N][N], int baris){
int i;  if (baris == N){                                          /* jika semua ratu sudah pada posisi yg tepat */
 cetak(letak);        
 return;}


/* letakkan ratu pada baris yang ada and cek jika letak diterima, Lanjutkan proses sampai semua posisi di temukan*/
for(i=0; i<N; ++i){ 
 if(accept(letak, baris, i)){  
  letak[baris][i] = 1;  solve_letak(letak, baris+1);}  
  letak[baris][i] = 0;}} 


int main(){
int letak[N][N] = {0};
cout<<"\tProgram Bactracking N Queen 27 MEI 2012\n\n";
solve_letak (letak, 0); 


getch();
return 0;}