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作业君
