Problem sa slagalicom?

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Pozdrav svima

Evo koda koji uspesno resava slagalicu 3x3 koju korisnik unese, e, ali je njegovo tzv. goal (finalno) stanje ovakvo:

0 1 2
3 4 5
6 7 8

a meni treba ovakvo:

1 2 3
8 0 4
7 6 5

0 - je pokretni blok

#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; }


Pokusao sam da promenim onaj deo za formaciju, ali nista, nisam uspeo da promenim "finalno" stanje slagalice koje treba program da slaze

Moze li neko pomoci?