What to look at if compilation time expires ?

[zesan]

My code works but in the end no solving result appears, is there any error in the code ?

#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <time.h>

using namespace std;

#define N 4


class Node
{

public:

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++)


std::cout<<mat[i][j]<< std::endl;

std::cout<<"\n"<<endl;


}
}


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);


std::cout<<"\n"<<endl;

}

// Comparison object to be used to order the heap
class comp

{
public:
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()
{

std::srand(std::time(NULL)); 

int initial[N][N] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 0}
};


std::random_shuffle(&initial[0][0], &initial[2][4]);

for (int row = 0; row < 4; ++row) {
for (int col = 0; col < 4; ++col) {
std::cout << initial[row][col] << ' ';
}
std::cout << std::endl;
}

int final[N][N] =
{
{1, 2, 3,4},
{5, 6, 7,8},
{9, 10,11, 12},
{13, 14,15, 0}
};

int x = 1, y = 2;

solve(initial, x, y, final);

return 0;
}

[keskiverto]

My code works but in the end no result appears

Ah, not getting a result means same as "works"?

Lack of indentation makes code harder to read.


Why do you mix std::cout and printf? Use only one I/O-system, not both.

[zesan]

Thanks a lot for your reply, I am sorry for saying it's working actually after shuffling it gets compilation timed out, I overlooked the mix up of std::cout and printf together, now is everything alright in the source code ? Please have a look again, this is the project's source code so I need to be sure that there is no error in the source code.

[zesan]

Can anyone please tell me there is no error in the source code, I am sorry to ask again because running out of time due to project submission.

[lastchance]

Here is your code for the 15-puzzle
https://en.wikipedia.org/wiki/15_puzzle
with some indentation and corrections: enough for me to read it anyway.

Please could you explain your algorithm in routine solve(). At the moment it is spawning so many child nodes (each with an entire matrix in) that eventually it runs out of memory.

Are you looking at something like Iterative Deepening A*?
https://en.wikipedia.org/wiki/Iterative_deepening_A*
I'm really not qualified to advise you on this, but I can see that at present you are adding nodes irrespective of whether that matrix state is already in the currently-accessible path. (Nodes contain other information besides the matrix state, so multiple versions of effectively the same thing may end up in the queue.)

Maybe somebody with a better knowledge of algorithms can have a look at this.


(Code runs but will run out of memory before completion.)

#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <ctime>
using namespace std;

#define N 4

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

class Node
{
public:
   Node* parent;
   int mat[N][N];
   int x, y;
   int cost;
   int level;
};

//======================================================================

void printMatrix( int mat[N][N] )                          // <==== CORRECTION: add "void"
{
   for ( int i = 0; i < N; i++ )
   {
      for ( int j = 0; j < N; j++ ) cout << mat[i][j] << '\t';
      cout << '\n';
   }
   cout << '\n';
}

//======================================================================

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 calculateCost( int initial[N][N], int final[N][N] )    // "cost" is number of differences from final
{
   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 )                                 // a possible point
{
   return ( x >= 0 && x < N && y >= 0 && y < N );
}

//======================================================================

void printPath( Node* root )
{
   if (root == nullptr ) return;

   printPath( root->parent );
   printMatrix( root->mat );
   cout << "\n\n";
}

//======================================================================

// Comparison object to be used to order the heap
class comp
{
public:
   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*, vector<Node*>, comp> pq;

   Node* root = newNode( initial, x, y, x, y, 0, nullptr );
   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 );

            cout << "Added a child with cost " << child->cost << '\n';    // just a debugging line
//          printMatrix( child->mat );   char c;   cin >> c;              // just a debugging line
         }
      }
   }
}

//======================================================================

int main()
{
   srand( time( nullptr ) );
   int initial[N][N];
   int final[N][N]   = { {  1,   2,  3,  4 },
                         {  5,   6,  7,  8 },
                         {  9,  10, 11, 12 },
                         { 13,  14, 15, 0  } };

   for ( int i = 0; i < N; i++ )
   {
      for (int j = 0; j < N; j++ ) initial[i][j] = final[i][j];
   }
   random_shuffle( &initial[0][0], &initial[0][0] + N * N );         // <==== CORRECTION
  
   cout << "Initial matrix:\n";
   printMatrix( initial );

   int x = 1, y = 2;                                                
   solve( initial, x, y, final );
}

[zesan]

Thanks a lot for putting enough time.

Your questions :

Please could you explain your algorithm in routine solve(). ?

I am trying to figure out the memory leakage for routine solve().

Are you looking at something like Iterative Deepening A* ?

I am trying to use Branch and Bound algorithm.

If I had 40 GB RAM it may work ?

[lastchance]

The problem is that for each node you pop off the queue you are creating four new nodes (slightly less at the boundaries) and putting them in the queue. You may also be putting exactly the same matrix state in several nodes (with different x,y or level). You would need a monumental amount of memory (and time) to make this work. If you are using branch and bound then I can see a lot of "branch", but not a lot of "bound". I can get it to work (partly) for a few hand shuffles, but not when the initial state is far from the final one.

In some way, you need to change your algorithm so that you delete child nodes if they are never going to be on the optimal path. Ideally, the same matrix state shouldn't be in multiple nodes, either.

Depending on the parity of the initial permutation, I think that half of the initial states do not give rise to possible solutions.

I'm sorry, @zesan, but I at present I can only see the problems, not the solution.