This assignment is the first of two assignments on state-space search in single-agent, deterministic environments. Later we will consider multi-agent search in environments with stochastic dynamics. In this assignment we introduce a framework for the classical theory of problem solving, and we implement and compare basic ("blind") search algorithms. In Assignment 2, you will build on the code from this assignment to explore heuristic search.

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

This assignment is about basic problem formulation and basic search algorithms.

1. First, download the starter code for this assignment. Unzip it with a utility such as Windows Compressed Folders, etc.

In the given formulation files, pay particular attention to how the State class is defined and how the operators are established. We will be talking about this code in class.

python Int_Solv_Client.py TowersOfHanoi 3

(a) Run the interactive solving client and by trying different operators solve the problem of getting all the humans and robots across the river. (b) Examine the formulation code, and focus most of your attention on the can_move method, which implements the preconditions for all the operators of this formulation. (c) In this method, there are five lines of code containing "return False". Explain what is going on in the 4th one of these lines. Put your answer into your report file ("A1Report.pdf") under the heading "Step 4 (c)." To create your A1Report.pdf, you should rename the starter-code file, which has the name "A1_Report_Template.tex" to "A1Report.tex" and then edit that in Overleaf. If you are not inclined to use Overleaf, you may create a comparable file in Word or Google Docs and then convert it to pdf. You can see the "empty" PDF version of the template here.

Here are some ideas to keep in mind for this assignment. The problem format we are using not only permits the "manual solving" that you do with the Interactive Solving Client. It also permits automatic solving, such as with DFS, and BFS. Thus it is important that you follow the problem structure correctly. Certain methods are required in the State class, including __init__, __eq__, __hash__, __str__, and copy. The operators must have the correct structure, as well. The nice thing about the Interactive Solving Client is that it provides a pretty good means to test whether your formulation will be OK. You will also be reusing this formulation framework and your search code in Assignment 2.

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-code search files come 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. 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:

Farmer_Fox.py
FFCG-log.txt
BFS.py
A1Report.pdf

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

Assignment 1, in CSE 415, Autumn 2026

This file contains my (or our) problem formulation for the problem of
the Farmer, Fox, Chicken, and Grain.
'''

Your file "A1Report.pdf" will start with some specific information given in the template. Then it will contain your results for Steps 4(c) and 8, then the general sections (including AI use and your prompt log), and at the end, your partnership retrospective.

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