Program C++ N Queen Secara Rekursif

Program C++ N Queen Secara Rekursif - Program n queen atau n ratu adalah masalah menempatkan n catur ratu pada papan catur n × n sehingga tidak ada dua ratu atau lebih menyerang satu sama lain atau saling memakan. Dengan demikian, solusi mensyaratkan bahwa tidak ada dua ratu atau lebih berbagi baris yang sama, kolom, atau diagonal.

Implementasi program n queen menggunakan bahasa c++ bisa menggunakan dua jenis perulangan. Yang pertama secara iteratif dan secara rekursif. Berikut ini adalah program c++ penempatan n ratu secara rekursif : (lihat juga program c++ nqueen secara iteratif)

#include <cstdlib>

#include <iostream>

#include <math.h>

using namespace std;

void cetakSolusi(int x[],int n){

    int i,j;

    char c[100][100];

    for(i=1;i<=n;i++)

    {

        for(j=1;j<=n;j++)

        {

            c[i][j]='X';

        }

    }

    for(i=1;i<=n;i++)

    {

        c[i][x[i]] ='Q';

    }

    for(i=1;i<=n;i++)

    {

        for(j=1;j<=n;j++)

        {

            cout<<"\t"<<c[i][j];

        }

    cout<<endl;

    }

    cout<<endl;

}

bool tempat (int x[], int k ){

int i;

bool stop, kedudukan;

kedudukan = true;

i = 1;

stop = false;

while((i<k) && (!stop)){

if((x[i]==x[k]) || (abs(x[i]-x[k])==abs(i-k))){

kedudukan = false;

stop = true;

}else{

i++;

}

}

return kedudukan;

}

void nRatuR(int n, int k, int x[]){

bool stop;

stop = false;

while(!stop){

x[k] +=1;

        while((x[k] <= n) && ( !tempat(x,k))){

            x[k] +=1;

        }

        

        if(x[k] <= n){

            if(k == n){

                cetakSolusi(x,n);

            }else{

                nRatuR(n,k+1,x);

            }

        }

        else{

            stop = true;

            x[k]=0;

        }

}

}

int main(int argc, char *argv[])

{

    system("color f2");

    system("title Program N_Ratu - 1 Juni 2012 - dyasprogramming.blogspot.com");

    

    awal:

    int n;

    int x [100];

    cout<<"Masukkan banyak ratu : ";

    cin>>n;

    cout<<"\n\nKemungkinan yang didapatkan :\n\n";

nRatuR(n,1,x);

    cout<<"\nIngin mengulang ? (y/n) : ";

    char p;

    cin>>p;

    if(p=='y') {

               system("cls");

               goto awal;

               }

    else return EXIT_SUCCESS;

}