Program N Ratu

Penerapan algoritma backtracking pada permasalahan N Queens adalah teknik yang digunakan untuk menempatkan N ratu di papan catur N x N sedemikian rupa sehingga tidak ada dua ratu yang saling menyerang (tidak ada dua ratu yang berada di baris, kolom, atau diagonal yang sama).

Penerapan algoritma backtracking dalam C++ untuk menyelesaikan permasalahan N Ratu:

#include iostream;
#include math.h;

using namespace std;

bool TEMPAT(int k){
     int i;
     int x[100];
     bool stop,kedudukan,keluar;

     i=1;
     stop=false;
     while((i<k) && (!stop)){
                 if((x[i]==x[k]) || (abs(x[i]-x[k])==abs(i-k))){
                                 kedudukan=false;
                                 keluar=true;
                                 }
                 else{
                      i++;
                      }
                 }
     return kedudukan;

     }

int CetakSolusi(int N){
    int x[100][100];
    int i,j; cout<<"SUSUNAN PELETAKAN\n\t";
    for(i=0; i<=N; ++i){
             for(j=0; j<=N; ++j)
             cout<<x[i][j]<<lt;<<" ";
             cout<<endl<<"\t";
    }
}

int N_RATU_R(int k){
    bool stop;
    int N;
    int x[100];
    cout<<"Masukkan jumlah Ratu : ";
    cin>>N;
    stop=false;

    while(!stop){
                 x[k]=x[k]+1;
                 while((x[k]<=N) && (!TEMPAT(k))){
                                 x[k]=x[k]+1;
                                 }
                 if(x[k]<=N){
                             if(k=N){
                                     CetakSolusi(N);
                                     }
                             else{
                                  N_RATU_R(k+1);
                                  }
                             }
                  else {
                       stop=true;
                       x[k]=0;
                       }
                 }
    }

int main(){
    int k;

    N_RATU_R(k);

    cout<<endl;
    system("PAUSE");
    return 0;
    }

Anda dapat mengubah nilai N sesuai dengan jumlah ratu yang diinginkan, dan program akan mencoba untuk menemukan solusi yang memenuhi aturan N Queens.