Hello, i have attached the questions for my assignment. i will be sending the codes for the second question. the first question's code is attached.
Assignment 4 A Purpose and Background Implement a Sudoku solver using the algorithm presented in the Lee et al. textbook. A Sudoku is a number puzzle. It consists of nine 3x3 matrices. Each of these 3x3 matrixes is called a block. The nine blocks are positioned in 3x3 fashion. As a result, the entire Sudoku matrix (or grid) is a 9x9 matrix. The 81 cells of the grid are therefore organized into rows, columns, and blocks. Each cell belongs to different rows, columns and blocks and we call these groups. For example, all cells on row 1 belongs to the same group i.e. row 1. All the cells on column 1 belongs to the same group i.e. column 1. As a result, each cell belongs to a particular row, a particular column and a particular group. Each cell stores a number that ranges from 1-9. The following shows an example of a Sudoku grid. Figure 1. A Sudoku Grid (Adapted from Lee et al. Figure 5.1) The puzzle starts with a grid that is partially filled such as what is shown in figure 1. The goal of the puzzle is to fill all cells (each cell can only take in a number between 1 to 9) such that for each row, each column and each block, the number 1 to 9 appears only once. For example, on figure 1, the number “7” appeared on the third cell (from the left) on the bottom row. As a result, the number “7” cannot appear on any other cell on the bottom row. One way to solve a Sudoku puzzle is by the process of elimination. For example, consider the top left block of the grid shown in figure 1. The numbers 8 and 6 are on the bottom row of this block. Therefore, these two numbers cannot appear on any other cells on this block and so we know that the remining 7 cells must take in the following numbers: 1,2,3,4,5,7,9. To help us visualize the problem, we can annotate the grid with candidate numbers. This is shown in figure 2. Figure 2. A Partially Annotated Sudoku Puzzle (Adapted from Lee et al. Figure 5.2) Figure 2 shows a Sudoku grid with candidate numbers annotated for the top left block. Consider the middle cell (row 2, column 2) of this block. We start with all candidate numbers (i.e. 1-9) and starts eliminating numbers as we see them appear on different row/column/block on the grid. The number 1 can be eliminated because the number 1 appears on row 2 column 5. Similarly, the number 9 and 2 can also be eliminated because they appear on row 2 column 8 and 9 respectively. The number 8 can also be eliminated because it appears on row 3 column 2. Examination of other numbers on column 2 shows that the number 3 and 9 can be eliminated since they appear on row 7 and 8 respectively. Lastly, the number 8 and 6 can also be eliminated because they appear in the same block. As one can see, some numbers (e.g. 8 and 9) can be eliminated for multiple reason (e.g. they appear on the same block as well as the same row/column). At the end of this elimination process, we end up with the following candidate numbers for the cell at row 2, column 2: 4,5 and 7 – these are the only numbers that can be on row2, column 2. Lee et al. presented two general rules to solve most of the Sudoku puzzles. The rules are as follows: Rule 1: Within a group (e.g. within a particular row, within a particular column or within a particular block) look for cells that contain the same set of candidate values. If the cardinality of the set (i.e. the number of items in the set) matches the number of duplicate sets found, then the items of the duplicate sets may safely be removed from all non-duplicate sets in the group. This rule applies even in the degenerative case where the number of duplicate sets is 1 and the size of that set is 1. Consider row 2 on the puzzle in figure 2. Consider the set {1}. This is the set of candidate numbers for the cell at row 2 column 5 – this is a set of one number (cardinality = 1). How many duplicates of this set, {1}, appears on row 2? Only once. Therefore, using rule #1, we can eliminate all 1’s from all non-duplicate sets on row 2, i.e. “1” will not be a candidate number for row 2 column 1-4 and 6-9. If so, “1” would appear more than once on row 2, violating the rule for Sudoku puzzle. Consider figure 3, a block of a Sudoku puzzle. Figure 3. Except of a Sudoku Puzzle. Consider the set {1,2}. This is the set of candidate numbers for the cell at row 1, column 1. The cardinality of this set is 2 (there are two numbers in this set). Within this block, are there any duplicates of this set? Yes, on row 3, column 2. In total, there are two duplicates of the set {1,2} on this block. Therefore, using rule #1, we can eliminate all 1’s and 2’s from all non-duplicate cells on this block (on figure 3), i.e. all cells except row 1, column 1 and row 3, column 2. Rule 2: The second rule looks at each cell within a group and throws away all items that appear in other cells in the group. If we are left with only one value in the chosen cell, then it must appear in this cell and the cell may be updated by throwing away all other values that appear in the chosen cell. Applying this rule to the fifth row in following figure (figure 4) results in the fourth column being reduced to containing a 1 because 1 does not appear in any other cell in the 5th row. This rule also applies in the last row of the puzzle where 2 is only possible in the second column after removing 1, 5 and 6 from that cell because they appear within other cells in that row. Figure 4. A Sudoku Puzzle. (Adapted from Lee et al. Figure 5.3) Cells with multiple numbers represent candidates numbers for that cell. Specification Please clone the GitHub repo:- I will send the code file Please finish the implementation of the following class: · SudokuSolver.java: please finish the implementation of the following two methods corresponding to the two rules for solving Sudoku puzzle described above: · private boolean rule1(ArrayList<>
> group) · private boolean rule2(ArrayList<>> group) SudokuTestDriver.java provides codes to test drive your SudokuSolver. It reads in a number of Sudoku puzzles (located at folder: test\resources) and pass them to your SudokuSolver to solve. It verifies whether the puzzle is indeed solved. Deliverables SudokuSolver.java Please put your name and student number on the top comment section of the file. Please submit your completed source code files Marking Scheme Codes free of compilation error (20%) SudokuSolver.java (total: 80%) · Implementation of rule1() – 40% · Implementation of rule2() – 40% B Implementation of TreeSet Purpose Provide implementation for the java.util.Set interface using Tree. Specification Provide your own implementation of TreeSet. As the name of the class implies, you must use an underlying tree to provide implementation of the java.util.Set interface. You will need to do so ONLY with user defined objects and primitive data types, nothing from Java libraries. Also, you must base your codes off of the binary search tree implementation from assignment #3. You do not need to implement all methods. The only methods needed are as follows: (Methods from java.util.Set) Please refer to: https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Set.html Modifier and Type Method Description boolean add(E e) Adds the specified element to this set if it is not already present. boolean addAll(Collection c) Adds all of the elements in the specified collection to this set if they're not already present. void clear() Removes all of the elements from this set (optional operation). boolean contains(Object o) Returns true if this set contains the specified element. boolean containsAll(Collection c) Returns true if this set contains all of the elements of the specified collection. boolean equals(Object o) Compares the specified object with this set for equality. boolean isEmpty() Returns true if this set contains no elements. Iterator iterator() Returns an iterator over the elements in this set. boolean remove(Object o) Removes the specified element from this set if it is present (optional operation). boolean removeAll(Collection c) Removes from this set all of its elements that are contained in the specified collection (optional operation). boolean retainAll(Collection c) Retains only the elements in this set that are contained in the specified collection (optional operation). int size() Returns the number of elements in this set (its cardinality). Object[] toArray() Returns an array containing all of the elements in this set. T[] toArray(T[] a) Returns an array containing all of the elements in this set; the runtime type of the returned array is that of the specified array. Note: for Iterator, only need to provide implementation for hasNext(), next() and remove(). Deliverables Source files - up to you as to the number of source files (classes) Marking Scheme Codes free of compilation error – 10% Codes’ comments according to Javadoc (please see reference such as: baeldung.com/Javadoc) – 10% A readme file with instruction on usage – 5% 1