Minimum number of moves to solve "game of fifteen"

Question

I read about this game and tried to make my own algorithm to solve this.

I asked it on StackOverflow for the appropriate algorithm and logic to solve this problem.

With the help of answers over there and my modifications I implemented it,

I posted my code there also and through suggestions in comments I was suggested to ask it here.

Constraints I made: An N X N matrix having one empty slot ,say 0, would be plotted having numbers 0 to n-1.

Now we have to recreate this matrix and form the matrix having numbers in increasing order from left to right beginning from the top row and have the last element 0 i.e. (N X Nth)element.

For example,

Input :

8 4 0
7 2 5
1 3 6

Output:
1 2 3
4 5 6
7 8 0

Now the problem is how to do this in minimum number of steps possible. As in game(link provided) you can either move left, right, up or bottom and shift the 0(empty slot) to corresponding position to make the final matrix.

The output to printed for this algorithm is number of steps say M and then Tile(number) moved in the direction say, 1 for swapping with upper adjacent element, 2 for lower adjacent element, 3 for left adjacent element and 4 for right adjacent element.

N could be in range [200,500]

Like, for

2     <--- order of N X N matrix
3 1
0 2

Answer should be: 3 4 1 2 where 3 is M and 4 1 2 are steps to tile movement.

So I have to minimise the complexity for this algorithm and want to find minimum number of moves. Please suggest me the most efficient approach to solve this algorithm.

It's taking too much time and I want to reduce its time complexity further and make it more efficient. Any suggestions would be appreciable.

My code:

// Program to print minimum moves from root node to destination node
// for N*N -1 puzzle algorithm.
// The solution assumes that instance of puzzle is solvable
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

//Some Global Declrations
int inDex=0,shift[100000],N,initial[500][500],final[500][500];

// state space tree nodes
struct Node
{
    // stores parent node of current node
    // helps in tracing path when answer is found
    Node* parent;

    // stores matrix
    int mat[500][500];

    // stores blank tile cordinates
    int x, y;

    // stores the number of misplaced tiles
    int cost;

    // stores the number of moves so far
    int level;
};
// Function to allocate a new node
Node* newNode(int mat[500][500], int x, int y, int newX,
              int newY, int level, Node* parent)
{
    Node* node = new Node;

    // set pointer for path to root
    node->parent = parent;

    // copy data from parent node to current node
    memcpy(node->mat, mat, sizeof node->mat);

    // move tile by 1 postion
    swap(node->mat[x][y], node->mat[newX][newY]);

    // set number of misplaced tiles
    node->cost = INT_MAX;

    // set number of moves so far
    node->level = level;

    // update new blank tile cordinates
    node->x = newX;
    node->y = newY;

    return node;
}


// bottom, left, top, right
int row[] = { 1, 0, -1, 0 };
int col[] = { 0, -1, 0, 1 };

// Function to calculate the the number of misplaced tiles
// ie. number of non-blank tiles not in their goal position
int calculateCost(int initial[500][500], int final[500][500])
{
    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;
}


// Function to check if (x, y) is a valid matrix coordinate
int isSafe(int x, int y)
{
    return (x >= 0 && x < N && y >= 0 && y < N);
}

// Comparison object to be used to order the heap
struct comp
{
    bool operator()(const Node* lhs, const Node* rhs) const
    {
        return (lhs->cost + lhs->level) > (rhs->cost + rhs->level);
    }
};

// Function to solve N*N - 1 puzzle algorithm using
// Branch and Bound. x and y are blank tile coordinates
// in initial state
void solve(int initial[500][500], int x, int y,
           int final[500][500])
{
    // Create a priority queue to store live nodes of
    // search tree;
    priority_queue<Node*, std::vector<Node*>, comp> pq;

    // create a root node and calculate its cost
    Node* root = newNode(initial, x, y, x, y, 0, NULL);
    root->cost = calculateCost(initial, final);

    // Storing the previous node
    Node* prev = newNode(initial,x,y,x,y,0,NULL);

    // Add root to list of live nodes
    pq.push(root);

    // Finds a live node with least cost,
    // add its children to list of live nodes and
    // finally deletes it from the list.
    while (!pq.empty())
    {
        // Find a live node with least estimated cost
        Node* min = pq.top();

        // Store the shifts 1,2,3,4 for top,bottom,left and right respectively.
        if(min->x > prev->x)
        {
            shift[inDex] = 4;
            inDex++;
        }
        else if(min->x < prev->x)
        {
            shift[inDex] = 3;
            inDex++;
        }
        else if(min->y > prev->y)
        {
            shift[inDex] = 2;
            inDex++;
        }
        else if(min->y < prev->y)
        {
            shift[inDex] = 1;
            inDex++;
        }
        prev = pq.top();
        // The found node is deleted from the list of
        // live nodes
        pq.pop();
        if (min->cost == 0)
        {
            // Print the number of moves
            cout << min->level << endl;
            return;
        }
        // do for each child of min
        // max 4 children for a node
        for (int i = 0; i < 4; i++)
        {
            if (isSafe(min->x + row[i], min->y + col[i]))
            {
                // create a child node and calculate
                // its cost
                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);

                // Add child to list of live nodes
                pq.push(child);
            }
        }
    }
}
int main(void)
{
    cin >> N;
    // Initial configuration
    int i,j,k=1;
    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
        {
            cin >> initial[j][i];
        }
    }
    // Putting numbers from 1 in increasing order.
    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
        {
            final[j][i] = k;
            k++;
        }
    }

    // Value 0 is used for empty space
    final[N-1][N-1] = 0;
    int x = 0, y = 1,a[100][100];
    solve(initial, x, y, final);

    // Printing the steps taken while moving tiles.
    for(i=0;i<inDex;i++)
    {
        cout << shift[i] << endl;
    }
    return 0;
}

Input:

2
3 1
0 2

Output: 3 1 4 2

Answer 1

#include <stdio.h>
#include <string.h>

Don't use the C compatibility headers; prefer the C++ headers <cstdio> and <cstring>, which define their identifiers in the std namespace.

using namespace std;

Really don't do that! That causes all (present or future) standard identifiers to be declared in the global namespace, potentially altering the meaning of your code.

int inDex=0,shift[100000],N,initial[500][500],final[500][500];

One line per declaration, please. And globals such as N really need more meaningful names - single-character names are only good at innermost scope. Why are we using so many globals anyway?

 Node* node = new Node;

Where's the matching delete for this? We should be using a smart pointer (probably std::unique_ptr since it's owned either by the heap or by a function).

void solve(int initial[500][500], int x, int y,
           int final[500][500])

Warning - some of these locals hide global variables of the same name. That makes the code especially hard to read and to reason about.

It looks to me that we push all possible positions onto the heap, including positions we've previously encountered. Notably, we're considering reversing the move just made, which is clearly not productive.

int main(void)

In C++, we write than int main(). Unlike C, an empty argument list means "no arguments" and we don't need to use the void keyword.

    cin >> N;

Don't use N until we've checked that the stream operation was successful. That applies to the other >> in main(), too.

for(i=0;i<inDex;i++)
{
    cout << shift[i] << endl;

Don't flush at the end of every line of output. We shouldn't need to flush at all in this program.