Assignment 3: Automated Puzzle Solving

You may complete this assignment individually or with a partner who can be from any section

of the course. You can search for teammates on Piazza using the following post.

Learning goals

By the end of this assignment, you should be able to:

• read complex code you didn’t write and understand its design and implementation,

including:

– reading the class and method docstrings carefully (including attributes, representation invariants, preconditions, etc.)

– understanding relationships between classes, by applying your knowledge of composition and inheritance

• complete a partial implementation of a class, including:

– reading the representation invariants to enforce important facts about implementation decisions

– reading the preconditions to factor in assumptions that they permit

– writing the required methods according to their docstrings

– use inheritance to define a subclass of an abstract parent class

• implementing algorithms by translating their steps into python code by:

– choosing an appropriate ADT to solve the problem

– deciding if recursion is appropriate

• implement recursive methods for trees when provided with their specifications.

• perform unit testing on a program to verify correctness

And more specifically:

• implement depth and breadth first searches to solve logic puzzles

• implement a simple expression tree class

• be able to implement additional logic puzzles beyond those in this assignment

• explore the behaviour of depth and breadth first solvers on various logic puzzles

1

Coding Guidelines

These guidelines are designed to help you write well-designed code that will adhere to the

interfaces we have defined.

You must:

• write each method in such a way that the docstrings you have been given in the starter

code accurately describe the body of the method.

• avoid writing duplicate code.

You must NOT:

• change the parameters, parameter type annotations, or return types in any of the

methods or functions you have been given in the starter code.

• add or remove any parameters in any of the methods you have been given in the starter

code.

• change the type annotations of any public or private attributes you have been given in

the starter code.

• create any new public attributes.

• create any new public methods or functions.

• write a method or function that mutates an object if the docstring doesn’t say that it

will be mutated.

• add any more import statements to your code, except for imports from the typing

module and the modules you’re implementing in this assignment.

You may find it helpful to:

• create new private helper methods or functions for the classes you have been given.

– if you create new private methods or functions you must provide type annotations

for every parameter and return value. You must also write a full docstring for

each method as described in the function design recipe

• create new private attributes for the classes you have been given.

– if you create new private attributes you must give them a type annotation and

include a description of them in the class’s docstring as described in the class

design recipe

• import more types from the typing module

All code that you write should follow the function and class design recipes.

While writing your code, you can assume that all arguments passed to the methods and functions you have been given in the starter code will respect the preconditions and type annotations outlined in the provided docstrings.

Introduction: Problem Domain

Puzzle solving is a typically human activity that, in recent decades, has been explored in the

context of computers. There are many potential benefits to this. For example, we can offload

2

some puzzle-solving tasks to computers, we may better understand human puzzle-solving by

programming computer puzzle solvers, or we might generate novel puzzles using a computer

program.

This assignment investigates a class of puzzles that have the following features in common:

feature description

full information all information about the puzzle state at any given point

is visible to the solver; there are no hidden or random

aspects

well-defined extensions a definition of legal extensions from a given puzzle state

to new states is given

well-defined solution a definition of what it means for the puzzle to be in a

solved state is given

These features are common to a very large class of puzzles: crosswords, sudoku, peg solitaire,

verbal arithmetic, and so on. This assignment generalizes the required features into an

abstract superclass Puzzle and solving such puzzles is written in terms of this abstract class.

Once this is done, particular concrete puzzles can be modelled as subclasses of Puzzle and

solved using the solve method of a subclass of the Solver abstract class, which will be

described later.

Although there may be faster puzzle-specific solvers for a particular puzzle by knowing specific

features of that puzzle, the general solvers are designed to work for all puzzles of this sort.

Starter Code

Download the starter code a3.zip. Unzip the file and place its contents in PyCharm in your

a3 folder (remember to set a3 folder as a source roor).

Any files that start with a3_ are files that you will need to modify and submit. Once you are

done Tasks 1-5, you will be able to run the files play_sudoku.py. play_expression_tree.py,

play_word_ladder.py and experiment.py. You are provided with a basic set of starter

tests, starter_tests_a3.py, to run locally, and a moderate set of tests on MarkUs. You

are expected to write your own test cases to thoroughly test your code, as we have additional

hidden tests you will be evaluated on.

Task 4 of the assignment requires you to install two python packages in order for your code

to run (you don’t need to write any code using them, but the code we have provided makes

use of them): networkx and pygame-gui.

Please follow the instructions at the bottom of the (Software Guide’s Installing Python

libraries section)[https://q.utoronto.ca/courses/219921/pages/software-guide] to install these

two packages. Ask on Piazza or visit office hours if you need help with this.

3

The Puzzles

We will start by introducing how the puzzles will be represented and what specific puzzles

we will consider in this assignment.

abstract Puzzle class

The abstract class Puzzle has the following methods:

method description

is_solved (abstract) returns True iff the puzzle is in a solved state

extensions (abstract) returns a list of extensions from the current puzzle state

to new states that are a single ‘move’ away

fail_fast (has a default

implementation in Puzzle)

returns True if it is clear that the puzzle can never,

through a sequence of extensions, move into a solved

state

And that’s it! Note: each subclass will need its own __init__ method in order to represent

that particular puzzle’s state information.

Sudoku

This puzzle commonly appears in print media and online. You are presented with an n × n

grid with some symbols, for example digits or letters, filled in. The symbols must be from a

set of n symbols. The goal is to fill in the remaining symbols in such a way that each row,

column, and √

n ×

√

n subsquare, contains each symbol exactly once. In order for all of that

to make sense, n must be a square integer such as 4, 9, 16, or 25.

You may want to read more about sudoku to get a feel for the puzzle if you aren’t already

familiar with it.

Word Ladder

This puzzle involves transforming one word into a target word by changing one letter at a

time. Each word must belong to a specified set of valid words. Here’s an example, where we

assume that the set of words is a rather large set of common English words.

Here is one potential sequence of words, where the goal is to get from the word ‘cost’ to the

word ‘save’:

cost → cast → case → cave → save

4

Expression Tree Puzzle

This puzzle consists of an algebraic equation containing one or more variables. The puzzle is

solved when the variables are assigned values that satisfy the equation.

5

The Solvers

Now that we know a bit about the puzzles that we will be implementing, we will turn our

attention to how we will implement the solvers.

Solving a puzzle can be done by systematically searching for a solution, starting from its

current state. To make this daunting task even possible, we have to be sure that we have

a systematic way of exploring all possible puzzle states – without needlessly re-visiting the

same state twice.

You will implement two standard systematic searching techniques.

The implicit tree underlying our search

To understand our searching techniques, it helps to think of the tree that is defined by all the

possible states of a puzzle: each node is one puzzle state, the root is the initial state of the

puzzle, and the children of a node are its extensions (puzzle states that are one move away).

When we actually implement the algorithms, we don’t need to explicitly form this tree, but

it is useful to remember that it is there. The A3: Search Algorithms Visual Guide examples

for the Word Ladder do a good job helping us visualize this tree.)

The search algorithms

With depth-first search, we search deeply before we search broadly. We exhaustively search

the first subtree before considering any other subtree. And we use the same strategy when

we search that subtree: exhaustively searching its first subtree before considering any other

subtree. And so on – think recursively!

With breadth-first search, we search broadly before we search deeply. We consider all

puzzle states at depth 1, then all puzzle states at depth 2, and so on until we have searched

all puzzle states in our tree. (You will find a queue is helpful for keeping track of puzzles

states to be checked when their turn comes.) Because we consider states that are “closer” to

the starting state before those that are “farther”, we are guaranteed to find the shortest path

to a puzzle’s solution.

For both solvers, we run the risk of encountering a puzzle state that we’ve already seen, and

which already failed to produce a solution. To avoid exploring that state all over again, we

will keep track of states we’ve seen before and just ignore them if we encounter them again.

For certain puzzle types, we might also be able to check whether we can quickly tell if a

puzzle state is unsolvable. Such a check can be incorporated into our search algorithms and

you will do so in your implementation.

Rather than spell out the algorithms in full detail and simply have you translate them into

code, we have put together some worked examples – one of your tasks in this assignment will

be to turn the above high level descriptions and the concrete examples into 2 algorithms you

can implement in Python!

6

The Solver Class

The abstract class Solver has the following methods:

method description

solve returns a path to a solution of the puzzle associated with

the solver. This method is abstract and must be

implemented in a subclass.

You will create two subclasses of the Solver class – DfsSolver, which uses the depth first

search strategy in its implementation of solve, and BfsSolver, which uses the breadth first

search strategy in its implementation of solve.

7

Tasks

We have broken down the assignment into several tasks. For the most part you, can tackle

the assignment in any order that you want, but note that Task 5 requires Task 4 and part of

Task 3 requires Task 2. Task 6 is optional, but is a great way to try out your code and see it

in action!

After reading the handout, docstring examples, and comments in the starter

code, please ask for clarification on Piazza if you still find any of the specifications

below to be unclear.

Any official clarifications will be added to the Assignment 3 FAQ** on Piazza.**

Task 1: a3_sudoku.py

We provide you with a mostly-implemented subclass SudokuPuzzle of class Puzzle.

1. Read and understand the provided code in puzzle.py for the abstract Puzzle class.

2. Read through the SudokuPuzzle class. Understand how the puzzle is represented, how

extensions is implemented, and familiarize yourself with the provided helper methods.

Note that some parts of the code use list comprehensions, as well as the functions any

and all. You do not need to use list comprehensions, but you may find them helpful

in making your code simpler in the next step. These are covered in a worksheet on list

comprehensions for those looking for a quick reference.

3. Implement fail_fast for the SudokuPuzzle class by having it return True for any

sudoku where there is at least one empty position that will be impossible to fill in

because the set of symbols has been completely used up by other positions in the same

row, column or subsquare. You should run the provided doctests to test your code, but

you are encouraged to add more doctests to fail_fast (or write pytests) for further

testing.

Task 2: a3_solver.py

1. Read the dosctrings provided in a3_solver.py and familiarize yourself with the interface

that the Solver class provides.

2. Go through the A3: Search Algorithms Visual Guide (courtesy Sophia!) to make sure

you understand how the depth first and breadth first search algorithms work.

3. Implement the DfsSolver and BfsSolver classes solver.py, based on the depth first

search and breadth first search algorithms described earlier.

4. Many logic puzzles like Sudoku require their solution to be unique. Implement the

has_unique_solution method in the SudokuPuzzle class, based on its docstring

description.

8

You can test your solvers using the provided SudokuPuzzle class and also the other two

puzzle types once you have implemented them.

Once you have completed Tasks 1 and 2, you can try running the provided play_sudoku

module.

Task 3: a3_word_ladder_puzzle.py

1. Read and understand the provided code in a3_word_ladder_puzzle.py.

2. Override the __str__ and __eq__ methods of WorldLadderPuzzle.

3. Override extensions. A legal extension of a WordLadderPuzzle is a new puzzle state

where the new from_word differs by a single letter from the previous from_word.

4. Override is_solved. The puzzle is solved when from_word is the same as to_word.

5. Implement method get_difficulty according to its docstring. (Requires Task 2)

Note: We do NOT require you to implement fail_fast for this puzzle type, as it isn’t entirely

obvious what it should look like! Of course, you are certainly welcome to attempt to devise a

strategy to quickly check if a WordLadderPuzzle has no solution. Feel free to discuss your

approach on Piazza if you come up with anything good!

Once you have completed Tasks 2 and 3, you can try running the provided play_word_ladder

module.

Task 4: a3_expression_tree.py

Note: This part of the assignment requires you to install two python packages

in order for your code to run (you don’t need to write any code using them, but

the code we have provided makes use of them): networkx and pygame-gui (you don’t

need pygame-gui except for in the optional Task 6, but you can install them both now).

Please follow the instructions at the bottom of the Software Guide’s Installing

Python libraries section to install these two packages. Ask on Piazza or visit

office hours if you need help with this.

Before we can implement the ExpressionTreePuzzle class, we need to develop an ExprTree

class to represent an Expression Tree.

1. Read and understand the provided code in a3_expression_tree.py.

2. Implement the folowing methods in the ExprTree class, as specified in the starter code:

• __str__

• __eq__

• populate_lookup

• eval

• substitute

9

3. Implement the function construct_from_list

Expression Tree Format

In this assignment, an expression tree can contain the single digit constants 1-9, single letter

variables containing only the letters a-z, and the operations: addition (+) and multiplication

(*).

Numbers and variables can only occur as leaves of the tree.

Operators must have at least 2 children.

The same variable name may appear more than once in the expression tree.

Variables can be given single digit values 0-9 (As we will see, in the context of the

ExpressionTreePuzzle class, the value 0 corresponds to an “unassigned variable”)

A Convenient Way to Construct Expression Trees

It is cumbersome to create a substantial expression tree using the initializer from class

ExprTree. Function construct_from_list allows client code to create one from a list of

lists instead. Here is a simple example:

[[‘+’], [3, ‘*’, ‘a’, ‘+’], [‘a’, ‘b’], [5, ‘c’]]

The first ‘+’ will be the root of the tree.

The next list contains its children, 3, ‘*’, ‘a’, and ‘+’.

The next list contains the children of ‘*’: ‘a’ and ‘b’.

And the last list contains the children of the second ‘+’: 5 and ‘c’.

Hint: A queue can help keep track of whose children the next list contains.

Visually, the resulting expression tree looks like this (note we use the × symbol to denote

multiplication in the diagram):

This expression tree’s string representation would be: (3 + (a * b) + a + (5 + c))

Evaluating an ExprTree

In order to evaluate an expression tree, a variable lookup dictionary must be provided (see

the eval method). All variables must appear in the lookup dictionary.

For our example above, if the lookup dictionary was {‘a’: 0, ‘b’: 0, ‘c’: 0}, then the

expression tree would evaluate to 8.

If the lookup dictionary was instead {‘a’: 2, ‘b’: 5, ‘c’: 6}, then the expression tree

would evaluate to 26.

10

Task 5: a3_expression_tree_puzzle

Once your ExprTree class is complete, you can implement the ExpressionTreePuzzle class

in a3_expression_tree_puzzle.py.

1. Read and understand the provided code in a3_expression_tree_puzzle.py.

2. Override the __str__ method for the ExpressionTreePuzzle subclass in

a3_expression_tree_puzzle.py.

3. Override extensions. Legal extensions of a state assign each unassigned variable (with

value 0) a value from 1-9. For example, if the variables dictionary was formerly {‘v’:

0}, then each extension would assign a different value from 1-9 to ‘v’. If the variables

dictionary was formerly {‘v’: 5}, then the puzzle would have no extensions, as all

variables have been assigned a non-zero value.

4. Override is_solved as specified in the code.

5. Implement fail_fast for the ExpressionTreePuzzle class. The exact implementation

is up to you, but we have provided a couple of hints in the code if you aren’t sure how

to approach this.

Task 6: Try out your code!

Once you have completed the first 5 tasks you will be able to run:

• play_sudoku.py (requires Tasks 1 and 2)

• play_word_ladder.py (requires Tasks 2 and 3)

• play_expression_tree.py (requires Tasks 2, 4, and 5)

• experiment.py (requires Tasks 2 and 3)

11

There are no marks for this part, but it can be a fun way to debug your code

and further explore what you can do with the code you have written.

You are free to modify or add to any of the code provided in these 3 modules.

Module play_sudoku.py

This module contains a simple GUI to let you try playing the sudoku puzzle you implemented.

It makes use of your solvers in two ways: (1) to create a random SudokuPuzzle of a selected

difficulty level and (2) to provide you with hints as you try solving the puzzle. The code also

has a nice application of inheritance to let us add randomness to the puzzles we generate.

Module play_word_ladder.py

This module contains a simple text UI to let you try playing the word ladder puzzle

you implemented. It makes use of your solvers in two ways: (1) to create a random

WordLadderPuzzle of a selected difficulty level and (2) to provide you with hints if you get

stuck solving the puzzle.

Module play_expression_tree.py

This module contains a simple GUI to let you try playing the expression tree puzzle you

implemented. It makes use of your solvers to provide you with hints.

Module experiment.py

This module runs a small experiment and produces output that you can review to verify your

understanding of how the solvers perform on different puzzles. Feel free to add your own

experiments and share any interesting observations you make with the class!

Sample Output:

Puzzle Type Solver len(sol) time

Sudoku Bfs 13 0.01907

Sudoku Dfs 13 0.00139

Sudoku Bfs 54 0.43171

Sudoku Dfs 54 0.15584

WordLadder Bfs 5 0.03384

WordLadder Dfs 703 0.04225

Polish!

Take some time to polish up. This step will improve your mark, but it also feels so good.

Here are some things you can do:

• In each module you are submitting, run the provided python_ta.check_all() code to

12

check for errors and violations of the “PEP8” Python style guidelines. Fix them!

• Check your docstrings to make sure that they are precise, complete, and that they

follow the conventions of the Function and Class Design Recipes.

• Read through and polish your internal comments.

• Remove any code you added just for debugging, such as print statements.

• Remove the word “TODO” wherever you have completed the task.

• Take pride in your gorgeous code!

submitting your work

Submit the following files on MarkUs

a3_solver.py

a3_sudoku_puzzle.py

a3_word_ladder_puzzle.py

a3_expression_tree.py

a3_expression_tree_puzzle.py

We strongly recommend that you submit early and run the provided self tests

on MarkUs as you go.

We will grade the latest version you submit within the permitted submission period.

Be sure to run the tests we’ve provided within MarkUs one last time before the due date.

This will make sure that you didn’t accidentally submit the wrong version of your code, or

worse yet, the starter code!

How your assignment will be marked

There will be no marks associated with defining your own test cases with pytest or hypothesis.

The marking scheme will be approximately as follows:

Category Weight

pyTA 10 marks

MarkUs self tests 20 marks

hidden tests 70 marks

13