Assignment #2automated puzzle solving solution

overview

Puzzle solving is a typically human activity that, in recent decades, is being explored in the context of computers. There are two benets to this: rst, we can o
-load some puzzle-solving tasks to computers, and second, we may understand human puzzle-solving better by studying how to implement it on a computer.

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

full information: all information about the puzzle conguration at any given point is visible to the solver; there are no hidden or random aspects

well-de ned extensions: a denition of legal extensions from a given puzzle conguration to new con
well-de ned solution: a denition of what it means for the puzzled 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 functions are 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 solving functions. Although there may be faster puzzle-specic solvers for a particular puzzle by knowing specic features of that puzzle, the general solvers are designed to work for all puzzles of this sort.

abstract Puzzle class

The abstract class Puzzle has the following methods, which are not implemented, but meant to be imple-mented in subclasses:

is solved: returns True or False, depending on whether the puzzle is in a solved conguration or not


extensions: returns a list of extensions from the current puzzle conguration to new congurations that are a single step (\move") away

fail fast: returns True or False, depending on whether it is clear that the current puzzle con
guration can never be completed, through a sequence of extensions, to a solved state


And that's it. Notice that there is no init method, since the representation and initialization of puzzles in this class vary widely. Each subclass will need an init method to represent a particular puzzle.


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, lled in. The symbols must be from a set of with    n symbols. The
goal is to ll in the remaining symbols in such a way that each row, column, or pn  pn subsquare, has each symbol exactly once. In order for all of that to make sense, n must be a square integer such as 4, 9, 16, 25, ...


You may want to read more about sudoku to get a feel for the puzzle.

We provide you with a mostly-implemented SudokuPuzzle subclass of Puzzle. We, however, did not override the fail fast method inherited from Puzzle, and you should be able to do better.

Implement fail fast for sudoku by having it return True for, and hence abandoning, any sudoku congu-


ration where there is at least one empty position that will be impossible to ll because the set of symbols has been completely used up by other positions in the same row, column or subsquare. Experiment to see whether this makes any di
erence in the performance of solver(s) for sudoku.

peg solitaire

This puzzle has gone by various names: Hi-Q, peg solitaire, solo noble, and patience, and has been around for several hundred years.

You are presented with a grid where most positions are occupied by a peg, marble, or other movable piece. The object is to \jump" a piece over a neighbouring piece and into an empty position, allowing you to remove the piece that was jumped over. A successful game leaves only one piece on the board.

Boards come in various shapes of grid. We will assume that some portion of an m  n grid is used, that some positions may be unused (no pieces may be placed there), some positions begin with pieces in them, and that a few (often just one) position is left empty to allow jumping. You can see various versions of peg solitaire on the web.
We provide you with the class declaration and    init    method for subclass GridPegSolitairePuzzle of


Puzzle.

You will override the extensions and is solved methods for this subclass, which make it possible for the


solvers (which you'll also write) to solve it. A legal extension of a GridPegSolitairePuzzle is a new conguration

that you can get to in a single jump. The puzzle is solved when a single peg is left.

We do not require you to override the fail fast method, although you are welcome to see whether you can


come up with one that improves performance.

word ladder

This puzzle involves starting with from word, from a set of allowed words, and deriving to word from the same


set of allowed words, by changing one letter at a time. Each changed letter must result in a word that is is from the same set of words. Here's an example, assuming that the set of words is a rather large set of English words provided to many computer applications. The goal is to get from cost to save

cost ! cast ! case ! cave ! save

We provide you with the class declaration and   init  method for subclass WordLadderPuzzle of Puzzle. You will override the extensions and is solved methods for this subclass. A legal extension of a WordLad-derPuzzle is a new con
guration where the from word di
ers by a single letter from the previous from word. A


WordLadderPuzzle is solved when the from word is the same as the to word.



We don't require you to override the fail fast method, although you are welcome to see whether you can come up with one that improves performance.


mn puzzle
Sometimes called the 15-Puzzle, Boss Puzzle, or Game of 15, this puzzle consists of a 4  4, 3  3, or (in general) an mn, grid with one empty position. A player must swap symbols with the empty position until they get the entire puzzle into the correct order.

We provide the class declaration and init method for subclass MNPuzzle. You will override is solved and extensions methods to allow the solvers to solve this puzzle. The puzzle is solved when the conguration


is the same as the supplied target conguration. Legal extensions of a conguration swap the empty space with either the symbol to its right, the symbol to its left, the symbol above it, or the symbol below it.

We don't require you to override the textbffail fast method, but you are welcome to see whether you can design one that improves performance.


searching

One approach to solving a puzzle is to systematically search for a solution, starting from the current con-guration. To make this daunting task even possible, we have to be sure that we have a systematic way of checking out puzzle congurations, and that we don't re-visit the same conguration twice.

You will implement two standard systematic searching techniques. We are well aware that plenty of code and pseudo-code for these are \out there" on the web, so you have to be very careful you are giving credit for any ideas you recycle, in order to avoid an academic o
ense.

depth-first search
As the name suggests, you search deeply before you search broadly.
1. don't bother with any puzzle con guration if it's been seen before
2. check whether the current puzzle con guration is solved; if so you're done; otherwise...
3. for each extension of the current puzzle con guration, make that extension the current puzzle con g-
uration and return to step 1
Notice how this process unwraps. You check a con guration, then one of its extensions , then one of the
extension’s extensions , and so on. That means that if a con guration has several extensions, you will be
checking every possible chain of extensions from one of them before you check the others.
Notice also that if there are no extensions, step 3 is empty.
You will implement depth rst solve following this strategy. You are welcome to read material on depth-
rst search, but be aware of several things:
# the return type for depth first solve is a PuzzleNode 1 that must be the rst node in a path of PuzzleNode s
that lead from the given con guration to a solution
# give credit for ideas from the web that you recycle, so you won't be guilty of an academic o ense.
1 PuzzleNode s
are de ned in puzzle tools.py
3breadth-first search
As the name suggests, you search broadly before you search deeply.
1. skip any puzzle con guration that has already been seen
2. check whether the current puzzle con guration is solved; if so you're done, otherwise
3. check whether any extensions of the current puzzle con guration are solved; if so you're done, otherwise
4. check whether any extensions of extensions of the current puzzle con guration are solved; if so you're
done, otherwise
5. . . .
Notice how this approach examines con gurations that are \closer" to the starting con guration before it
examines those that are \farther." This may be useful for nding a shortest solution to a puzzle.
You will implement breadth rst solve following this strategy. You are welcome to read material on
breadth- rst search, but be warned:
# the return type for breadth first solve is a PuzzleNode that is the rst node in a path of PuzzleNode s from
the current puzzle con guration to a solution
# give credit for ideas from the web that you recycle, so you won't be guilty of an academic o ense
starter code
You'll nd the following les, with associated tasks, in Starter. Leave the class declarations, init methods,
and the if name == ” main :” block as you nd them: we have veri ed that neither PyCharm 2 nor PEP8
disapprove of them.
puzzle.py Read and understand the Puzzle class.
sudoku puzzle.py Read and understand the SudokuPuzzle class, then override the fail fast method inherited
from Puzzle .
grid peg solitaire puzzle.py Read the init method, then override the extensions and is solved methods inherited
from Puzzle .
word ladder puzzle.py Read the
from Puzzle .
init
method, then override the extensions and is solved methods inherited
mn puzzle.py Read the init method, then override the extensions and is solved methods inherited from Puzzle .
puzzle tools.py Read and understand the PuzzleNode class, then implement module-level functions depth first solve
and breadth first solve .
2 Well,
at least, PyCharm Community Edition 5.0.4
4declaring your assignment team
You may do this assignment alone or in a team of either 1, 2 or 3 students. Your partner(s) may be from
any section of the course on St George campus. You must declare your team (even if you are working solo)
using the MarkUs online system.
Navigate to the MarkUs page for the assignment and nd \Group Information". If you are working solo,
say so. If you are working with other(s):
First: one of you needs to \invite" the other(s) to be partners, providing MarkUs with their cdf user name(s).
Second: the invited student(s) must accept the invitation.
Important: there must be only one inviter, and other group members accept after being invited, if you want
MarkUs to set up your group properly.
To accept an invitation, nd \Group Information" on the appropriate Assignment page, nd the invitation
listed there, and click on \Join".
submitting your work
Submit the following les on MarkUs by 10 p.m. March 24th:
#
#
#
#
#
sudoku puzzle.py
grid peg solitaire puzzle.py
word ladder puzzle.py
mn puzzle.py
puzzle tools.py
Click on the \Submissions" tab near the top. Click \Add a New File" and either type a le name or use the
\Browse" button to choose one. Then click \Submit". You can submit a new version of a le later (before
the deadline, of course); look in the \Replace" column.
Only one team member should submit the assignment. Because you declared your team, all of you will
get credit for the work.