puzzle-8-Astar

/* puzzle 8 by hanhan */
/* belum beres :D */
#include <iostream>
#include <cstdlib>
//#include "random_state.h"

using std::cout;
using std::endl;

#define atas -3
#define bawah 3
#define kanan 1
#define kiri -1

//int pAwal[9] = {7,2,4,5,0,6,1,8,3};
//int pAwal[9] = {4,2,1,3,5,6,0,7,8};
//int pAwal[9] = {2,8,3,1,6,4,7,0,5};     //bisa
//int pAwal[9] = {2,8,1,4,6,3,0,7,5};
//int pAwal[9] = {1,2,3,8,0,4,6,5,7};               //gagal

//int pAwal[9] = {1,3,4,8,6,2,7,0,5};           //berhasil
//int pAwal[9] = {1,3,4,8,0,2,7,6,5};           //berhasil
int pAwal[9] = {1,2,3,8,0,4,6,5,7};               //gagal

int pAkhir[9] = {1,2,3,8,0,4,7,6,5};

clock_t start, finish;
double waktu;

struct PuzzleNode {
    int node[9];
    int g;
    int h;
    int f;
    int langkah;
    PuzzleNode *parent;
    int plangkah;   //langkah parent
    PuzzleNode *next;
};

PuzzleNode neighbors[4];
PuzzleNode *first = NULL;                   //first list open
PuzzleNode *last = NULL;                    //last list open
PuzzleNode *akhir = NULL;                   //awal list closed
PuzzleNode *awal = NULL;                    //akhir list closed

void cp(int a[], int b[])   //salin posisi
{
    for(int i=0;i<9;i++)
    {
        a[i]=b[i];
    }
}

int abs(int x)  //fungsi absolut (kenapa ga bisa pakai yang sudah jadi ya?
{
    if(x<0) return (x*-1);
    return x;
}

int compare(int pState[], int pGoal[])  //bandingkan dua posisi
{
    int sama =0;
    for(int i=0;i<9;i++)
    {
        if(pState[i]!=pGoal[i])
        {
            sama=0;
            break;
        }
        else
            sama=1;
    }
    return sama;
}

int manhattanHeuristic(int pState[]) //pakai manhattan distance
{
    int distance=0;
    int row, col,r,c;
    for(r=0;r<9;r++)
    {
        for(c=0;c<9;c++)
        {
            if(pState[r]!=0)
            {
                if(pState[r]==pAkhir[c])
                {
                    row = r%3;
                    col = r/3;
                    distance += abs(row-(c%3)) + abs(col-(c/3));
                }
            }
        }
    }
    return distance;
}

void cetakPuzzle(int pState[])  //cetak puzzle
{
    for(int i=0;i<9;i++)
    {
        if(i%3==0)
            cout<<endl;
        cout<<pState[i]<<" ";
    }
    cout<<endl;
}

int cariNol(int pState[])       //cari posisi Nol
{
    int posisi;
    for(int i=0;i<9;i++)
    {
        if(pState[i]==0)
            posisi = i;
    }
    return posisi;
}

void gerak(int pState[], int arah, int p[])
{
    int pNol,temp2;
    //int p[9];
    cp(p,pState);                        //salin state[] ke temp
    pNol=cariNol(p);                     //cari posisi nol ada di mana
    //gerak berdasarkan posisi nol
    temp2= p[pNol];                      //tukar-tukar
    p[pNol] = p[pNol+arah];
    p[pNol+arah] = temp2;
}

void cekNeighbors(PuzzleNode *pState)
{
    int posNol = cariNol(pState->node);
    switch(posNol)
    {
    case 0:
        gerak(pState->node,kanan,neighbors[0].node);
        gerak(pState->node,bawah,neighbors[1].node);
        neighbors[0].langkah = kanan;
        neighbors[1].langkah = bawah;
        break;
    case 1:
        gerak(pState->node,kiri,neighbors[0].node);
        gerak(pState->node,kanan,neighbors[1].node);
        gerak(pState->node,bawah,neighbors[2].node);
        neighbors[0].langkah = kiri;
        neighbors[1].langkah = kanan;
        neighbors[2].langkah = bawah;
        break;
    case 2:
        gerak(pState->node,kiri,neighbors[0].node);
        gerak(pState->node,bawah,neighbors[1].node);
        neighbors[0].langkah = kiri;
        neighbors[1].langkah = bawah;
        break;
    case 3:
        gerak(pState->node,atas,neighbors[0].node);
        gerak(pState->node,kanan,neighbors[1].node);
        gerak(pState->node,bawah,neighbors[2].node);
        neighbors[0].langkah = atas;
        neighbors[1].langkah = kanan;
        neighbors[2].langkah = bawah;
        break;
    case 4:
        gerak(pState->node,kiri,neighbors[0].node);
        gerak(pState->node,atas,neighbors[1].node);
        gerak(pState->node,kanan,neighbors[2].node);
        gerak(pState->node,bawah,neighbors[3].node);
        neighbors[0].langkah = kiri;
        neighbors[1].langkah = atas;
        neighbors[2].langkah = kanan;
        neighbors[3].langkah = bawah;
        break;
    case 5:
        gerak(pState->node,kiri,neighbors[0].node);
        gerak(pState->node,atas,neighbors[1].node);
        gerak(pState->node,bawah,neighbors[2].node);
        neighbors[0].langkah = kiri;
        neighbors[1].langkah = atas;
        neighbors[2].langkah = bawah;
        break;
    case 6:
        gerak(pState->node,atas,neighbors[0].node);
        gerak(pState->node,kanan,neighbors[1].node);
        neighbors[0].langkah = atas;
        neighbors[1].langkah = kanan;
        break;
    case 7:
        gerak(pState->node,kiri,neighbors[0].node);
        gerak(pState->node,atas,neighbors[1].node);
        gerak(pState->node,kanan,neighbors[2].node);
        neighbors[0].langkah = kiri;
        neighbors[1].langkah = atas;
        neighbors[2].langkah = kanan;
        break;
    case 8:
        gerak(pState->node,kiri,neighbors[0].node);
        gerak(pState->node,atas,neighbors[1].node);
        neighbors[0].langkah = kiri;
        neighbors[1].langkah = atas;
        break;
    }
}

//samentawis
void cetakOpen()
{
    cout<<"=======Isi open==========="<<endl;
    PuzzleNode *current = first;
    while(current)
    {
        cetakPuzzle(current->node);
        cout<<"F: "<<current->f<<"| G: "<<current->g<<" | H: "<<current->h<<endl;
        current = current->next;
    }
    cout<<"=======sampai sini==========="<<endl;
}

void cetakClose()
{
    cout<<"=======Isi close==========="<<endl;
    PuzzleNode *current = awal;
    while(current->next)
    {
        cetakPuzzle(current->node);
        cout<<"F: "<<current->f<<"| G: "<<current->g<<" | H: "<<current->h<<endl;
        current = current->next;
    }
    cout<<"=======sampai sini==========="<<endl;
}

void bestNode(PuzzleNode *temp)
{
    PuzzleNode *lOpen = first;
    //PuzzleNode *temp = new PuzzleNode;
    int min = lOpen->f;
    cp(temp->node,lOpen->node);
    temp->f = lOpen->f;
    temp->g = lOpen->g;
    temp->h = lOpen->h;
    temp->langkah = lOpen->langkah;
    //cp(temp->parent,lOpen->parent);
    temp->parent=lOpen->parent;
    //bandingkan f terkecil
    while(lOpen)
    {
       // cout<<"nilai Min= "<<min<<endl;
        if(lOpen->f<min)
        {
            min = lOpen->f;
            temp->f = lOpen->f;
            cp(temp->node,lOpen->node);
            temp->f = lOpen->f;
            temp->g = lOpen->g;
            temp->h = lOpen->h;
            temp->langkah = lOpen->langkah;
            //cp(temp->parent,lOpen->parent);
            //temp->parent=lOpen->parent;
        }
        lOpen= lOpen->next;
    }
    //
    //cout<<"node terbaik dengan F: "<<temp->f<<endl;
   // cetakPuzzle(temp->node);
}

void inputList(PuzzleNode *pState)
{
    //cout<<"input list open"<<endl;
    PuzzleNode *lOpen = new PuzzleNode;
    cp(lOpen->node,pState->node);
    lOpen->f = pState->f;
    lOpen->g = pState->g;
    lOpen->h = pState->h;
    lOpen->langkah = pState->langkah;
    lOpen->plangkah = pState->plangkah;
    //cp(lOpen->parent,pState->parent);
    lOpen->parent=pState->parent;

    if(!first)
    {
        first = lOpen;
        last = lOpen;
    } else
    {
        last->next = lOpen;
        last = lOpen;
    }

}

void delNode(PuzzleNode *pState)
{
    PuzzleNode *current = first;
    while(current)
    {
        if(compare(current->node,pState->node)==1)
        {
            if(current==first)
            {
               //if(current->next){
                    first = current->next;
               //}
                delete current;
            }else if(current==last)
            {
                PuzzleNode *pos;
                pos = first;
                while(pos->next != last)
                        pos = pos->next;
                pos->next = NULL;
                last = pos;
                delete current;
            }
            else {
                PuzzleNode *pos;
                pos = first;
                while(pos->next != current)
                        pos = pos->next;
                pos->next = current->next;
                delete current;
            }

            break;

        }

        current=current->next;
    }


}

void inputClose(PuzzleNode *pState)
{
   // cout<<"input close akan dimasukkan F: "<<pState->f<<" G: "<<pState->g<<" H: "<<pState->h<<endl;
    PuzzleNode *temp = new PuzzleNode;
    cp(temp->node,pState->node);
    temp->f = pState->f;
    temp->g = pState->g;
    temp->h = pState->h;
    temp->langkah = pState->langkah;
    temp->plangkah = pState->plangkah;
    //cp(temp->parent,pState->parent);
    temp->parent=pState->parent;
    if(!awal)
    {
        awal = temp;
        akhir = temp;
    } else
    {
        akhir->next = temp;
        akhir = temp;
    }
}

int cekInClosed(int pState[])
{
    int sama =0;
    PuzzleNode *lClosed = awal;
    while(lClosed)
    {
        if(compare(lClosed->node,pState)==1)
        {
            sama =1;
            break;
        }
        lClosed = lClosed->next;
    }
    return sama;
}

void rekonstruksi(PuzzleNode *pNode)
{
    //belum beresss
    cout<<"langkah:"<<endl;
    //int s= compare(pNode->node,pAwal);
    cout<<pNode->langkah<<endl;
    while(compare(pNode->node,pAwal)!=1)
    {
        cout<<pNode->langkah<<endl;
        pNode= pNode->parent;
    }
    //   while(pNode->langkah==0)
    //   {
    //     cout<<pNode->langkah<<endl;
    //     pNode->langkah = pNode->plangkah;
     //  }
}

void AStar()
{
    start = clock();
    PuzzleNode *pState = new PuzzleNode;
    PuzzleNode *x = new PuzzleNode;
    PuzzleNode *y = new PuzzleNode;
    int g=0;
    //int j=0;
    bool lanjut=true;
    cp(pState->node,pAwal);
    pState->h = manhattanHeuristic(pState->node);
    pState->f = pState->h;
    pState->g = 0;
    pState->langkah = 0;
    //cp(pState->parent,pAwal);
    pState->parent = NULL;
    //1. masukkan state awal ke openList
    inputList(pState);
    //car node terbaik
    //selama ada isinya di open
    PuzzleNode *open = first;
    while(lanjut){

        //cout<<"iterasi: "<<g<<endl;
        g++;

        //cetakOpen();
        bestNode(x);
        //delete di open
        delNode(x);
        //masukkan x ke close;
        //cetakPuzzle(x->node);
        inputClose(x);
        if(compare(x->node,pAkhir)==1)
        {
            cout<<"\n\nHoreee...ketemu"<<endl;
            cout<<"Posisi awal"<<endl;
            cetakPuzzle(pAwal);
            cout<<"\nPosisi Akhir"<<endl;
            cetakPuzzle(x->node);
            cout<<"Waktu iterasi: "<<g<<endl;
            //rekonstruksi(x);
            break;
        }

        cekNeighbors(x);
        for(int i=0;i<4;i++)
        {
            if((neighbors[i].langkah!=0) )
            {
                //cek apakah ada di closed
                if(cekInClosed(neighbors[i].node)!=1)
                {
                    //cp(y->parent,x->node);
                    y->parent=x;
                    y->plangkah = x->langkah;
                    y->langkah = neighbors[i].langkah;
                    //cout<<"nilai plangkah: "<<x->langkah<<endl;
                    y->g = x->g + 1 ;
                    y->h = manhattanHeuristic(neighbors[i].node);
                    y->f = y->g + y->h;
                    cp(y->node,neighbors[i].node);
                    //masukkan ke openlist
                    inputList(y);
                }
            }
        }
        //cetakClose();
        if(open)
            lanjut = true;
        else
            break;
    }
    finish = clock();
    waktu = (double(finish)-double(start))/CLOCKS_PER_SEC;
    cout<<"waktu : "<<waktu<<" detik"<<endl;

}

void menu()
{
    int pilih;
    cout<<"\n\t1. {1,3,4,8,6,2,7,0,5}"<<endl;
    cout<<"\t2. {2,8,1,0,4,3,7,6,5}"<<endl;      //katanya hard
    cout<<"\t3. {2,8,1,4,6,3,0,7,5}"<<endl;
    cout<<"\t4. {5,6,7,4,0,8,3,2,1}"<<endl;
    //cout<<"\t5. Random"<<endl;
    cout<<"\n\tPilih State Awal: ";
    //std::cin>>pilih;
    pilih =5;
    int p[9];
    int xrand=0;
    switch(pilih)
    {
    case 1:
        p= {1,3,4,8,6,2,7,0,5};
        cp(pAwal,p);
        AStar();
        break;
    case 2:
        p= {2,8,1,0,4,3,7,6,5};
        cp(pAwal,p);
        AStar();
        break;
    case 3:
        p= {2,8,1,4,6,3,0,7,5};
        cp(pAwal,p);
        AStar();
        break;
    case 4:
        p= {5,6,7,4,0,8,3,2,1};
        cp(pAwal,p);
        AStar();
        break;

    default:
        p= {2,8,3,1,6,4,7,0,5};
        cp(pAwal,p);
        AStar();
        break;
    }
}

int main()
{
    menu();
    return 0;
}