3. When moving the empty tile up from S to S in Figure 1, please show the Permut
ID: 3748141 • Letter: 3
Question
3. When moving the empty tile up from S to S in Figure 1, please show the Permutation Inversion relationships for tiles xi, x2, x3, and x4, before and after the empty tile movement for each of the two conditions: (1) xlx4; (Tip: check the relationship between nai and n) (0.5 pt) Please explain why the total Permutation Inversions from S to S' is "N mod invariant (0.5 pt) (including the row number of the empty tile) Explain why one can NOT solve the 15 puzzle whose initial layout is showing on the left of Figure 2, and the goal state is showing on the right of Figure 2. (0.5 pt) 123 4 12 3 4 x2 x3 x4 8 13 14 15 12 x2 x3 13 14 15 12 8 Figure 1 123 4 56 7856 7 8 9 10 1112 1314 15 9 10 1112 131514 Figure 2Explanation / Answer
Movement along the row i.e. swapping either 6 with the empty tile or x1 with the empty tile doesn't change permutation at all. So, no change in the permutation inversion counts there.
When we do column movement, we analyze the permutation inversions for two cases Let the Permutation inversion count of S be P while that of S' be P':
x1 < x2 < x3 < x4
Swapping x4 upwards, we find that we gain an inversion count of 3 from S to S' as x4 > x1 ,x2 and x3. Similarly, when tile number 3 is swapped with an empty tile, we also get an inversion count of 3. So, P' = P +3.
x1 > x2 > x3 >x4
If tile number 3 is swapped with an empty tile, we get an increase in the inversion count by 3 ,here P' = P + 3 but if x4 is swapped with the empty tile, we get a decrease in inversion count by 3 as x4 is smaller than x1,x2 and x3 . So, here P' = P - 3.
In the 15 puzzle, the parity of inversion count of Permutation of current arrangement + row number of the blank tile counting from the bottom is invariant.
In the initial configuration of S, row number of the blank tile counting from bottom is 3. So, (P+3) mod 2 should invariant after any number of moves.
We see that any column move changes the inversion count by odd number while the row number of blank tile also changes by 1 increased by 1 or decreased by 1 which is also odd.
If the Initial inversion count is P and row number of blank tile is r ,in State S', inversion count is P + (2*k+1) and row number of blank tile is r + 1 or r -1
(P' + r’) mod 2 = (P + 2*k+1 + r+1) mod 2 = (P + r + 2*k+2) mod 2 = (P+r) mod2
(P' + r') mod 2 = (P + 2*k +1 + r-1) mod 2 = (P + r + 2*k) mod 2 = (P+ r) mod 2.
Hence, the parity remains invariant after a single move.
2. In Figure 2, the permutation of start state is 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 _ . The inversion count is 0.
Parity of inversion count + row number of blank tile counting from bottom = 0 + 1 = 1 is odd.
Permutation of end state is 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 _.
The inversion count is 1. Parity of inversion count + row number of blank tile = 1 + 1 = 2 which is even.
As proved in (1), the parity of sum of inversion count and row number of blank tile remains constant after a move.
Therefore, the goal state is unreachable from the start state given in figure 2
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.