Algoritma Ornegi Atın Turu

[Jey@Nfer]

Arkadaşlar mateatikçi Euler tarafından ortaya atılmış olan atın turu problemi(http://tr.wikipedia.org/wiki/At_turu)  için yazdığım  ; iyi bir algoritma örneği olabileceğini düşündüğüm kodu paylaşıyorum.
Fazla bir c bilgisine gerek yok algoritması da çok karmaşık değil hatta bazı durumlarda çözemiyor fakat bir defa yazdıktan sora tekrar inceleyemedim .
Belki işinize yarar, örnek olabilir diyerekten koyuyorum.

Kod Seç Genişlet


#include <stdio.h>
#define SATIR 8
#define SUTUN 8


int duzlem[SATIR][SUTUN];

int yatay[8], dikey[8];

int konum_x, konum_y;

int sayac=1;

int KacIhtimalVar(const int sayi);

int HamleSec();

void Yazdir();

int main()
{
    konum_x=-1; konum_y=-1;

    int i, j, sayi;

     yatay[0]=2;  yatay[1]=1; yatay[2]=-1; yatay[3]=-2; yatay[4]=-2; yatay[5]=-1; yatay[6]=1; yatay[7]=2;

    dikey[0]=-1; dikey[1]=-2; dikey[2]=-2; dikey[3]=-1;  dikey[4]=1;  dikey[5]=2; dikey[6]=2; dikey[7]=1;



    for(i=0;i<SATIR;i++)
        for(j=0;j<SUTUN;j++)
            duzlem[i][j]=0;


    while(konum_x<0 || konum_x>SATIR-1)
    {
        printf("Satir (0-%d) : ",SATIR-1);
        scanf("%d",&konum_x);
    }

    while(konum_y<0 || konum_y>SUTUN-1)
    {
        printf("Sutun (0-%d) : ",SUTUN-1);
        scanf("%d",&konum_y);
    }

    duzlem[konum_x][konum_y]=1;

    sayac=1;

    while(1)
    {
        getchar();

        Yazdir();

        sayac++;
        i=HamleSec();

        if(i==8)
        {
            if(sayac==(SATIR*SUTUN)+1)
            {
                getchar();
                Yazdir();
                printf("Butun karelere ulasildi\n");
                printf("TEBRIKLER \n");
            }

            else
            {
                getchar();
                Yazdir();
                printf("Ne yazik ki butun karelere ulasilamadi \n");
            }

            printf("Cikmak icin bir tusa basiniz \n");
            getchar();
        return 0;
        }

        else
        {
            konum_x+=yatay[i];
            konum_y+=dikey[i];
        }


        duzlem[konum_x][konum_y]=sayac;

    }//for0

}//main

void Yazdir()
{
    int i,j;

    if(sayac==(SATIR*SUTUN)+1)
    {
        printf("\nTEBRIKLER! \n");
    }

    else    printf("sayac : %d \n",sayac);

    for(i=0;i<SATIR;i++)
    {
        for(j=0;j<SUTUN;j++)
        {
            if(duzlem[i][j]==0)
            {
                printf("  .  ");
            }

            else
            {
                if(duzlem[i][j]==sayac) printf("%c[%d;%d;%dm%3d  %c[%dm",27, 1, 31, 47,duzlem[i][j],27,0);

                else printf("%3d  ",duzlem[i][j]);
            }
        }

        printf("\n\n");
    }
}

int HamleSec()
{
    int hamle[8];

    int i, kucuk, adet;

    int seviye, seviye_x, seviye_y;

    for(i=0;i<8;i++)
    {
        if( (konum_x+yatay[i]>=0 && konum_x+yatay[i]<SATIR) && (konum_y+dikey[i]>=0 && konum_y+dikey[i]<SUTUN) )
        {
            if(duzlem[konum_x+yatay[i]][konum_y+dikey[i]]==0)
            {
                hamle[i]=1;
            }

            else hamle[i]=0;
        }

        else hamle[i]=0;
    }

    for(i=0, kucuk=8; i<8;i++)
    {
        if(hamle[i]==1)
        {
            hamle[i]=KacIhtimalVar(i);

            if(hamle[i]=='\0')
            {
                return i;
            }

            if(hamle[i]<kucuk) kucuk=hamle[i]; // en kucuk ihtimal
        }
    }

    if(kucuk==8)
    {
        return 8; //baska hamle kalmadi;
    }

    for(i=0,adet=0; i<8; i++) //en kucuk hamleden kac tane var
    {
        if(hamle[i]==kucuk) //eger kucuke esit ise
        {adet++; seviye=i;} //adedini bir attir; ve seviye ile de en sonuncunun adresini tut
    }

    if(adet==1)
    {
            return seviye; //eger bi taneyse zaten seviye degiskeni tek olan adresi tutacak
    }

    //EGER ADET 1DEN FAZLAYSA

    for(i=0; i<8; i++) //seviyeleri buldur
    {
        if(hamle[i]==kucuk) //en kucuk ihtimali olanlara bak
        {
            seviye_x=konum_x+yatay[i];

            for( adet=1; adet<=((SATIR+1)/2); adet++)
            {
                if(seviye_x==adet-1 || seviye_x==SATIR-1)
                { seviye_x=adet; break; }
            }



            seviye_y=konum_y+dikey[i];

            for( adet=1; adet<=((SUTUN+1)/2); adet++)
            {
                if(seviye_y==adet-1 || seviye_y==SATIR-1)
                { seviye_y=adet; break; }
            }


            if(seviye_x>seviye_y)
            {
                seviye=seviye_x;
                seviye_x=seviye_y;
                seviye_y=seviye;
            }

            hamle[i]=10*seviye_x+seviye_y;
        }
    }

    for(i=0,kucuk=10*SATIR+SUTUN ; i<8 ; i++)
    {
        if(hamle[i]>8)
        {
            if(hamle[i]<kucuk) kucuk=hamle[i];
        }
    }

    for(i=0;i<8;i++)
    {
        if(hamle[i]==kucuk) return i;
    }

}//NereGitsin

int KacIhtimalVar(const int sayi )
{
    int i, adet=0;

    for(i=0;i<8;i++)
    {
        if (
            (konum_x+yatay[sayi]+yatay[i]>=0 && konum_x+yatay[sayi]+yatay[i]<8)
            &&
            (konum_y+dikey[sayi]+dikey[i]>=0 && konum_y+dikey[sayi]+dikey[i]<8)
            )
        {
            if(duzlem[konum_x+yatay[sayi]+yatay[i]][konum_y+dikey[sayi]+dikey[i]]==0)

            adet++;
        }
    }

return adet;
}//KacIhtimalVar



#define SATIR ve #define SUTUN
degerlerini degistirerek tahta boyutlarını ayarlayabilirsiniz...

Aslında bi kaç eklemeyle eğer kare adetleri bütün kareleri dolaşmaya izin vermeyecek şekilde değilse yani; eğer bir çözümü varsa %100 doğru yolu yoksa da en mantıklı yolu gösteren algoritmaya yükseltilebilir ancak şu anda inceleyemiycem.

Eğer siz ekleme yapmak isterseniz kodu geliştirip burada yayınlarsanız da sevinirim..

Yorumlarınızı bekliyorum...

Ayrıca burdan da oyununu oynayabilirsiniz : http://www.knightstour.co.uk/GameBoard.aspx