Question 1: Six-Puzzle [30] Write code in a language of your choice to solve this problem. Hand in the source code with your submission, making clear that the file(s) is/are for Question 1. Consider a variant of the eight-puzzle, which we saw in class, where we reduce the size of the puzzle to 3x2, in order to keep the number of states manageable. Now, consider the following initial and goal states: Initial state: Goal state: 142 53 15|4|3 12 a) Show the solution path (i.e., the sequence of puzzle states from the initial to the goal state) found by each of the following algorithms, assuming transitions have unit cost. You must ensure that puzzle states that have been explored are not added to the search queue. Given multiple states to explore that are otherwise equivalent in priority, the algorithm should prefer the state that involves moving a lower-numbered piece. i. Breadth first search ii. Uniform cost search iii. Depth first search iv. Iterative deepening b) Suppose now that transitions have differing costs. In particular, the cost of a transition is equal to the number of the piece that is moved (e.g., moving the 4 costs 4). If we employ the Manhattan distance heuristic for the original unit cost version of the eight-puzzle presented in class (Lecture 4, slide 11, h2), would this heuristic still be an admissible heuristic for A* search in the new variant? Justify your answer. c) Design an admissible heuristic that dominates the heuristic from part b, under the same transition cost scheme as part b. Question 1: Six-Puzzle [30] Write code in a language of your choice to solve this problem. Hand in the source code with your submission, making clear that the file(s) is/are for Question 1. Consider a variant of the eight-puzzle, which we saw in class, where we reduce the size of the puzzle to 3x2, in order to keep the number of states manageable. Now, consider the following initial and goal states: Initial state: Goal state: 142 53 15|4|3 12 a) Show the solution path (i.e., the sequence of puzzle states from the initial to the goal state) found by each of the following algorithms, assuming transitions have unit cost. You must ensure that puzzle states that have been explored are not added to the search queue. Given multiple states to explore that are otherwise equivalent in priority, the algorithm should prefer the state that involves moving a lower-numbered piece. i. Breadth first search ii. Uniform cost search iii. Depth first search iv. Iterative deepening b) Suppose now that transitions have differing costs. In particular, the cost of a transition is equal to the number of the piece that is moved (e.g., moving the 4 costs 4). If we employ the Manhattan distance heuristic for the original unit cost version of the eight-puzzle presented in class (Lecture 4, slide 11, h2), would this heuristic still be an admissible heuristic for A* search in the new variant? Justify your answer. c) Design an admissible heuristic that dominates the heuristic from part b, under the same transition cost scheme as part b
