程序代写案例-CS5011-Assignment 2
School of Computer Science, University of St Andrews, CS5011, 2020-21
CS5011: A2 - Logic - ‘Easy As ABC’ Hint System
Assignment: A2 - Assignment 2: Logic
Deadline: 10th of March 2021
Weighting: 25% of module mark
Please note that MMS is the definitive source for deadline and credit details. You are
expected to have read and understood all the information in this specification and any
accompanying documents at least a week before the deadline. You must contact the
lecturer regarding any queries well in advance of the deadline.
1 Objective
This practical aims to implement a hint system for the puzzle game ‘Easy as ABC’ using logical
techniques.
2 Competencies
• Design, implement, and document procedural AI logic algorithms.
• Design, implement, and document encodings of logic problems into Satisfiability.
• Compare the procedural and declarative AI logic methods.
3 The Easy as ABC Puzzle
‘Easy as ABC’ is a puzzle game in which we have to fill letters in a grid. (It must be said that
most people do not find it that “easy”.) Each cell in the grid has to be filled in either with one of
the letters in the puzzle, or left blank. The rules of the puzzle state that each letter in the puzzle
should appear once in each row and column (but not twice). Also, where a letter outside the
grid is given, it has to be the first letter visible in that row/column and direction.
An example is shown in Figure 1. The solution is also shown in Figure 1, where an X in the
solution represents a blank square. In this puzzle the letters are A, B, C, and D. We must put
one (not two or zero) of each letter in each row and in each column. Since there are four letters
and the grid is 6 by 6, there must be exactly two blank squares in every row and column. The
final rule, about seeing a letter first, needs a little bit of explaining. Let’s look at the left hand
column of clues. The bottom two clues are both A. The rule is that the first letter visible in that
direction must be an A in both rows. We can’t have an A in both positions in the first column,
so one of them must be blank, with the next square either being blank or an A. However many
blanks we need, which in this case is at most 2, the first non-blank square must be an A. Now
look at the right hand column of clues. Here there are three As. Only one of those rows can
start on the right with an A, so the other two have to be X. Then in the second-right column,
one of those two also has to be an X, and then finally that third row has its A following two X’s
in the first two cells on the right: in this case it’s the A in the second row.
1
Figure 1: ‘Easy as ABC’ puzzle and solution taken from http://tectonicpuzzel.eu/
easy-as-abc-puzzle%20techniques.html. Note that ‘blank’ squares in the solution are
marked with an X: this is to make it easy to tell the difference between a square being not
filled in yet and it being ‘blank’ (filled with an X) The yellow square is of no significance, just
showing where the cursor was when I took the screenshot.
In the first puzzle the letters are the obvious ones of A-D, and every row and column has
a clue. But neither of these are required. Figure 2 shows an example problem, ‘AUGUST’, in
which neither property holds. Several rows and columns have no clues, and the set of letters
is AGSTU. Our format for puzzles will allow both of these. You might enjoy solving this puzzle,
but hopefully whether or not you solve it by hand, your program should be able to solve it!
4 The Practical
In this practical, we are going to use logical methods to do various tasks relating to the ABC
puzzle. In Part 1, you will write a procedural method to check the logical constraints on the
problem being satisfied. In Part 2, you will write a procedural method to make some logical
deductions about what can be deduced. In Part 3, you will use a declarative method which
will be able to check constraints but also be able to solve complete puzzles. In Part 4, you will
use any combinations you wish of procedural and declarative methods to provide a system for
providing hints to each user.
Research-led teaching: Part 4 is an example of ‘research-led teaching’: it is something we
are actively researching at St Andrews, and we don’t have all the answers about how to do it.
So we do not expect perfect hint systems from you. We are genuinely interested to see what
you come up with!
4.1 Part 1: Checking Correctness Procedurally
You are provided with some skeleton code so that basic properties of puzzles and grids are
already defined. You are free to add additional classes if you wish to structure your code, but
the methods required below should be within the class part1/CheckerABC. You are to complete
the simplementation of isFullGrid and isConsistent, as follows.
• isFullGrid should test whether a given grid is completely assigned with valid letters or
blanks from the puzzle, i.e. with no cells not yet filled in.
2
Figure 2: ‘Easy as ABC’ puzzle by Prasanna Seshadri. Taken from http://www.gmpuzzles.
com/blog/2015/09/easy-as-abc-by-prasanna-seshadri/.
• isConsistent should test if all the constraints of the puzzle are obeyed for every square
except the constraint that every square should be filled in. So for example, if we have
the same letter twice in the same row then this breaks the constraint that letters appear
only once, even if there is an unfilled square in the row. Similarly, if a row is entirely filled
in but one letter is not in that row, then that breaks the constraint. However, if we have
a row which contains an unfilled square, then we cannot indicate inconsistency even if
there are letters not in the row.
Note that once you have done these two methods, you have automatically implemented
isSolution since this is true precisely when both the above methods return true. A number
of tests are provided which should make clear when it is intended that these methods should
return true or false.
4.2 Part 2: Making Deductions Procedurally
In this part, you will write methods which, given a puzzle and a partially filled in grid, produce
a grid in which some deductions are made and filled in the grid. You are free to add additional
classes if you wish to structure your code, but the methods required below should be within the
class part2/ProceduralABC.
For each of the following techniques, implement a method which takes a partially filled
grid and returns a grid in which the rule has been applied to every square in the grid. Some
techniques are fairly obvious for making deductions, while some more complex ones are also
described at the following URL, and we are asking you to implement some (but not all). http:
//www.tectonicpuzzel.eu/easy-as-abc-puzzle-solving-techniques.html.
In each of the following, the method to be implemented should return a new Grid object,
containing all the same filled in squares as the input grid, with any unfilled squares completed
if they can be filled in by the technique being implemented.
1. Implement the technique “Corners with Different Clues.” If any corner has different clues
in the row and column adjacent to it, there must be an X in that square. There is no
example in Figure 1, but e.g. if the first clue in the top line of clues was C instead of D,
the top left corner would have to contain an X. Implement differentCorners to achieve
this.
3
2. If any given square is the only unfilled square in a row or column, and one letter does not
appear in that line, then it must go in that square. Implement onlyPlaceForLetterRow
which fills in squares which implements this for rows, and onlyPlaceForLetterCol which
does it for columns.
3. If every different letter appears in a row or column then the remaining squares in that line
must be blank. Implement fillInBlanksRow and fillInBlanksCol to achieve this.
4. Implement the technique “Look for Common Clues.” To be precise, if every clue is given
on one side, and there is only one place for one clue for any letter, that letter must appear
in the first square in that row or column. For example, in Figure 1, there must be a B
followed by A in the last two squares in the top row, because those are the only places
for those clues. Implement commonClues() to achieve this.
Tests are given in the sample code to clarify what is expected in each case. Other procedural
techniques are possible and in Part 4 youmight wish to implement some you find online or invent
yourself.
4.3 Part 3: Solving Puzzles Declaratively
We are going to encode the problem using propositional logic, and then use the LogicNG li-
brary1 to use a SAT solver to solve the puzzles. You are free to add additional classes if
you wish to structure your code, but the methods required below should be within the class
part3/DeclarativeABC.
Expressing The Constraints of the Puzzle: We are going to have a propositional variable
for each combination of square and symbol that could be there. The proposition will be true if
that square is occupied by that letter. With these variables, we can encode the constraints of
the puzzle as follows:
• Every square contains at least one symbol
• Every square contains at most one symbol
Notice that the two statements above don’t really express anything about the problem, but
instead make sure that the logical model is consistent with core facts about the puzzle, i.e.
that we can only write one symbol in each square. We can now move on to expressing
the logical properties of the core problem.
• Every row/column has every letter at least once. It will have one or more blank squares
unless the number of letters is the same as the size of the grid.
• Every row/column has each letter at most once. Notice that the symbol for a blank square
can occur more than once.
• Where a clue is given in a row/column, the first symbol in that row/column direction is
consistent with the clue, i.e. the first non blank symbol is the clued letter. If no clue is
provided, no restriction applies.
You are strongly advised to implement the clauses for each constraint separately and test
them individually. To aid this you might wish to add test functions and cases.
Within package part3 and class DeclarativeABC, complete the implementation of methods:
1https://github.com/logic-ng/LogicNG
4
• setup which sets up any necessary data structures
• createClauses which creates the necessary clauses
• solvePuzzle which uses a MiniSAT solver to solve the problem
• modelToGrid which (when the puzzle has been solved) returns a Grid object with the
solution in it.
Testing Suggestion: For any puzzle which is solvable, the method isSolution from Part 1
should succeed when passed the result of this last function.
4.4 Part 4: Creating a Hint System
For this part of the practical we are not giving as clear guidance as the earlier parts. It is up to
you to decide how tomake a hint system as good as possible and how hints should be presented
to the user. This part of the practical should be implemented in the class part4/HintABC.
Wewant you to provide a hint systemwhich, given a puzzle, provides a sequence of squares
to fill in that lead to a solution. Each move should definitely be correct, but also ideally should
be the one that a human could best understand of the possible moves available at that time.
We are not concerned with issues about user interface design, we are addressing the core
algorithms that might be used to decide what move to suggest next to a human player.
Your program should produce a sequence of hints for a given puzzle that lead to a complete
solution. Each hint should be the assignment of a square to its correct symbol, listed in the
best order possible to make the chain of reasoning as easy as possible to understand. So, for
example, if we have a program that can solve a puzzle, then we could simply choose a random
square in the grid and print out which letter it should be, but this would be a bad hint. Ideally
we want a square and letter which is as understandable as possible.
You are free to, and encouraged to, use the methods from the above parts. You might
want to use the procedural methods from Part 2, and the logic clauses from Part 3, either
individually or together. It is also completely acceptable to write newmethods, either procedural
or declarative, based on techniques you find online or invent yourself. Some techniques you
might find would be considered advanced techniques (see below), for example if they involve
hints which don’t determine the complete value of a square but instead just rule out one value
from it.
4.4.1 Advanced Hint Techniques
You may wish to extend your work with one of the following more advanced techniques. Please
note that there is no benefit for implementing more than ONE of the following. Examples of
additional functionalities include:
1. Add to the hint system hints that eliminate individual symbols from a square as well as
ones that finally set the symbol in a given square. For example, if we have a given
letter in a square it cannot occur in any other square in the same row or column, which
might be useful information in other squares. For a more complex example, see the
technique ‘cross-referencing between rows and columns’ from http://tectonicpuzzel.
eu/easy-as-abc-puzzle-solving-techniques.html
2. Create “explanations” in English for hints instead of simply printing out valid assignments.
If you choose to do this we will be looking for explanations which are as understandable
as possible.
5
5 Code Specification
5.1 Code Submission
The program must be written in Java and your implementation must compile and run without
the use of an IDE. Your system should be compatible with the version of Java available on
the School Lab Machines (Amazon Corretto 11 – JDK112). Please do not use libraries that
implement algorithms for tasks like puzzle solving that are key to the practical, but other libraries
that are secondary to the objectives of the practical can be used. Your source code should be
placed in a directory called A2src/ and should include all non-standard external libraries. The
code must run and produce outputs as described in the next sections.
Please note that code that does not adhere to these instructions may be penalised.
5.2 Starter Code
For this practical, a number of starter classes are provided. You are free to extend these and
add additional classes if you wish to help you complete the program in the best way possible.
The starter code should compile and run, though of course failing most tests.
A2main.java contains example code which scans input and makes an appropriate call. You
can extend this with additional commands if you wish.
The package mains contains Puzzle.java and Grid.java. with definitions of the two key
data structures for puzzles and partial or complete solutions of the puzzles. Some basic data
consistency methods are provided, as is a method for printing out a grid together with its puzzle.
A skeleton class is provided in each package part1, part2, part3, and part4. These
should each be extended to complete the relevant part. You are free to add classes to each
part and/or to add classes in other packages: for example you might have some utility code
that would be best shared among the packages.
Within the tests package, a number of sample puzzles and grids are provided. These are
defined as Enum Type3. For example, puzzle ABC1 is the puzzle presented in Figure 1, with
the solution in the grid ABC1Sol. You should feel free to add puzzles and grids to these classes,
but please do NOT modify the samples that are already there.
Also in tests you will find some testing classes. TestsBase provides ability to run simple
tests for methods in parts 1 to 3 and TestsStaff provides our sample tests. A skeleton class
TestsStudent is provided for you to add tests for all parts of the practical. You are not limited
to adding tests only using TestsBase and are free to use other methods such as JUnit.
The directory also contains two jarfiles for the LogicNG and ANTLR libraries, for your conve-
nience. If it works better for you to compile them separately or obtain them yourselves, please
feel free to do so.
5.3 Running
Your code should run using the following command:
java A2main
For example, to test all of parts 1 to 3 on the staff tests you would run
java A2main TEST StaffAll
2https://aws.amazon.com/corretto/
3https://docs.oracle.com/javase/tutorial/java/javaOO/enum.html
6
If you wish you may add other commands/options to the program as long as the above still
works.
For Parts 1 to 3, we have provided test sets but you are STRONGLY encouraged to add
additional tests as you work.
For Part 4, no specific format is required and therefore no tests are provided, but you should
demonstrate adequate testing in your report. You might wish to add arguments to allow for hints
to be given appropriate inputs or settings, in which case they should be documented.
6 Report
You are required to submit a report describing your submission in PDF with the structure and
requirements presented in the additional document CS5011_A_Reports. The core sections
(Design, Implementation and Evaluation) have an advisory limit of 1500 words in total. The
report should include clear instructions on how to run your code. Consider the following points
in your report:
1. Describe what testing you have done for all the above beyond the tests provided to you.
2. Describe the implementation of the procedural algorithms clearly, as well as the imple-
mentation of the encoding into clauses.
3. Describe how your hint system works.
4. In your evaluation for parts 2 and 3, what insights did you gain to the difference between
implementing logic methods procedurally or declaratively?
5. In your evaluation for your hint system, how good is it at choosing a good hint next? And
how can you tell?
7 Deliverables
A single ZIP file must be submitted electronically via MMS by the deadline. Submissions in any
other format may be rejected.
Your ZIP file should contain:
1. A PDF report as discussed in Section 6
2. Your code as discussed in Section 5
8 Assessment Criteria
Marking will follow the guidelines given in the school student handbook. The following issues
will be considered:
• Achieved requirements
• Quality of the solution provided
• Examples and testing
• Insights and analysis demonstrated in the report
7
Some guideline descriptors for this assignment are given below:
• For a mark of 7 to 10: the submission implements the procedural checker in part 1, im-
plemented in full at the higher end of this range, adequately documented or reported.
• For a mark of 10 to 13: as well as the checker, the submission implements the procedural
solvingmethods fromPart 2, in full at the higher end of this range, adequately documented
or reported.
• For a mark of 13 to 16: the submission implements the methods in Parts 1 and 2, and the
declarative methods in Part 3, with complete implementations of all parts at the higher end
of this range. The code submitted is of an acceptable standard and is tested appropriately,
and the report describes clearly what was done, with good style.
• For a mark of 16 to 18: the submission implements all four parts of the practical, including
being able to give a complete set of well-chosen hints at the higher end of the range. It
contains clear and well-structured code and is tested well, and a clear report showing a
good level of understanding of design and evaluation of logic algorithms.
• For a mark above 18: all of the above and EITHER the submission implements one of the
advanced techniques suggested OR a particularly outstanding hint system is provided.
9 Policies and Guidelines
Marking: See the standard mark descriptors in the School Student Handbook
https://info.cs.st-andrews.ac.uk/student-handbook/learning-teaching/feedback.html#
Mark_-Descriptors
Lateness Penalty: The standard penalty for late submission applies (Scheme B: 1 mark per
8 hour period, or part thereof):
https://info.cs.st-andrews.ac.uk/student-handbook/learning-teaching/assessment.html#
latenesspenalties
Good Academic Practice: The University policy on Good Academic Practice applies:
https://www.st-andrews.ac.uk/students/rules/academicpractice/
Ian Gent
[email protected]
February 19, 2021
8

欢迎咨询51作业君
51作业君 51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: ITCSdaixie