(C++) Implement Genetic Algorithm to solve the 8-puzzle problem. Please display

Question

(C++) Implement Genetic Algorithm to solve the 8-puzzle problem. Please display output and EXPLAIN how the code performs the Genetic Algorithm heuristic!!!

2) 8 Puzzle Problem: The 8 puzzle consists of eight numbered, movable tiles set in a 3x3 frame. One cell of the frame is always empty thus making it possible to move an adjacent numbered tile into the empty cell. Such a puzzle is illustrated in following diagram. 1 2 3 8 7 6 5 4 Goal Initial The program is to change the initial configuration into the goal configuration. A solution to the problem is an appropriate sequence of moves, such as "move tiles 5 to the right, move tile 7 to the left, move tile 6 to the dow, etc"

Explanation / Answer

#include <bits/stdc++.h>

using namespace std;

#define N 3

struct node

{

node* parent;

int matrix[N][N];

int x, y;

int cost;

int level;

};

int printmatrix(int matrix[N][N])

{

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

printf("%d ", matrix[i][j]);

printf(" ");

}

}

node* newnode(int matrix[N][N], int x, int y, int newX,

int newY, int level, node* parent)

{

node* node = new node;

node->parent = parent;

memcpy(node->matrix, matrix, sizeof node->matrix);

swap(node->matrix[x][y], node->matrix[newX][newY]);

node->cost = INT_MAX;

node->level = level;

node->x = newX;

node->y = newY;

return node;

}

int row[] = { 1, 0, -1, 0 };

int col[] = { 0, -1, 0, 1 };

int calculateCost(int initial[N][N], int final[N][N])

{

int count = 0;

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++)

if (initial[i][j] && initial[i][j] != final[i][j])

count++;

return count;

}

int isSafe(int x, int y)

{

return (x >= 0 && x < N && y >= 0 && y < N);

}

void printPath(node* root)

{

if (root == NULL)

return;

printPath(root->parent);

printmatrix(root->matrix);

printf(" ");

}

struct comp

{

bool operator()(const node* lhs, const node* rhs) const

{

return (lhs->cost + lhs->level) > (rhs->cost + rhs->level);

}

};

void solve(int initial[N][N], int x, int y,

int final[N][N])

{

priority_queue<node*, std::vector<node*>, comp> pq;

node* root = newnode(initial, x, y, x, y, 0, NULL);

root->cost = calculateCost(initial, final);

pq.push(root);

while (!pq.empty())

{

node* min = pq.top();

pq.pop();

if (min->cost == 0)

{

printPath(min);

return;

}

for (int i = 0; i < 4; i++)

{

if (isSafe(min->x + row[i], min->y + col[i]))

{

node* child = newnode(min->matrix, min->x,

min->y, min->x + row[i],

min->y + col[i],

min->level + 1, min);

child->cost = calculateCost(child->matrix, final);

pq.push(child);

}

}

}

}

int main()

{

int initial[N][N] =

{

{2, 8, 3},

{1, 6, 4},

{7, 0, 5}

};

int final[N][N] =

{

{1, 2, 3},

{8, 0, 4},

{7, 6, 5}

};

int x = 1, y = 2;

solve(initial, x, y, final);

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.