Başlangıç > Kodlar > C++ ile 8 puzzle çözümü

C++ ile 8 puzzle çözümü

 

https://tdsoftware.files.wordpress.com/2012/11/8puzzle.jpg

8obj.h:

#include <iostream>

const int LEFT=1;
const int RIGHT=2;
const int UP=3;
const int DOWN=4;
const int EMPTY=5;

using namespace std;

class POINT
{
private:
friend class BOARD;
int x,y;
POINT():x(0),y(0){}
POINT(int a, int b):x(a),y(b){}
POINT&operator=(const POINT&rhs)
{
x=rhs.x;
y=rhs.y;
return *this;
}
friend bool operator==(const POINT&p1,const POINT&p2)
{
return (p1.x==p2.x && p1.y==p2.y);
}
};

class BOARD
{
private:
friend class puzzle;
int board[3][3];
int lastAction;
int step;
BOARD *previous;
POINT blank;
BOARD(const int arr[][3]):lastAction(EMPTY),step(0),previous(NULL)
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
board[i][j]=arr[i][j];
refresh();
}
BOARD(BOARD&src){*this=src;}
BOARD(BOARD *src,int action)
{
*this=*src;
lastAction=action;
step++;
previous=src;
moveBlank(lastAction);
}
BOARD&operator=(const BOARD&rhs)
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
board[i][j]=rhs.board[i][j];
lastAction=rhs.lastAction;
step=rhs.step;
previous=rhs.previous;
blank=rhs.blank;
return *this;
}
friend bool operator==(const BOARD&b1,const BOARD&b2)
{
if(!(b1.blank==b2.blank))
return false;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++){
if(b1.board[i][j]!=b2.board[i][j])
return false;
}
return true;
}
void refresh()
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++){
if(board[i][j]==0)
{
blank.x=i;
blank.y=j;
return;
}
}
}
bool checkMove(int action)
{
switch(action)
{
case LEFT:
return (blank.y>0);break;
case RIGHT:
return (blank.y<2);break;
case UP:
return (blank.x>0);break;
case DOWN:
return (blank.x<2);break;
}
}
void moveBlank(int action)
{
switch(action)
{
case LEFT:
board[blank.x][blank.y]=board[blank.x][blank.y-1];
board[blank.x][blank.y-1]=0;
blank.y–;
break;
case RIGHT:
board[blank.x][blank.y]=board[blank.x][blank.y+1];
board[blank.x][blank.y+1]=0;
blank.y++;
break;
case UP:
board[blank.x][blank.y]=board[blank.x-1][blank.y];
board[blank.x-1][blank.y]=0;
blank.x–;
break;
case DOWN:
board[blank.x][blank.y]=board[blank.x+1][blank.y];
board[blank.x+1][blank.y]=0;
blank.x++;
break;
}
}
void printBoard()
{
for(int i=0;i<3;i++){
for(int j=0;j<3;j++)
cout<<board[i][j]<<” “;
cout<<endl;
}
}
void printActionList()
{
BOARD *temp=previous;
int i=step;
int actionList[30];
actionList[i]=lastAction;
while(temp)
{
i–;
actionList[i]=temp->lastAction;
temp=temp->previous;
}
cout<<endl;
for(int i=0;i<=step;i++)
printAction(actionList[i]);
cout<<endl;
}
static void printAction(int action)
{
switch(action)
{
case LEFT:
cout<<“LEFT”<<endl;break;
case RIGHT:
cout<<“RIGHT”<<endl;break;
case UP:
cout<<“UP”<<endl;break;
case DOWN:
cout<<“DOWN”<<endl;break;
}
}
static int* createActionList(int index)
{
int *temp=new int[index];
for(int i=0;i<index;i++)
temp[i]=0;
return temp;
}
};

class puzzle
{
private:
static long LIMIT;
bool status;
int curIndex;
BOARD STATE,GOAL;
BOARD **p;
public:
~puzzle()
{
for(int i=0;i<LIMIT;i++)
delete p[i];
delete[] p;
}
puzzle(const int arr1[][3],const int arr2[][3]):status(false),curIndex(1),STATE(arr1),GOAL(arr2)
{
p=new BOARD*[LIMIT];
p[0]=new BOARD(STATE);
}
void Solve()
{
for(int i=0;curIndex<LIMIT;i++)
{
if(p[i]->checkMove(LEFT) && p[i]->lastAction!=RIGHT)
{
p[curIndex]=new BOARD(p[i],LEFT);
if(*p[curIndex]==GOAL)
{
status=true;
break;
}
curIndex++;
}
if(p[i]->checkMove(RIGHT) && p[i]->lastAction!=LEFT)
{
p[curIndex]=new BOARD(p[i],RIGHT);
if(*p[curIndex]==GOAL)
{
status=true;
break;
}
curIndex++;
}
if(p[i]->checkMove(UP) && p[i]->lastAction!=DOWN)
{
p[curIndex]=new BOARD(p[i],UP);
if(*p[curIndex]==GOAL)
{
status=true;
break;
}
curIndex++;
}
if(p[i]->checkMove(DOWN) && p[i]->lastAction!=UP)
{
p[curIndex]=new BOARD(p[i],DOWN);
if(*p[curIndex]==GOAL)
{
status=true;
break;
}
curIndex++;
}
}
if(status){
if(*p[curIndex]==GOAL)
{
STATE.printBoard();
p[curIndex]->printActionList();
p[curIndex]->printBoard();
cout<<endl<<“Solution found in “<<p[curIndex]->step<<” step”;
if(p[curIndex]->step>1)
cout<<“s”;
cout<<endl;
}
}
else
cout<<“There is no solution”<<endl;
}
};

void getTable(int table[][3])
{
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
cin>>table[i][j];
}
}

code.cpp:

#include <iostream>
#include “8obj.h”

using namespace std;

long puzzle::LIMIT=1000000;

int main()
{
puzzle *puz;
int table[3][3],table2[3][3];
char option;
do
{
cout<<“Enter first table:”<<endl;
getTable(table);
cout<<“Enter second table:”<<endl;
getTable(table2);
cout<<endl;
puz=new puzzle(table,table2);
puz->Solve();
delete puz;
cout<<“Do you want to continue(e/h):”;
cin>>option;
}
while(option==’e’);
return 0;
}

Reklamlar
Kategoriler:Kodlar Etiketler:, , , , , , ,
  1. osman
    12/03/2013, 12:11

    satırların yanlarına açıklama yazılsın

    Beğen

  2. 02/07/2014, 23:33

    biraz daha ayrıntı verirseniz daha iyi olur hocam ama gerçekten çok teşekkürker paylaşım için.

    Beğen

  3. 24/07/2014, 00:32

    çok teşekkürler gerçekten çok faydalı oldu

    Beğen

  1. No trackbacks yet.

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Connecting to %s

%d blogcu bunu beğendi: