Description
Introduction For this assignment, you will be implementing a solver for the Hua Rong Dao sliding puzzle game. Hua Rong Dao is a sliding puzzle that is popular in China. Check out the following page for some background story on the puzzle and an English description of the rules. http://chinesepuzzles.org/huarong-pass-sliding-block-puzzle/ (Links to an external site.) The puzzle board is four spaces wide and five spaces tall. We will consider the variants of this puzzle with ten pieces. There are four kinds of pieces: • One 2×2 piece. • Five 1×2 pieces. Each 1×2 piece is either placed horizontally or vertically. • Four 1×1 pieces. Once we place the ten pieces on the board, two empty spaces should remain. Look at the most classic initial configuration of this puzzle below. (Don’t worry about the Chinese characters. They are not crucial for understanding the puzzle.) In this configuration, one 1×2 piece is horizontal, and the other four 1×2 pieces are vertical. The goal is to move the pieces until the 2×2 piece is above the bottom opening (i.e. helping Cao Cao escape through the Hua Rong Dao/Pass). You may move each piece horizontally or vertically only, into an available space. You are not allowed to rotate any piece or move it diagonally. There are many other initial configurations for this puzzle. Check out this Chinese Wikipedia page (Links to an external site.) for 32 initial configurations. The link below each configuration opens another page where you can play the puzzle and see the solution. Counting Moves: We will count moves differently from how the website does it. On the website, consecutive moves of a single piece count as one move. However, we will count the consecutive moves separately. Suppose that I move a single piece by two spaces to the right. We will count it as two moves, whereas the website counts it as one move. For the most classic initial configuration, the optimal solution takes 81 moves on the website, whereas it takes 116 moves based on our counting rule. Your Tasks Two Search Algorithms: A* and DFS You will implement two search algorithms: A* search and Depth-first search. Two Heuristic Functions for A* Search If we want A* search to find an optimal solution, we need to provide it with an admissible heuristic function. You will implement two admissible heuristic functions for A* search. You will first implement the Manhattan distance heuristic, the simplest admissible heuristic function for this problem. Suppose that we relax the problem such that the pieces can overlap. Given this relaxation, we can solve the puzzle by moving the 2×2 piece over the other pieces towards the goal. The cost of this solution would be the Manhattan distance between the 2×2 piece and the bottom opening. For example, for the most classic initial configuration, the heuristic value is 3. Next, propose another advanced heuristic function that is admissible but dominates the Manhattan distance heuristic. Implement this heuristic function. Explain why this heuristic function is admissible and dominates the Manhattan distance heuristic. Mark Breakdown The tasks for this assignment consist of implementing the depth-first search and A* search for the Hua Rong Dao puzzle, where the A* search requires the implementation of a Manhattan heuristic and an original heuristic of your own. The mark breakdown for this is as follows: • Depth-first search solution: 35% • A* solution (Manhattan heuristic): 55% • Original heuristic (implementation & description): 10% What to Submit: You should submit two files: • hrd.py contains your Python program, and • advanced.pdf contains a description of your advanced heuristic function. This file should be no more than one page long. Please describe the advanced heuristic function and explain why it is admissible and why it dominates the Manhattan distance heuristic. Your program must use python3 and run on the teach.cs server (where we run our autotesting script). We will test your program using a random subset of the 32 initial configurations on the Chinese Wikipedia page (Links to an external site.). For each initial configuration, we will run the following command: python3 hrd.py <A* output file> The command specifies one plain text input file and the two plain text output files containing the solutions found by DFS and A* for the puzzle. For example, if we run the following command for puzzle 5, specified in a file called puzzle5.txt: python3 hrd.py puzzle5.txt puzzle5sol_dfs.txt puzzle5sol_astar.txt The DFS solution will be found in puzzle5sol_dfs.txt and the A* solution will be found in puzzle5sol_astar.txt After submitting your code, we will run a script to verify that your DFS solution is valid and your A* solution is valid and optimal. We are providing a validation script that you can use to verify that your code compiles and will work with our autotesting script. Note that this does not test the correctness of your solution. It is only meant to prevent compilation errors with our autotester. Input Format The input to your program is a plain text file that stores an initial Hua Rong Dao puzzle configuration. See below for an example of the input file content. It contains 20 digits arranged in 5 rows and 4 digits per row, representing the initial configuration of the puzzle. The single pieces are denoted by 7. The 2×2 piece is denoted by 1. The 5 1×2 pieces are denoted by different numbers, but the numbers are assigned at random. 2113 2113 4665 4775 7007 Output Format The two output files should store the DFS and A* solution for the input file provided. See below for an example of the content of the output file. On the first line, print the cost of the solution. Next, print the sequence of states from the initial configuration to a goal state. Two consecutive states are separated by an empty line. Note that we are using 2 to denote horizontal 1×2 pieces, 3 to denote vertical 1×2 pieces, and 4 to denote the single pieces. Due to limited space, we only show the beginning of the output file below. Make sure that your output files match this format exactly. Cost of the solution: 116 3113 3113 3223 3443 4004 3113 3113 3223 3443 0404 3113 3113 3223 3443 0440 Suggested Steps for Tackling This Assignment: We are not providing any starter code for this assignment. If you feel overwhelmed or have trouble getting started, this section offers suggestions on tackling this assignment incrementally. First, sit down and think about formulating this puzzle as a search problem. Note that the pieces have different sizes. Think carefully about how to represent each state, so it is easy to translate your representation into code. Here are some suggested steps to implement A* Search: 1. Implement a data structure to store a state. 2. Implement a function to read in an initial configuration of the puzzle from an input file and store it as a state. 3. The solution to each puzzle is a sequence of states. Think about how to store the sequence in memory. Hint: we recommend keeping the minimal information possible so that you can recover the sequence at the end. 4. Implement a priority queue to store the frontier. 5. Implement a function which tests whether a state is a goal state. 6. Implement a function which takes a state and returns a list of its successor states. 7. Implement a function that takes a solution (i.e. a sequence of states) and returns the cost of the solution. 8. Implement a function which takes a state and returns the heuristic estimate for the state (i.e. the cost of the optimal path from the state to a goal state based on your heuristic function). That is, this function returns the h value of the state. 9. Implement a function that performs A* search given an initial state and returns a solution. This solution should be the optimal solution if your heuristic is admissible. Here are some suggested steps to implement Depth-First Search: 1. You should be able to re-use most of the implementation for A* search. 2. Implement a LIFO stack to store the frontier. 3. Implement a function that performs DFS given an initial state and returns a solution.
