[SOLVED] 代写 algorithm game Java Homework 3 — Constraint satisfaction problems

Homework 3 — Constraint satisfaction problems
UWL CS452/552 Artificial 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 fill 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 left 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 specification files. A puzzle specification file 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 specification file 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 first task in creating your CSP solver for these puzzles is loading in a puzzle specification
file. Therefore, please create a class PuzzleSpec with:
• A constructor taking a single String argument, the text file holding the puzzle specifi- cation. The constructor should read and decode the file 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 hori- zontal, 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 in- stances. 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 ar- guments 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 first step is due on Sunday, October 27.
2. The main step of this homework is to write a class CrosswordSolver implementing back- tracking CSP search. In the constraint problem you will have set up with the first step, variables correspond to WordSlot instances, constraints correspond to Intersection in- stances, 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 file 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 specified 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 find (or fail to find) the solution.
* Method toStrings, which takes no arguments, and which returns an array of strings depicting the final 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 specification 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 satisfies 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 •
•
•
This 3. Step
files 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.
second step is due on Monday, November 4.
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 pre- processor 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 after 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 files: 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 specification enumerates methods which classes must provide, it does not forbid additional methods. You are free to create additional methods to help you manage, de- bug, trace, etc. these structures and processes. Likewise, you are free to create additional constructors for these classes.
4

However, in the final submitted versions of your classes, you must turn off all debugging output. The required methods must not print anything to any output stream except as specified 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 specification (but not the correctness of the implementation), so be sure to look at the output from Autolab.
• Do include the files from Part 1 with your submission for Parts 2 and 3. It is OK to fix bugs which you found or otherwise improve your code after submitting Part 1 (although grading for Part 1 will be based only on the Part 1 submission).
PPPPP
5