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) xlx2>x3>x4; (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 1