#1 Download computer science & engineering books free           #2 Display your sponsored posts here. Reach 10,000+ students. Contact: info[at]cpentalk.com for quote           #3 Take the Ultimate Trivia Quiz. See where you rank globally.
+2 votes
in Artificial Intelligence by

1 Answer

+2 votes
by
selected by (user.guest)
 
Best answer

Define the order of counting from the upper left corner to the lower right corner.

Start state is

image

Let N denote the number of lower numbers following a number, called “inversions”. Then, goal state is

image

The goal state has the numbers in a certain order where counting starts at the upper left corner and proceeds from left to right. When reached to the end of a row then move to the left most square in the next row. For any other configuration besides the goal, whenever a tile with a greater number on it precedes a tile with a smaller number, the two tiles are said to be inverted.

Proposition:

For a given puzzle configuration, let N denote the sum of the total number of inversions and the row number of the empty square.

Then (N mod 2) is invariant under any legal move. Means, after a legal move an odd N remains odd whereas an even N remains even.

Proof:

Sliding a tile horizontally changes neither the total number of inversions nor the row number of an empty square. Therefore let us consider sliding a tile vertically.

Assume that the tile 1 is located directly over the empty square. Sliding it down changes the parity of row number of an empty square. Now consider the total number of inversions. The move only affects relative positions of tiles 1, 2, 3, and 4. If none of the 2, 3, 4 caused an inversion relative to 1 then after sliding one gets three of additional inversions.

If one of the three is smaller than 1, then before the move greater than 2, 3, and 4 contributes a single inversion. After the move they’ll be contributing two inversions - a change of 1, also an odd number. Two additional cases obviously lead to the same result. Thus the change in the sum N is always even. This is precisely what we have set out to show.

So before we solve a puzzle, we should compute the N value of the start and goal state and make sure they have the same parity, otherwise no solution is possible.

Related questions

Welcome to CPEN Talk
Solution-oriented students of computer engineering on one platform to get you that

ONE SOLUTION

Chuck Norris protocol design method has no status, requests or responses, only commands.
...