What to look at if compilation time expires ?

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
#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;
}
Last edited on
keskiverto (10402)
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 (25)
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 (25)
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 (6980)
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.)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
#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 );
}

Last edited on
zesan (25)
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 (6980)
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.
Last edited on
Topic archived. No new replies allowed.