Homework 3 — Constraint satisfaction problems
UWL CS452/552 Articial Intelligence
Fall 2019
For your third homework, please write a constraint solver for crossword puzzles. Crossword
puzzles are pen-and-paper games which ask the player to complete a grid of squares by writing
down words, one letter per square. The grids and their solutions follow a few simple rules:
• Words begin at numbered squares, and ll up all blanks leading across or down from that
number until encountering the edge of the puzzle or a black square.
• Horizontal (across) words always have a puzzle edge or a black square to the le of their
number; vertical (down) words always have a puzzle edge or a black square above their
number. One numbered square may see the start of both a horizontal and a vertical word.
• If two words intersect at a given blank square, their letters must match.
Blank Filled
Puzzle specication les. A puzzle specication le will begin with two integers specifying the
number of rows and columns in the puzzle. It will then have a corresponding grid of numbers,
mixed with symbols for blank squares (the underscore symbol ) and black squares (the letter X).
For the example blank grid above, its specication le would be:
In a large puzzle, the number may be multiple-digits. Extra spaces between numbers, underscores
and Xs should be ignored.
Deliverables
This homework is to be completed in Java.
1. A rst task in creating your CSP solver for these puzzles is loading in a puzzle specication
le. Therefore, please create a class PuzzleSpec with:
• A constructor taking a single String argument, the text le holding the puzzle speci-
cation. The constructor should read and decode the le contents to set up the results
of the methods of PuzzleSpec instances.
• Two methods
public int getWidth();
public int getHeight();
giving the width and height of the puzzle.
• A method getWords, which returns a java.util.List of WordSlot instances. Your
class WordSlot should provide at least the following:
– Method getLength, taking no arguments and returning the length of the word as
an int. – Method getNumber, taking no arguments and returning the number labelling the
slot as an int. – Method isHorizontal, taking no arguments and returning true if the slot is horizontal, or false if vertical.
The result of getWords should include all of the numbered slots for words in the puzzle.
The list returned from getWords must either be immutable, or a shallow copy of the
list stored internally to the PuzzleSpec instance so that changes to the result of a call
to getWords do not alter the internals of the PuzzleSpec instance.
• A method getIntersections, which returns a java.util.List of Intersection instances. Your class Intersection should provide at least the following:
– Methods getVerticalSlot and getHorizontalSlot, each taking no arguments and
returning the WordSlot instances of the intersecting slots.
2
– Methods getVerticalPosition and getHorizontalPosition, each taking no arguments and returning an int giving the character of the respective word slot
which is common to the two slots.
The result of getIntersections should include descriptions all of the intersections of
word slots in the puzzle. As with the list returned from getWords, the list returned
from getIntersections must either be immutable, or a shallow copy of the list stored
internally to the PuzzleSpec instance.
This rst step is due on Sunday, October 27.
2. The main step of this homework is to write a class CrosswordSolver implementing backtracking CSP search. In the constraint problem you will have set up with the rst step,
variables correspond to WordSlot instances, constraints correspond to Intersection instances, and domains for the variables arise from the lists of words we describe below.
• The constructor for CrosswordSolver should take a single String argument giving a
le which contains a list of words, one word per line, to be used in solving puzzles
with this CrosswordSolver instance.
• Instances of class CrosswordSolver should provide a method solve which
– Takes one PuzzleSpec argument, and
– Returns a PuzzleSolution instance. Instance of your class PuzzleSolution must
provide at least the following:
* Method solvable, which returns true exactly when the puzzle has a solution.
* Method getWord which takes an instance of WordSlot, and returns the String
word to be entered into that slot for this solution. The behavior of this method
is not specied if either the puzzle has no solution, or if the WordSlot instance
is not part of the PuzzleSpec provided to method solve. * Method getCallCount, which prints the number of recursive calls required to
nd (or fail to nd) the solution.
* Method toStrings, which takes no arguments, and which returns an array of
strings depicting the nal solution, one string per line. The strings should omit
number labels, and use a space for black squares in the grid. For example,
the strings returned in the result array for the solved puzzle earlier in this
specication would be
"DEVELOP"
"E E E R"
"TORNADO"
"R B T G"
"ANOTHER"
"C S E A"
"THEOREM"
Your solve method is to employ recursive backtracking search, as explained in lectures
and the textbook. When choosing a variable, use the Most-Constrained-Variable heuristic,
and break ties using the Most-Constraining-Variable heuristic. Values of variables can be
iterated over in any order. For this step, you can leave out the Inference step from the
algorithm. Search should terminate when either a variable assignment is found that
satises all constraints or no such solution is found, and search fails.
3
Document the steps of your solve method to explain how you implement the various
aspects of your CSP solver and the backtracking algorithm.
At this step, your code should be able to solve small puzzles most of the time. The sample
data les linked from Canvas can help you to test your implementation and its abilities:
• The simplest puzzle grid xword00 should be solvable against all three of the dictionaries
very quickly.
• The second-simplest puzzle grid xword01 should be solvable using the small and medium
dictionaries. A proper implementation will solve the puzzle against the small dictionary
very quickly, while the medium case may take several seconds. Your implementation
should be able to solve the second puzzle against the large dictionary as well, although
it may take a few minutes.
• The more complex puzzle grid xword02 is not solvable with the small dictionary, and
your solution should be able to determine this very quickly. This puzzle is solvable
against the larger dictionaries, but will require at least several minutes, and probably
at least an hour.
This second step is due on Monday, November 4.
3. Step 3 is required for CS 552 students, and is optional for CS 452 students.
Revise your CrosswordSolver solution to use the method of arc-consistency as a preprocessor for solving a CSP, to reduce the number of actual values allowed for the variables
in the problem. Implement the AC-3 algorithm given in the text, and run it on the CSP
problem before performing search.
Extend your class PuzzleSolution class with two additional methods for this step:
• Method domainSizeBeforeAC3 takes a WordSlot instance, and returns the size of the
domain associated with that variable before running AC3.
• Method domainSizeAfterAC3 takes a WordSlot instance, and returns the size of the
domain associated with that variable aer running AC3.
If properly implemented, the search should then proceed very quickly to a solution or failure
state, for any combination of puzzle and dictionary les: make sure that this is true of your
implementation.
This third step is due on Monday, November 11.
Additional technical details
• All of the code you write for this assignment should be housed in the package h3. I suggest
that you set up code in this package from the beginning, to avoid last-minute aggrevation
from re-packaging your code at the last minute.
• Where this specication enumerates methods which classes must provide, it does not forbid
additional methods. You are free to create additional methods to help you manage, debug, trace, etc. these structures and processes. Likewise, you are free to create additional
constructors for these classes.
4
However, in the nal submitted versions of your classes, you must turn o all debugging
output. The required methods must not print anything to any output stream except as
specied here.
• You are free to use interfaces and classes from the standard Java library packages java.lang,
java.util and java.io . You must get my approval before using other library classes.
• Assignment submission will be via Autolab. Further submission instructions will be posted
to Canvas by the end of the week before each deadline. Autolab will check that your solution
meets the API described in this specication (but not the correctness of the implementation),
so be sure to look at the output from Autolab.
• Do include the les from Part 1 with your submission for Parts 2 and 3. It is OK to x bugs
which you found or otherwise improve your code aer submitting Part 1 (although grading
for Part 1 will be based only on the Part 1 submission).