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.
