Please help with this artificial intelligence problem. Thank you. When moving th
ID: 3744716 • Letter: P
Question
Please help with this artificial intelligence problem. Thank you.
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 n, and n (0.5 pt) Please explain why the total Permutation Inversions from S to S' is "N mod 2" 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) 12 3 4 12 3 4 5 6 x4 x1 x2 X3 13 14 15 12 5 6 131415 12 Figure 1Explanation / Answer
Permutation inversion count for a perumation (a1 ,a2,a3, ...an) is defined as the number of pairs (ai,aj) where i < j but ai > aj
1. 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 inersion count there. When we do column movement,we analyze the permutation inversions for two cases (Let the Permuation inversion count of S be P while that of S' be P':
i). 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.
ii) 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 Permuation 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 colmun move chnages 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
So, (P' + r' ) mod 2 = (P + 2*k+1 + r+1) mod 2 = (P + r + 2*k+2) mod 2 = (P+r) mod 2
or (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 perumation 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 . Hence, the goal state is unreachable from the start state given in figure 2