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! :slight_smile:

#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