The S puzzle consists of three purple tiles, eight red tiles, and four blue tiles, arranged in a 4x4 square with one space empty. The puzzle has the following legal moves with associated costs: A purple tile can jump over one or two tiles at a cost equal to the number of tiles jumped over. A red tile can jump over another tile at a cost of 1. Any tile can move into an adjacent empty location with a cost of 1. The goal is to have all of the purple tiles in the leftmost column. The position of the blank tile is not important. Suppose that initially the puzzle is in configuration Co, in which the leftmost two columns are filled with red tiles, column three is filled with blue tiles, and the first three rows of the rightmost column are filled with purple tiles; the empty space is in the fourth row of column four. Consider the following heuristic h functions: hi(puzzle) = the number of purple tiles that have a red or blue tile to the left of them (but in the same row). In this case, the evaluation of Co is 3. h2(puzzle) = the sum of the distance from each purple tile to the leftmost column. In this case, the evaluation of Cois 9. hz (puzzle) = twice the number of purple tiles in the rightmost column. In this case, the evaluation of Co is 6. . hu(puzzle) = the sum of the number of purple tiles that have a red or blue tile somewhere to the left of them in the same row), the number of blue tiles that have a purple tile somewhere to the right of them (in the same row), and the number of red tiles that have a purple tile somewhere to the right of them in the same row). In this case, the evaluation of Co is 15. h; (puzzle) = the sum of the number of blue tiles to the left (in the same row) of each purple tile. (a) For each h function, determine whether the heuristic is admissible. If the heuristic is admissible, informally prove that it is. If it is not admissible, give a counterexample showing that it is not. (b) For each pair of h functions that are admissible, determine if one dominates the other and if so, informally prove that it dominates, and if it does not dominate, give a counterexample showing that it does not. The S puzzle consists of three purple tiles, eight red tiles, and four blue tiles, arranged in a 4x4 square with one space empty. The puzzle has the following legal moves with associated costs: A purple tile can jump over one or two tiles at a cost equal to the number of tiles jumped over. A red tile can jump over another tile at a cost of 1. Any tile can move into an adjacent empty location with a cost of 1. The goal is to have all of the purple tiles in the leftmost column. The position of the blank tile is not important. Suppose that initially the puzzle is in configuration Co, in which the leftmost two columns are filled with red tiles, column three is filled with blue tiles, and the first three rows of the rightmost column are filled with purple tiles; the empty space is in the fourth row of column four. Consider the following heuristic h functions: hi(puzzle) = the number of purple tiles that have a red or blue tile to the left of them (but in the same row). In this case, the evaluation of Co is 3. h2(puzzle) = the sum of the distance from each purple tile to the leftmost column. In this case, the evaluation of Cois 9. hz (puzzle) = twice the number of purple tiles in the rightmost column. In this case, the evaluation of Co is 6. . hu(puzzle) = the sum of the number of purple tiles that have a red or blue tile somewhere to the left of them in the same row), the number of blue tiles that have a purple tile somewhere to the right of them (in the same row), and the number of red tiles that have a purple tile somewhere to the right of them in the same row). In this case, the evaluation of Co is 15. h; (puzzle) = the sum of the number of blue tiles to the left (in the same row) of each purple tile. (a) For each h function, determine whether the heuristic is admissible. If the heuristic is admissible, informally prove that it is. If it is not admissible, give a counterexample showing that it is not. (b) For each pair of h functions that are admissible, determine if one dominates the other and if so, informally prove that it dominates, and if it does not dominate, give a counterexample showing that it does not