Breadth First Search - Implementiran u C-u

Code:
#include <iostream.h>
#include <process.h>
#include <conio.h>

struct PoljeSlagalice
{
    PoljeSlagalice *levo;
    PoljeSlagalice *desno;
    PoljeSlagalice *ispod;
    PoljeSlagalice *iznad;

    int vrednost;
    int pozicija;

    PoljeSlagalice()
    {
        levo = NULL;
        desno = NULL;
        ispod = NULL;
        iznad = NULL;
    }

    
    void copy(PoljeSlagalice *temp)
    {
        PoljeSlagalice *temp2 = this;
        temp2->vrednost=temp->vrednost;
        temp2->pozicija=temp->pozicija;
        
        
        if(temp->levo!=NULL)
        {
            temp2->levo->vrednost=temp->levo->vrednost;
            temp2->levo->pozicija=temp->levo->pozicija;
        }

        
        if(temp->desno!=NULL)
        {
            temp2->desno->vrednost=temp->desno->vrednost;
            temp2->desno->pozicija=temp->desno->pozicija;
        }

        
        if(temp->ispod!=NULL)
        {        
            temp2->ispod->vrednost=temp->ispod->vrednost;
            temp2->ispod->pozicija=temp->ispod->pozicija;
        }

        
        if(temp->iznad!=NULL)
        {
            temp2->iznad->vrednost=temp->iznad->vrednost;
            temp2->iznad->pozicija=temp->iznad->pozicija;
        }

    }

};

struct Leaves
{
    class Formacija *ptr;
    Leaves *next;
    int Index;

    Leaves(int k)
    {
        next=NULL;
        Index = k;
    }

    Leaves()
    {
        ptr=NULL;    
    }
};

int static brojac=0;


class LinkedList
{
    Leaves *head;

public:
    LinkedList(int j,Formacija *F)
    {
        head = new Leaves(j);
        head->ptr=F;
    }

    inline void add(int k, Formacija *F)
    {
        Leaves *temp = head;
        Leaves *temp2;

        while(temp->next!=NULL)
        { 
            temp = temp->next;
        }

        temp2=new Leaves(k);
        temp->next=temp2;
        temp2->ptr=F;
    }

    inline void del(int d)
    {
        Leaves *temp = head;
        Leaves *prev = head;

        if(temp==head && temp->Index==d)
        {
            head=temp->next;
            delete temp;
            return;
        }
        
        else
        {
            while(temp->Index != d )
            {    
                prev = temp;
                temp = temp->next;
            }

        
            prev->next= temp->next;
            delete temp;
            return;
        }
        


    }

    Formacija *Searchcc();
};

LinkedList *Linked;

int  brojac2=0;
struct Leaves *X=new Leaves[8000];

class Formacija
{
    PoljeSlagalice *SlobodanBlok,*Broj1,*Broj2,*Broj3,*Broj4,*Broj5,*Broj6,*Broj7,*Broj8;
    Formacija *GORE,*DOLE,*desno,*levo;
    Formacija *testGORE,*testDOLE,*testdesno,*testlevo;
    

    int C;
    int NOM;
    
    
public:
    
    int Function; 
    Formacija *Parent;
    int heuristic;
    int ZadnjiPotez;

    Formacija()
    {
        Formacija *temp = this;
          Linked = new LinkedList(brojac,temp);
        SlobodanBlok= new PoljeSlagalice();
        Broj1 = new PoljeSlagalice();
        Broj2 = new PoljeSlagalice();
        Broj3= new PoljeSlagalice();
        Broj4= new PoljeSlagalice();
        Broj5= new PoljeSlagalice();
        Broj6= new PoljeSlagalice();
        Broj7= new PoljeSlagalice();
        Broj8= new PoljeSlagalice();

        
        GORE=NULL;
        DOLE=NULL;
        desno=NULL;
        levo=NULL;

        testGORE=NULL;
        testDOLE=NULL;
        testdesno=NULL;
        testlevo=NULL;
        NOM=0;
        C=::brojac++;
        Linked->add(C,temp);
        temp->Parent=NULL;
        temp->NOM=0;
        
    }

    
    
    Formacija(int x)
    {
        GORE=NULL;
        DOLE=NULL;
        desno=NULL;
        levo=NULL;

        SlobodanBlok= new PoljeSlagalice();
        Broj1 = new PoljeSlagalice();
        Broj2 = new PoljeSlagalice();
        Broj3= new PoljeSlagalice();
        Broj4= new PoljeSlagalice();
        Broj5= new PoljeSlagalice();
        Broj6= new PoljeSlagalice();
        Broj7= new PoljeSlagalice();
        Broj8= new PoljeSlagalice();
        
        SlobodanBlok->levo=NULL;
        SlobodanBlok->desno=Broj1;
        SlobodanBlok->iznad=NULL;
        SlobodanBlok->ispod=Broj3;
            
        Broj1->levo=SlobodanBlok;
        Broj1->desno=Broj2;
        Broj1->iznad=NULL;
        Broj1->ispod=Broj4;
        
        Broj2->levo=Broj1;
        Broj2->desno=NULL;
        Broj2->iznad=NULL;
        Broj2->ispod=Broj5;
        
        Broj3->levo=NULL;
        Broj3->desno=Broj4;
        Broj3->iznad=SlobodanBlok;
        Broj3->ispod=Broj6;
                
        Broj4->levo=Broj3;
        Broj4->desno=Broj5;
        Broj4->iznad=Broj1;
        Broj4->ispod=Broj7;
    
        Broj5->levo=Broj4;
        Broj5->desno=NULL;
        Broj5->iznad=Broj2;
        Broj5->ispod=Broj8;
        
        Broj6->levo=NULL;
        Broj6->desno=Broj7;
        Broj6->iznad=Broj3;
        Broj6->ispod=NULL;
    
        Broj7->levo=Broj6;
        Broj7->desno=Broj8;
        Broj7->iznad=Broj4;
        Broj7->ispod=NULL;
        Broj7->pozicija=7;
        Broj7->vrednost=7;
        
        Broj8->levo=Broj7;
        Broj8->desno=NULL;
        Broj8->iznad=Broj5;
        Broj8->ispod=NULL;
    
    }


    
    inline void doExpansion()
    {
        Formacija *temp;
        temp= this;
        temp->getHeuristic();

        if(temp->MogucPotezGore())
        {
            temp->GORE=temp->PomeriGore();
            temp->GORE->Parent=temp;
            temp->GORE->getHeuristic();
            temp->GORE->ZadnjiPotez=1;
            temp->GORE->C=::brojac;
            brojac++;
            Linked->add(temp->GORE->C,temp->GORE);
        }
        

        if(temp->MogucPotezDole())
        {
    
            temp->DOLE=temp->PomeriDole();
            temp->DOLE->Parent=temp;
            temp->DOLE->getHeuristic();
            temp->DOLE->ZadnjiPotez=2;
            temp->DOLE->C=::brojac;
            brojac++;
            Linked->add(temp->DOLE->C,temp->DOLE);
        }
        
        

        if(temp->MogucPotezLevo())
        {
            temp->levo=temp->PomeriLevo();
            temp->levo->Parent=temp;
            temp->levo->getHeuristic();
            temp->levo->ZadnjiPotez=4;
            temp->levo->C=::brojac;
            brojac++;
            Linked->add(temp->levo->C,temp->levo);
        }

        if(temp->MogucPotezDesno())
        {
    
            temp->desno=temp->PomeriDesno();
            temp->desno->Parent=temp;
            temp->desno->getHeuristic();
            temp->desno->ZadnjiPotez=3;
            temp->desno->C=::brojac;
            brojac++;
            Linked->add(temp->desno->C,temp->desno);
            
        }

        Linked->del(temp->C);        
    }

    void Init(int *a)
    {
        SlobodanBlok->levo=NULL;
        SlobodanBlok->desno=Broj1;
        SlobodanBlok->iznad=NULL;
        SlobodanBlok->ispod=Broj3;
        SlobodanBlok->pozicija=0;
        SlobodanBlok->vrednost=a[0];
        
        Broj1->levo=SlobodanBlok;
        Broj1->desno=Broj2;
        Broj1->iznad=NULL;
        Broj1->ispod=Broj4;
        Broj1->pozicija=1;
        Broj1->vrednost=a[1];
        
        Broj2->levo=Broj1;
        Broj2->desno=NULL;
        Broj2->iznad=NULL;
        Broj2->ispod=Broj5;
        Broj2->pozicija=2;
        Broj2->vrednost=a[2];
        
        Broj3->levo=NULL;
        Broj3->desno=Broj4;
        Broj3->iznad=SlobodanBlok;
        Broj3->ispod=Broj6;
        Broj3->pozicija=3;
        Broj3->vrednost=a[3];
        
        Broj4->levo=Broj3;
        Broj4->desno=Broj5;
        Broj4->iznad=Broj1;
        Broj4->ispod=Broj7;
        Broj4->pozicija=4;
        Broj4->vrednost=a[4];
        
        Broj5->levo=Broj4;
        Broj5->desno=NULL;
        Broj5->iznad=Broj2;
        Broj5->ispod=Broj8;
        Broj5->pozicija=5;
        Broj5->vrednost=a[5];
        
        Broj6->levo=NULL;
        Broj6->desno=Broj7;
        Broj6->iznad=Broj3;
        Broj6->ispod=NULL;
        Broj6->pozicija=6;
        Broj6->vrednost=a[6];
        
        Broj7->levo=Broj6;
        Broj7->desno=Broj8;
        Broj7->iznad=Broj4;
        Broj7->ispod=NULL;
        Broj7->pozicija=7;
        Broj7->vrednost=a[7];
        
        Broj8->levo=Broj7;
        Broj8->desno=NULL;
        Broj8->iznad=Broj5;
        Broj8->ispod=NULL;
        Broj8->pozicija=8;
        Broj8->vrednost=a[8];
        
        }


    bool goalState()
    {
        Formacija *temp = this;
            
        if(heuristic==0)
            return true;

        else 
            return false;
        return false;

    }

    inline void getHeuristic()
    {
        Formacija *temp=this;
        
        int h=0;
        
        switch(temp->nadjiPrvo()->pozicija)
        {
        case 0:
        case 2:
        case 4: h+=1; break; 
        case 3:
        case 5:
        case 7: h+=2; break; 
        case 6:
        case 8: h+=3; break;
        default:break;
        }
        switch(temp->nadjiDrugo()->pozicija)
        {
        case 1:
        case 5: h+=1; break; 
        case 0:
        case 4:
        case 8: h+=2; break; 
        case 3:
        case 7: h+=3; break;
        case 6: h+=4; break;
        default:break;
        }
        switch(temp->nadjiTrece()->pozicija)
        {
        case 0:
        case 4:
        case 6: h+=1; break; 
        case 1:
        case 7:
        case 5: h+=2; break; 
        case 2: 
        case 8: h+=3; break;
        default:break;
        }

        switch(temp->nadjiCetvrto()->pozicija)
        {
        case 1:
        case 3:
        case 5:
        case 7: h+=1; break; 
        case 2:
        case 0: 
        case 6: 
        case 8: h+=2; break; 
        default:break;
        }

        switch(temp->nadjiPeto()->pozicija)
        {
        case 2:
        case 4:
        case 8: h+=1; break; 
        case 7:
        case 1:
        case 3: h+=2; break;
        case 6: 
        case 0: h+=3; break; 
        default:break;
        }

        switch(temp->nadjiSesto()->pozicija)
        {
        case 7:
        case 3: h+=1; break; 
        case 0:
        case 4:
        case 8:h+=2; break;
        case 5: 
        case 1: h+=3; break; 
        case 2: h+=4; break;
        default:break;
        }

        
        switch(temp->nadjiSedmo()->pozicija)
        {
        case 4:
        case 6:
        case 8: h+=1; break; 
        case 1:
        case 3:
        case 5: h+=2; break; 
        case 0: 
        case 2: h+=3; break; 
        default:break;
        }

        switch(temp->nadjiOsmo()->pozicija)
        {
        case 5:
        case 7: h+=1; break; 
        case 2: 
        case 4:
        case 6: h+=2; break; 
        case 1:
        case 3: h+=3; break; 
        case 0: h+=4; break;
        default:break;
        }

        heuristic =  h;
        if(temp->Parent!=NULL)
        {
            NOM=temp->Parent->NOM+1;
            Function = heuristic + NOM;
        }
        
    }

    
    bool Provera(int *h, int *t)
    {
        for(int i=0;i<9;i++)
            if(t[i]!=h[i])
            {
                delete []h;
                delete []t;
                return false;
            }
            delete []h;
            delete []t;
        return true;
    }

    

    Formacija* getMinHeuristic()
    {
        Formacija *temp=Linked->Searchcc();
        return temp;
    }

    PoljeSlagalice* Search(int val)
    {
        
        if(SlobodanBlok->vrednost==val)
            return SlobodanBlok;
        else if (Broj1->vrednost==val)
            return Broj1;
        else if(Broj2->vrednost==val)
                return Broj2;
        else if(Broj3->vrednost==val)
            return Broj3;
        else if(Broj4->vrednost==val)
            return Broj4;
        else if(Broj5->vrednost==val)
            return Broj5;
        else if(Broj6->vrednost==val)
            return Broj6;
        else if(Broj7->vrednost==val)
            return Broj7;
        else if(Broj8->vrednost==val)
            return Broj8;


            return NULL;

    }

    PoljeSlagalice* getSlobodanBlok()
    {
        return Search(0);
    }

    PoljeSlagalice* nadjiPrvo()
    {
        return Search(1);    
    }

    PoljeSlagalice* nadjiDrugo()
    {
        return Search(2);
    }

    PoljeSlagalice* nadjiTrece()
    {
        return Search(3);
    }

    PoljeSlagalice* nadjiCetvrto()
    {
        return Search(4);
    }

    PoljeSlagalice* nadjiPeto()
    {
        return Search(5);
    }

    PoljeSlagalice* nadjiSesto()
    {
        return Search(6);
    }

    PoljeSlagalice* nadjiSedmo()
    {
        return Search(7);
    }

    PoljeSlagalice* nadjiOsmo()
    {
        return Search(8);
    }


    Formacija* PomeriGore(int flag=0)
    {
        Formacija *temp=this;
        
        testGORE=new Formacija(1);

        testGORE->SlobodanBlok->copy(temp->SlobodanBlok);
        testGORE->Broj1->copy(temp->Broj1);
        testGORE->Broj2->copy(temp->Broj2);
        testGORE->Broj3->copy(temp->Broj3);
        testGORE->Broj4->copy(temp->Broj4);
        testGORE->Broj5->copy(temp->Broj5);
        testGORE->Broj6->copy(temp->Broj6);
        testGORE->Broj7->copy(temp->Broj7);
        testGORE->Broj8->copy(temp->Broj8);

        
        int h= testGORE->getSlobodanBlok()->iznad->vrednost;
        PoljeSlagalice *temp2=testGORE->getSlobodanBlok();

        temp2->iznad->vrednost=0;
        temp2->vrednost=h;

    return testGORE;
    
    }

    Formacija* PomeriDole(int flag=0)
    {
    
        Formacija *temp=this;

        testDOLE=new Formacija(1);
            
        testDOLE->SlobodanBlok->copy(temp->SlobodanBlok);
        testDOLE->Broj1->copy(temp->Broj1);
        testDOLE->Broj2->copy(temp->Broj2);
        testDOLE->Broj3->copy(temp->Broj3);
        testDOLE->Broj4->copy(temp->Broj4);
        testDOLE->Broj5->copy(temp->Broj5);
        testDOLE->Broj6->copy(temp->Broj6);
        testDOLE->Broj7->copy(temp->Broj7);
        testDOLE->Broj8->copy(temp->Broj8);

        
        int h= testDOLE->getSlobodanBlok()->ispod->vrednost;
        
        PoljeSlagalice *temp2=testDOLE->getSlobodanBlok();

        temp2->ispod->vrednost=0;
        temp2->vrednost=h;

        
    return testDOLE;
        

    }

    Formacija* PomeriLevo(int flag =0)
    {
            
            Formacija *temp=this;
            testlevo=new Formacija(1);
    
        testlevo->SlobodanBlok->copy(temp->SlobodanBlok);
        testlevo->Broj1->copy(temp->Broj1);
        testlevo->Broj2->copy(temp->Broj2);
        testlevo->Broj3->copy(temp->Broj3);
        testlevo->Broj4->copy(temp->Broj4);
        testlevo->Broj5->copy(temp->Broj5);
        testlevo->Broj6->copy(temp->Broj6);
        testlevo->Broj7->copy(temp->Broj7);
        testlevo->Broj8->copy(temp->Broj8);

        
        int h= testlevo->getSlobodanBlok()->levo->vrednost;
        PoljeSlagalice *temp2=testlevo->getSlobodanBlok();

                
        temp2->levo->vrednost=0;
        temp2->vrednost=h;

        
    
        return testlevo;
        }

    
    Formacija* PomeriDesno(int flag =0)
    {
        if (flag ==0)
        {
        Formacija *temp=this;
        testdesno=new Formacija(1);

        testdesno->SlobodanBlok->copy(temp->SlobodanBlok);
        testdesno->Broj1->copy(temp->Broj1);
        testdesno->Broj2->copy(temp->Broj2);
        testdesno->Broj3->copy(temp->Broj3);
        testdesno->Broj4->copy(temp->Broj4);
        testdesno->Broj5->copy(temp->Broj5);
        testdesno->Broj6->copy(temp->Broj6);
        testdesno->Broj7->copy(temp->Broj7);
        testdesno->Broj8->copy(temp->Broj8);


        int h= testdesno->getSlobodanBlok()->desno->vrednost;
        
        PoljeSlagalice *temp2=testdesno->getSlobodanBlok();
    
        
        temp2->desno->vrednost=0;
        temp2->vrednost=h;

                
        return testdesno;
        }

        else
        {
            Formacija *temp=this;
        int h= temp->getSlobodanBlok()->desno->vrednost;
        
        PoljeSlagalice *temp2=temp->getSlobodanBlok();
    
        
        temp2->desno->vrednost=0;
        temp2->vrednost=h;

        return temp;

        }

    }

bool MogucPotezGore()
    {
        if(getSlobodanBlok()->iznad == NULL)
            return false;
        else
        {
            if(NRGORE())
                return true;
            else
                return false;
        }

    }

    bool MogucPotezDole()
    {
            if(getSlobodanBlok()->ispod == NULL)
            return false;
        else
        {
            if(NRDOLE())
                return true;
            else
                return false;
        }

    }

    bool MogucPotezDesno()
    {
        if(getSlobodanBlok()->desno == NULL)
            return false;
        else
        {
            if(NRdesno())
                return true;
            else
                return false;
        }

    }

    bool MogucPotezLevo()
    {
            if(getSlobodanBlok()->levo == NULL)
            return false;
        else
        {
            if(NRlevo())
                return true;
            else
                return false;
        }

    }
    bool NRdesno()
    {
        Formacija *hello=this;
        hello = hello->PomeriDesno();
        for (int i=0;i<brojac2;i++)
            if(Provera(X[i].ptr->getPlace(),hello->getPlace()))
                return false;

        return true;
    }

    bool NRlevo()
    {
        Formacija *hello=this;
        hello = hello->PomeriLevo();
        for (int i=0;i<brojac2;i++)
            if(Provera(X[i].ptr->getPlace(),hello->getPlace()))
                return false;

        return true;
    }

    bool NRGORE()
    {
        Formacija *hello=this;
        hello = hello->PomeriGore();
        for (int i=0;i<brojac2;i++)
            if(Provera(X[i].ptr->getPlace(),hello->getPlace()))
                return false;

        return true;
    }

    bool NRDOLE()
    {
        Formacija *hello=this;
        hello = hello->PomeriDole();
        for (int i=0;i<brojac2;i++)
            if(Provera(X[i].ptr->getPlace(),hello->getPlace()))
                return false;
    
        return true;
    }

    int *print_Init()
    {
        int *j=new int[9];
        int k;
        cout<<"Ovaj program sluzi za resavajne slagalice 3x3.\nUz pomoc AI pristupa problemu.\n";
        cout<<"Koriscen je tzv. prvi najbolji algoritam.\nUkljucena je "<<" \"prevencija ponavljanja stanja\""<<" da bi program radio brze.\nA samim tim program daje i najoptimalnije resenje!\n\n";
        cout<<"Programmed in C++\n\n";
        
        
        cout<<"Rasporedite elemente slagalice!\n";
        cout<<"Na primer, ako unesete vrednosti:\n\n1\n2\n5\n\n3\n4\n8\n\n6\n7\n0\n";
        cout<<"\nonda cete imati ovaj raspored za slagalicu:";
        cout<<"\n\n1  2  5\n3  4  8\n6  7  0\n";
        cout<<"\nNAPOMENA!\n Broj '0' je zamena za prazno polje.\n\n";
        cout<<"Pritisnite bilo koji taster da bi napravili pocetnu slagalicu...";
        cout<<endl;
        getch();
        system("cls");
        cout<<"Pocnite sa unosom...\n\n";


        
    
        for(int i(0);i<9;i++)
        {
            k=i;
        
            cout<<i+1<<"-";
            cin>>j[i];
            for(int l=0;l<i;l++)
                if(j[l]==j[i])
                {    cout<<"Nije prihvacen broj, mozda ste ga vec uneli. Unesite opet... \n";
                    i--;
                    break;
                }
            while(j[i]<0||j[i]>8)
            {
                cout<<"Nije prihvacen broj! Morate uneti broj koji je veci ili jednak 0 i manji od 10 \n";
                cout<<i+1<<"-";
                cin>>j[i];
            }


            if(--k%3==1)
                cout<<endl;
        }
        system("cls");
        cout<<"Program se izvrsava...\n\nMolim sacekajte!\n";
        cout<<endl;        
        return j;
    

    }

    int *getPlace()
    {
        Formacija *temp = this;
        int static *a;
        a=new int[9];
        a[0]=temp->SlobodanBlok->vrednost;
        a[1]=temp->Broj1->vrednost;
        a[2]=temp->Broj2->vrednost;
        a[3]=temp->Broj3->vrednost;
        a[4]=temp->Broj4->vrednost;
        a[5]=temp->Broj5->vrednost;
        a[6]=temp->Broj6->vrednost;
        a[7]=temp->Broj7->vrednost;
        a[8]=temp->Broj8->vrednost;
        return a;
    }

};

Formacija *LinkedList::Searchcc()
{
    Leaves *temp=head;
    Formacija *best;
    int x=head->next->ptr->Function;
    best=head->ptr;

    while(temp!=NULL)
    {
        if(temp->ptr->Function<x)
        {
            x=temp->ptr->Function;
            best=temp->ptr;
        }
        temp=temp->next;
    }
    X[brojac2].ptr=best;
    brojac2++;
    return best;
}


class GoalSearch
{
    Formacija *obj;
    int *a ;
    int i;
    char choice;
    

public:
    int BrojPotezaResavanja;
    
    
    GoalSearch()
    {
        choice ='y';
        
        
            
        while(choice=='y')
        {
            obj = new Formacija();
            BrojPotezaResavanja=0;
            obj->Init(obj->print_Init());
            obj->getHeuristic();
            a = obj->getPlace();
            pocni_pretragu(obj);
            trazi_opet();    
        }
        
    }

    void pocni_pretragu(Formacija *temp)
    {
        if(temp==NULL)
            return;
    if(temp->goalState())
    {
        printF(temp);
        cout<<endl;
        getch();
        return;
    }
    
        else
        {
            temp->doExpansion();                
            temp=temp->getMinHeuristic();
            pocni_pretragu(temp);
        }    
    }

    
    void printF(Formacija *t)
    {
        BrojPotezaResavanja=0;
        cout<<"RESENJE JE PRONADJENO: \n\n";
        
        recPrint(t);
                
        cout<<endl<<"Broj poteza za resavanje slagalice je:"<<BrojPotezaResavanja-2<<endl<<endl;
    }

    void recPrint(Formacija *k)
    {
        ++BrojPotezaResavanja;
        if(k==NULL)
            return;

            else
        {
            recPrint(k->Parent);
            switch(k->ZadnjiPotez)
            {
                case 1: cout<<"\n\n"<<"Prazno polje ('0') treba premestiti => GORE\n"; break;
                case 2: cout<<"\n\n"<<"Prazno polje ('0') treba premestiti => DOLE\n"; break;
                case 3: cout<<"\n\n"<<"Prazno polje ('0') treba premestiti => DESNO\n"; break;
                case 4: cout<<"\n\n"<<"Prazno polje ('0') treba premestiti => LEVO\n"; break;
                
                default: cout<<"Pocetno stanje:\n"; break;
            }
            a=k->getPlace();
            for(int j=1;j<10;j+=1)
            {
                cout<<a[j-1]<<"  ";
                if(j%3==0)
                cout<<endl;
            }
            delete []a;
        }
    }

    void trazi_opet()
    {
        cout<<"\nNova slagalica?(y/n)  ";
        cin>>choice;
        switch(choice)
        {
            case 'y':
            case 'Y': system("cls"); choice = 'y'; break;

            case 'n': 
            case 'N': choice = 'n'; break;

            default: cout<<"\nAko zelite da probate opet izaberite (y) na vasoj tastaturi, ako ne zelite onda (n) za izlaz\n"; trazi_opet(); break;

        }
        for (int i=0;i<8000;i++)
            X[i].ptr=NULL;
        brojac2=0;
        delete Linked;
        
    }
    
};

void main()
{
    GoalSearch obj;
}

Code:
/*
 * Copyright (C) 1995, 1996 Peter Bouthoorn.
 *
 * This software may be freely distributed and modified provided
 * this copyright message is left intact. The copyright message must be
 * included both with this (the original) software and with any modified
 * copies of this software or with any new software based on this software.
 * Furthermore any modified copies of this software must carry prominent
 * notices stating the software was changed and the date of any change.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. In no event
 * will the copyright holder be liable for any damage arising out of
 * the use of this software.
 *
 * As a matter of courtesy, the author requests to be informed about
 * any bugs found in this software and about improvements that may be of
 * general interest.
 *
 * Peter Bouthoorn
 * peter@obelix.icce.rug.nl
 */

#include "8puzzleAStar.h"

/*
 * The target node is saved because it must be used by totdist() to
 * compute the "difference" of a particulare node and the goal
 * node.
 */
Puzzle::Puzzle(PNode *start, PNode *target)
    :AStar(4, start, target)
{
    goal = target;
}


/*
 * This constructor is used to create the initial board configuration.
 */
PNode::PNode(const char *b, int empty_x, int empty_y)
{
    char
        *p = *board;
    int
        i;

    for (i = 0; i <= 8; i++)
        *(p + i) = *(b + i);

    x = empty_x;
    y = empty_y;
}


/*
 * This constructor initializes a new configuration using another
 * configuration (the parent configuration). First the old board is
 * copied and next the two tiles that are on old_x, old_y and
 * new_x, new_t respectively are swapped.
 */
PNode::PNode(const char *b, int old_x, int old_y, int new_x, int new_y)
{
    char
        *p = *board;
    int
        i;

    for (i = 0; i <= 8; i++)
        *(p + i) = *(b + i);

    board[old_x][old_y] = board[new_x][new_y];
    board[new_x][new_y] = 0;

    x = new_x;
    y = new_y;
}


void PNode::display() const
{
    int
        row,
        col;

    for (row = 0; row < 3; row++)
    {
        for (col = 0; col < 3; col++)
            printf("%d ", board[row][col]);
        putchar('\n');
    }
    putchar('\n');
}


/*
 * operator== determines if two nodes, i.e., two board positions are
 * the same. First, the x- and y-coordinates of the empty tile are
 * compared and next, if necessary, the two boards themselves are
 * compared.
 */
int PNode::operator==(const Node &other) const
{
    const PNode &pnother = (PNode &)other;

    if (x != pnother.x && y != pnother.y)
    return(0);
    return(compare_board(pnother.board));
}


const char (*PNode::get_board() const)[3]
{
    return(board);
}


/*
 * compare_board() compares the current board configuration with
 * another.
 */
int PNode::compare_board(const char bo[3][3]) const
{
    const char
        *p = *board,
        *b = *bo;

    int
        i;

    for (i = 0; i <= 8; i++)
        if (*(p + i) != *(b + i))
            return(0);

    return(1);
}


/*
 * do_operator() applies operator n to the current configuration:
 * the empty tile is moved in the specified direction (by calling one of
 * the do_..() functions) resulting in a new board configuration. 0 is
 * returned if the operator cannot be applied to this board configuration.
 */
Node *PNode::do_operator(int index)
{
    switch(index)
    {
        case 0:
            return(do_left());
        case 1:
            return(do_up());
        case 2:
            return(do_right());
    }
    return(do_down());
}


PNode *PNode::do_left() const
{
    if (!y)
        return(0);

    return(new PNode(*board, x, y, x, y - 1));
}


PNode *PNode::do_right() const
{
    if (y == (2))
        return(0);

    return(new PNode(*board, x, y, x, y + 1));
}


PNode *PNode::do_down() const
{
    if (x == (2))
        return(0);

    return(new PNode(*board, x, y, x + 1, y));
}


PNode *PNode::do_up() const
{
    if (!x)
        return(0);

    return(new PNode(*board, x, y, x - 1, y));
}


/*
 * compute_g() computes the cost of getting from the parent node to
 * this node. In this problem this cost is always 1.
 */
int Puzzle::compute_g(const Node *)
{
    return(1);
}


/*
 * compute_h() computes the heuristic value of the node by calling
 * totdist().
 */
int Puzzle::compute_h(const Node *node)
{
    const PNode *pnode = (PNode *)node;
    return(totdist(pnode->get_board(), goal->get_board()));
}


/*
 * totdist() computes the total or Manhatten distance of the tiles in the
 * current configuration from their 'home squares' (= the ordering
 * of the tiles in the goal configuration). The Manhatten between
 * two squares S1 and S2 is the distance between S1 and S2 in the
 * horizontal direction plus the distance between S1 and S2 in the
 * vertical direction.
 */
int Puzzle::totdist(const char now[3][3], const char target[3][3])
{
    int nrow, ncol,
        trow, tcol,
        found, tot = 0;

    for (nrow = 0; nrow < 3; nrow++)
    {
        for (ncol = 0; ncol < 3; ncol++)
        {
            found = 0;
            if (now[nrow][ncol] == 0)       // skip empty tile!
                continue;
            for (trow = 0; trow < 3 && !found; trow++)
                for (tcol = 0; tcol < 3 && !found; tcol++)
                    if (now[nrow][ncol] == target[trow][tcol])
                    {
                        tot += abs(ncol - tcol) + abs(nrow - trow);
                        found = 1;
                    }
        }
    }

    return(tot);
}


#ifdef _MSC_VER
int no_mem(size_t size)
{
    fprintf(stderr, "Out of memory\n");
    exit(1);
    return(0);
}
#else
void no_mem()
{
    fprintf(stderr, "Out of memory\n");
    exit(1);
}
#endif


int main()
{
    DEBUG = true;
    char
        start[3][3] = {
                        {2, 8, 3},
                        {1, 6, 4},
                        {7, 0, 5},
                       };

    char
        goal[3][3] = {
                        {1, 2, 3},
                        {8, 0, 4},
                        {7, 6, 5},
                    };


    /* Install new handler to catch out of memory errors. */
#ifdef _MSC_VER
    _set_new_handler(no_mem);
#else
    set_new_handler(no_mem);
#endif

    /*
     * Create Puzzle object passing it the start and goal node
     * which are also created at this point.
     */
    Puzzle
        puzzle(new PNode(*start, 2, 1), new PNode(*goal, 1, 1));

    /*
     * To demonstrate how this can be done we call get_sol()
     * and iterate over the solution path and print each element
     * we find instead of just calling display().
     */
    if (puzzle.generate())
    {
        IntrList<Node> *sol = puzzle.get_sol();
        IntrListIterator<Node> iter(*sol);

        for (PNode *p = (PNode *)iter.getfirst(); p; p = (PNode *)iter.getnext())
        p->display();

        delete sol;
    }
    return(1);
}