This assignment continues our study of state-space search in single-agent, deterministic environments, building on Assignment 1. There, we introduced a framework for the classical theory of problem solving (problem formulation files with a State class and operators, and an interactive solving client), and we implemented blind search algorithms (DFS and BFS). In this assignment we use the same problem-formulation framework and search-program structure to examine heuristic search.

After doing the coding and executions described below, you'll make entries in a report document A2Report.pdf that you'll submit along with your code.

1. First, download the starter code for this assignment. Unzip it with a utility such as Windows Compressed Folders, etc. The starter code uses the same problem-formulation format and search framework as the A1 code; you may find it helpful to refer back to your own A1 formulation and BFS code.

The starter code includes a new problem formulation for you to use with UCS; it's the French Cities network in which the problem is to find a shortest route from the initial-state city to the goal-state city. These are, by default, RENNES and AVIGNON. (These could easily be changed by editing the formulation file's line defining STARTING_CITY, etc.) This formulation is in the file FranceWithCosts.py.
The State class in this formulation file has a method edge_distance(s2), which is used to get the edge cost from the current state to s2. You'll be setting up the UCS.py program to use these cost values to determine the cost of the lowest-cost path from the starting state to any newly reached state.
When the UCS algorithm reaches a goal state, it produces a backtrace of "backlinks" (sometimes called predecessor links) to represent the actual lowest-cost path from the start state to the goal state found. The file UCS.py includes a method runUCS.

For the default initial state and goal state, the results are

['Rennes', 'Nantes', 'Limoges', 'Lyon', 'Avignon']

1041.0

Page 184 in the reading shows the state space for this problem, with the distances on the graph edges. When you run the code you should get a solution path of 4 edges (5 cities) and total distance 1041: ['Rennes', 'Nantes', 'Limoges', 'Lyon', 'Avignon']. It might be formatted differently in the printout. The map is also shown below:

Map showing French cities (which serve as the states of this problem) and distance values on roads (represented as graph edges) between them.

Implement an A* search program, putting your code into the starting template file AStar.py. You may wish to cut and paste from the UCS.py file, since most of the implementation will be identical.

Develop your A* program to work with the heuristic function defined in the file FranceWithDXHeuristic.py. Your program will be operated as follows:

python AStar.py FranceWithDXHeuristic

Here are some hints about how to modify UCS.py to implement A*. Change the names of the file and the algorithm in the code and the comments. After the code that imports the Problem, assign self.h = Problem.h, so that you can call the heuristic function easily in your algorithm. Within the search algorithm, any time UCS uses gs or new_g as a priority value, you should compute f (or call it fs or new_f, depending on the context), and use the f value as the priority.

When checking the CLOSED list, don't necessarily delete the new state if the same city is already on CLOSED, but look at the priority, and if the new state has a lower priority value, delete the state on CLOSED and put the new one on OPEN.

Make sure that the first five CAPITALIZED variables in class AStar get assigned the values they need (as described in the corresponding comments), so that you can receive credit on autograder tests. These include self.COUNT through self.TOTAL_COST. The solution path should be set as the value of self.PATH, and it must be a list of strings, such as ['Rennes', 'Nantes', 'Limoges', 'Lyon', 'Avignon']. Also, be sure to assign proper values in the dictionary for self.g.

Try to solve some instances of the Eight Puzzle using UCS.py. There is a default instance you should try first. You can do it with the command line:

python UCS.py EightPuzzle

python UCS.py EightPuzzle '[[3, 1, 2], [4, 5, 0], [6, 7, 8]]'

python UCS.py puzzle_rotate_2

Example puzzles to try:

# Puzzle A. (should be very fast)
python UCS.py EightPuzzle '[[3,0,1],[6,4,2],[7,8,5]]'

# Puzzle B. (should not take long)
python UCS.py EightPuzzle '[[3,1,2],[6,8,7],[5,4,0]]'

# Puzzle C. (May take a few minutes)
python UCS.py EightPuzzle '[[4,5,0],[1,2,8],[3,7,6]]'

# Puzzle D. (May take several seconds or even minutes)
python UCS.py EightPuzzle '[[0,8,2],[1,7,4],[3,6,5]]'

# Test with Puzzle A:
python AStar.py EightPuzzleWithHamming '[[3,0,1],[6,4,2],[7,8,5]]'

Your report will have a section called "Heuristics for the Eight Puzzle". Compare the performance of these heuristics on each of the example puzzles (given above). For each puzzle-heuristic pair, report (a) whether the puzzle was successfully solved, (b) length of the solution path found, in number of edges, (c) total cost of the path found, (d) number of states expanded, and (e) MAX_OPEN_LENGTH. Put this information into the table given in the report template, described below.

The table in the template has one row for each puzzle-heuristic pair (e.g., Puzzle A with Hamming), with "none (UCS)" as the heuristic for the Uniform-Cost Search runs. The first two columns identify the puzzle and the heuristic, and the remaining five columns hold items (a) through (e) above, in that order: Solved?, # Soln Edges, Soln Cost, # Expanded, and Max Open. (The initial state of each puzzle, as a flattened list such as [3,0,1,6,4,2,7,8,5], is listed just below the table.) If it takes more than 5 minutes to solve a particular puzzle with a particular heuristic, you may abort that run; write "aborted" in its Solved? column and leave the rest of that row blank.

Here are some ideas to keep in mind for this assignment. As in A1, the problem format we are using permits both "manual solving" with the Interactive Solving Client and automatic solving, such as with UCS and A*. Thus it is important that any formulation files you write (such as your heuristic files) follow the problem structure correctly. Certain methods are required in the State class, including __init__, __eq__, __hash__, __str__, and copy.

Even if you are familiar with Python, there may be some constructs in the formulation files that you are not familiar with. You can read up on list comprehensions (p.31 of the first reading) and lambda expressions (pp. 47-52 of that reading).

Parts of your code will be graded by an autograder. To do this, your files will be imported as modules by the autograder. Your search should not automatically start running when the module is imported. The starter template file AStar.py comes with some code at the end of the file that takes care of this. This code is: "if __name__ == '__main__' " which avoids running the search automatically if it is being imported, but still runs it automatically if it is the main program. The autograder will be comparing the solutions and statistics found by your code with expected solutions, by calling functions in your code and examining the values of certain variables in your code. These variables are generally already in place for you in the starter code UCS.py. So you should not rename variables like self.PATH or any of the other variables written with all CAPITAL letters.

Each of your Python files should begin with a multiline string (more details are shown below.)

Follow reasonable commenting practice in your code. The comments in the starter code can serve as examples of the commenting style that we consider appropriate.

Turn in the following files to Gradescope:

AStar.py
EightPuzzleWithHamming.py
EightPuzzleWithManhattan.py
A2Report.pdf

Each of the Python files should start with a multiline comment in the following format with your own information rather than the sample information given here.

'''AStar.py
by John Nathan Smith and Emily Doe
UWNetIDs: jnsmith25, emilydoe24
Student numbers: 2576543, 2483119

Assignment 2, in CSE 415, Autumn 2026

This file contains my (or our) implementation of A* search.
'''

Your file "A2Report.pdf" will start with some specific information given in the template. Then it will contain your results mentioned above (heuristics comparison and, optionally, extra credit), then your partnership retrospective, the general report sections, and at the end, your AI prompts.

The turn-in method is via file uploads to Gradescope. Be sure to upload your files to the A2 assignment.