|
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?
|
