Algorithm – How to get the minimum number of movements to solve the “fifteen year game”?

September 27, 2021By Simo Game

I am reading about this and considering forming an algorithm to find the minimum number of moves to solve this problem.

The constraint I made: has an empty slot An N×N matrix of (e.g. 0) will be drawn with numbers 0 to n-1.

Now we have to recreate this matrix and increment the numbers from left to right starting from the top row, and The last element is 0, which is (NX Nth) elements.

For example,

Input :

8 4 0 
7 2 5
1 3 6

Output:
1 2 3
4 5 6
7 8 0

< p>Now the question is how to do this in as few steps as possible.
In the game (link provided), you can move left, right, up or down, and move 0 (empty slot) to The corresponding position is used to make the final matrix.

The output of this algorithm is the number of steps M, and then the Tile (number) moves in the direction, 1 means swapping with the upper adjacent element, 2 means lower adjacent element, 3 Represents the left adjacent element, 4 represents the right adjacent element.

2 <--- order of NXN matrix
3 1 
0 2

The answer should be: 3 4 1 2 where 3 is M and 4 1 2 is the step of tiling.

So, I must minimize this The complexity of the algorithm, and hope to find the smallest number of moves. Please suggest me the most effective way to solve this algorithm.

Edit:

What I coded in c, please refer to Algorithm instead of pointing out other problems in the code.

#include 
using namespace std;
int inDex=0 ,shift[100000],N,initial[500][500],final[500][500];
struct Node
{
 Node* parent;
 int mat[ 500][500];
 int x, y;
 int cost;
 int level;
};

 Node* newNode(int mat[500][500], 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[500][500], int final[500][500])
{
 int count = 0;
 for (int i = 0; i  for (int j = 0; j  if (initial[i][ j] && initial[i][j] != final[i][j])
 count++;
 return count;

}

 int isSafe(int x, int y)
{
 return (x >= 0 && x = 0 && y }
struct comp 
{
 bool operator()(const Node* lhs, const Node* rhs) const
 {
 return (lhs->cost + lhs->level)> (rhs->cost + rhs->level);
 }
};

void solve(int initial[500][500], int x, int y,
 int final[500][500])
{
 priority_queue, comp> pq;
 Node* root = newNode(initial, x, y, x, y, 0, NULL);
 Node* prev = newNode(initial ,x,y,x,y,0,NULL);
 root->cost = calculateCost(initial, final);
 pq.push(root);
 while (!pq. empty())
 {
 Node* min = pq.top();
 if(min->x> prev->x)
 {
 shift[ inDex] = 4;
 inDex++;
 }
 else if(min->x x)
 {
 shift[inDex] = 3;< br /> inDex++;
 }
 else if(min->y> prev->y)
 {
 shift[inDex] = 2;
 inDex++;< br /> }
 else if(min->y y)
 {
 shift[inDex] = 1;
 inDex++;
 }
 prev = pq.top();
 pq.pop();
 if (min->cost == 0)
 {
 cout << min->level << endl;
 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()
{
 cin >> N;
 int i,j,k=1;
 for(i=0;i {
 for(j=0;j {
 cin >> initial[j] [i];
 }
 }
 f or(i=0;i {
 for(j=0;j {
 final[j][i] = k;
 k++;
 }
 }
 final[N-1][N-1] = 0;
 int x = 0, y = 1,a [100][100];
 solve(initial, x, y, final);
 for(i=0;i {
 cout << shift[i] << endl;
 }
 return 0;
}

In the code above, I am checking each child node with the smallest cost (from How many numbers were placed incorrectly in the final matrix number).

I want to make this algorithm more efficient and reduce its time complexity. Any suggestions will be obvious.

< div class="content-split">

Although this sounds like a homework problem, I will provide some help.

For small problems, such as your 2×2 or 3×3, you can brute force. Basically, you can make all possible combinations for each possible movement, track the number of laps for each shot, and then print out the smallest .

To improve this, please maintain a list of resolved solutions, and then make possible moves at any time, if you have completed the move, please stop trying, because it cannot be the smallest.

For example, suppose I’m in this state (flatten the matrix into a string for easy display):

5736291084
6753291084
 5736291084

Please note that we have returned to the state we have seen before. This means that it cannot be the smallest movement, because the smallest movement will not return to the previous state.

You need to create a tree that does this, so you have something like:

134
 529
 870
 / \
 / \
 / \
 / \
 134 134
 529 520
 807 879
 / | \ / | \
 / | X / X \
 134 134 134 134 134 130
 509 529 529 502 529 524
 827 087 870 879 870 879

Wait. Note that I marked some with X because they are duplicates, so we don’t want to continue pursuing them because we know they are not the smallest.

You just keep repeating this until you try all Possible solutions (i.e. all unstopped leaves arrive at the solution), and then you only see which is the shortest. You can also do this in parallel to stop after anyone finds a solution, saving you time.

This brute force method is not effective for large matrices. To solve these problems, you need to consider some serious software engineering. One method you can take is to decompose it into smaller matrices and use this Way to solve it, but this may not be the best path.

This is a tricky problem to be solved under a larger value, and there are some tricky NP problems.

From the solution At the beginning of the solution, determine the rank of the arrangement

The above reverse is how to generate a list of all possible values in advance.

Start from the solution. Its rank is 0 (e.g., zero movement ):

012
345
678

Then, make all possible actions from there. Arrangement of all these moves grade It is 1, as it is to be solved by a move.

012
0 345
 678
 / \
 / \< br /> / \
 102 312
1 345 045 
 678 678

Repeat the above steps. Each new level has the same permutation level. Generate all possible Move (in this case, until all branches are deleted as duplicates).

Then you can store all of these into objects. Flattening the matrix makes this easy (using only JavaScript Syntax):

{
 '012345678': 0,
 '102345678': 1,
 '312045678': 1,
 '142305678': 2,
 // and so on
}

Then, to solve your problem “minimum number of moves”, just find the same as your starting point The entry. The rank is the answer.

If you are in a scenario where the entire solution can be pre-generated, this will be a good solution. The generation will take some time, but the lookup will be fast (This is similar to the “rainbow table” of cracking the hash).

If you have to solve it dynamically (without pre-generation), then the first solution, starting from the answer, move gradually in your way, Until you find the solution will be better.

Although the maximum complexity is O(n! ), but there are only O(n^2) possible solutions. Cut down the copy on the tree when you go, your complexity will be somewhere between these two, maybe O(n^3)~ Near O(2^n)

I am reading about this and considering forming an algorithm to find the minimum number of moves to solve this problem.

Constraint I made: An N×N matrix with an empty slot (such as 0) will be drawn with numbers 0 to n-1.

Now we have to recreate this matrix and start from the top The line starts with increasing numbers from left to right, and the last element is 0, which is (NX Nth) elements.

For example,

Input: 

8 4 0
7 2 5
1 3 6

Output:
1 2 3
4 5 6< br />7 8 0

Now the question is how to do this in as few steps as possible.
In the game (link provided), you can go left, right, up or down Move, and move 0 (empty slot) to the corresponding position to make the final matrix.

The output of this algorithm is the number of steps M, and then the Tile (number) moves in the direction, 1 means adjacent to the upper part Element exchange, 2 represents the lower adjacent element, 3 represents the left adjacent element, and 4 represents the right adjacent element.

2 <-- -order of NXN matrix
3 1
0 2

The answer should be: 3 4 1 2 where 3 is M and 4 1 2 is the step of tiling.

Therefore, I must minimize the complexity of this algorithm and hope to find the smallest number of moves. Please suggest me the most effective way to solve this algorithm.

Edit:

What I have coded in c, please refer to the algorithm instead of pointing out other issues in the code.

#include 
using namespace std;
int inDex=0,shift[100000],N,initial[500][500],final[500][500];
struct Node
{
 Node* parent;
 int mat[500][500];
 int x, y;
 int cost;
 int level;
};

Node* newNode(int mat[500][500], 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[500 ][500], int final[500][500])
{
 int count = 0;
 for (int i = 0; i  for (int j = 0; j  if (initial[i][j] && initial[i][j] != final[i][j])
 count++;< br /> return count;

}

int isSafe(int x, int y)
{
 return (x >= 0 && x < N && y >= 0 && y }
struct comp
{
 bool operator()(const Node* lhs, const Node* rhs) const
 {
 return (lhs->cost + lhs->level)> (rhs->cost + rhs->level); 
 }
};

void solve(int initial[500][500], int x, int y,
 int final[500][500]) 
{
 priority_queue, comp> pq;
 Node* root = newNode(initial, x, y, x, y, 0, NULL );
 Node* prev = newNode(initial,x,y,x,y,0,NULL);
 root->cost = calculateCost(initial, final);
 pq.push (root);
 while (!pq.empty())
 {
 Node* min = pq.top();
 if(min->x> prev-> x)
 {
 shift[inDex] = 4;
 inDex++;
 }
 else if(min->x x)
 {
 shift[inDex] = 3;
 inDex++;
 }
 else if(min->y> prev->y)
 {
 shift [inDex] = 2;
 inDex++;
 }
 else if(min ->y y)
 {
 shift[inDex] = 1;
 inDex++;
 }
 prev = pq.top();
 pq.pop();
 if (min->cost == 0)
 {
 cout << min->level << endl;
 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);< br /> pq.push(child);
 }
 }
 }
}
int main()
{
 cin >> N;
 int i,j,k=1;
 for(i=0;i {
 for(j=0;j {
 cin >> initia l[j][i];
 }
 }
 for(i=0;i {
 for(j=0;j  {
 final[j][i] = k;
 k++;
 }
 }
 final[N-1] [N-1] = 0;
 int x = 0, y = 1,a[100][100];
 solve(initial, x, y, final);
 for( i=0;i {
 cout << shift[i] << endl;
 }
 return 0;
}

In the above code, I am checking each child node with the smallest cost (how many numbers are incorrectly placed from the final matrix number).

I want to make this algorithm more efficient and Reduce its time complexity. Any suggestions will be obvious.

Although this sounds like a homework problem, I will provide some help.

For very small problems, such as your 2×2 or 3×3, you can brute force. Basically, you can make all possible combinations for every possible movement, tracking every time Take the number of laps and print out the smallest one.

To improve this, please maintain a list of resolved solutions, and then make possible moves at any time, if you have completed the move, please stop trying, Because it can’t be the smallest.

For example, suppose I’m in this state (flatten the matrix into a string for display):

 5736291084
6753291084
5736291084

Please note that we have returned to the state we have seen before. This means that it cannot be the smallest movement, because the smallest movement will not return to The previous state.

You need to create a tree that does this, so you have something like:

134
 529
 870 / \
 / \
 / \
 / \
 134 134
 529 520
 807 879
 / | \ / | \
 / | X / X \
 134 134 134 134 134 130
 509 529 529 502 529 524
 827 087 870 879 870 879

etc. .Note that I marked some with X because they are duplicates, so we don’t want to continue pursuing them because we know they are not the smallest.

You just keep repeating this until you try all possible Solution (i.e. all unstopped leaves arrive at the solution), and then you only see which is the shortest. You can also do this in parallel to stop after anyone finds the solution, thus saving you time.

This brute force method is not effective for large matrices. To solve these problems, you need to consider some serious software engineering. One method you can take is to decompose it into smaller matrices and solve this way , But this may not be the best path.

This is a tricky problem to be solved at a larger value, and there are some tricky NP problems.

Start with the solution , Determine the rank of the arrangement

The above reverse is how to generate a list of all possible values in advance.

Start from the solution. Its rank is 0 (for example, zero movement):

012
345
678

Then, make all possible actions from there. The rank of all these moves is 1, as a mobile solution.

012
0 345
678
/ \
/ \
/ \
102 312
1 345 045
678 678

Repeat the above steps. Each new level has the same permutation level. Generate all possible moves (in this case, until all branches are deleted as duplicates).

Then you can store all of this in an object. Flattening the matrix will make this easy (using only JavaScript syntax):

{
'012345678': 0,
'102345678': 1,
'312045678': 1,
'142305678': 2,
// and so on
}

Then, to solve your problem “minimum number of moves”, just find the entry that is the same as your starting point. The level of arrangement is the answer.

In the scenario of generating the entire solution, this will be a good solution. The generation will take some time, but the lookup will be very fast (this is similar to the “rainbow table” of cracking the hash).

If you must solve it dynamically (without pre-generation), then the first solution, starting from the answer, move gradually in your way, until you find that the solution will be better.

Although the maximum complexity is O(n! ), but there are only O(n^2) possible solutions. Cut down the copy on the tree when you go, your complexity will be somewhere between these two, maybe O(n^3)~ Near O(2 ^ n)

Leave a Comment Cancel reply