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) xlx2>x3>x4, (Tip: check the relationship between nz and ) (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) 123 4 123 4 56 x4 xl x2 x3 x4 8 13 14 1512 8 13 14 1512 Figure 1 25 678 9 10 11 12 910 11 12 13 14 15 1315 14