 # Can someone explain this 8 puzzle code for me?

You must select a tag to post in this category. Please find the tag relating to the section of the course you are on

When you ask a question, don’t forget to include a link to the exercise or project you’re dealing with!

If you want to have the best chances of getting a useful answer quickly, make sure you follow our guidelines about how to ask a good question. That way you’ll be helping everyone – helping people to answer your question and helping others who are stuck to find the question and answer! ``````#include <iostream>
#include <queue>

using namespace std;

#define N 3

struct Node

{

Node* parent;

int mat[N][N];

int x, y;

int cost;

int level;

};

int printMatrix(int mat[N][N])

{

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

{

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

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

printf("\n");

}
return 0;
}

Node* newNode(int mat[N][N], int x, int y, int newX,

int newY, int level, Node* parent)

{

Node* node = new Node;

node->parent = parent;

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

swap(node->mat[x][y], node->mat[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->mat);

printf("\n");

}

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->mat, min->x,

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

min->y + col[i],

min->level + 1, min);

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

pq.push(child);

}

}

}

}

int main()

{

int initial[N][N] =

{

{1, 2, 3},

{5, 6, 0},

{7, 8, 4}

};

int final[N][N] =

{

{1, 2, 3},

{5, 8, 6},

{0, 7, 4}

};

int x = 1, y = 2;

solve(initial, x, y, final);

return 0;

}
``````

Hi!

There’s 2 main questions, have you covered stuff like `struct` and `class` yet? And the other one, have you covered data structures? If you have some knowledge with both of those you can get a feel for what’s going on here.

I recommend this channel for basic intro to data structures, but there are many others: Learn STL: Introduction of Templates - YouTube

1 Like