关于算法:CS-1027-用java实现2D数据算法

Assignment 1CS 1027Computer Science Fundamentals IIDue date: Thursday, October 5 at 11:55 pm

1. Learning Outcomes

In this assignment, you will get practice with:Creating classes and their methodsArrays and 2D array Conditionals and loopsWorking with objects that interact with one another Creating a subclass and using inheritance Programming according to specifications

2. Introduction

Sudoku is a popular number puzzle in which the numbers 1 through n have to be placed into ann by n grid of cells such that each row and column contains each of the n digits exactly onceeach. Most sudokus have n = 9 so the numbers 1 through 9 are placed into a 9 by 9 grid. In thispopular 9 digit sudoku, there is an additional rule that each 3 by 3 box must contain each of the9 digits exactly once. Sudokus generally have some given digits from which the solver shouldbe able to correctly complete the remaining cells using deduction and other strategies. A sudokumust have only one possible solution based on the given digits and to be valid it must follow allthe rules mentioned above. In Figure 1 below, the left image is an example of a valid sudokusolution. On the right side, the sudoku is invalid because there is a 7 in row 2 column 8(highlighted in yellow) which conflictswith the other 7s in its row, column, and box. All these 7sare shown in red text.Figure 1. An example of a valid 9×9 sudoku (left) and an invalid 9×9 sudoku (right).Assignment 1CS 1027Computer Science Fundamentals IIFigure 2. Depictions of a row (left), column (middle), and 3×3 box (right) in a valid 9×9 sudokuFigure 2 above shows examples of a valid row (left), column (middle), and 3×3 box in whicheach contains all the digits from 1 through 9 exactly once.
In recent years, variations of sudokus have emerged that combine the standard rules of sudokuwith additional rules or restrictions for the placement of digits in different parts of the grid. Onesuch variation is a unique diagonal sudoku in which the numbers along one or both of the maindiaginals (top left to bottom right OR bottom left to top right) must also contain each of the ndigits exactly once eachwithout repeating any. The regular rules of sudoku must still befollowed in addition to the new diagonal rule. The sudoku shown below in Figure 3 is anexample of a valid unique diagonal sudoku because it satisfies the rules of a regular sudokuand it has each of the digits 1 through 9 exactly once along its bottom-left to top-right diagonal.Figure 3. An example of a valid unique diagonal 9×9 sudoku.Assignment 1CS 1027
Computer Science Fundamentals IIFigure 4. An example of an invalid unique diagonal 9×9 sudoku. This is a valid regular sudoku(the numbers 1-9 are placed once each in each row, column, and 3×3 box) but does not have allunique numbers along either of its diagonals so it is not a valid Unique Diagonal sudoku.The sudoku shown in Figure 4 is not a valid unique diagonal sudoku. Although it is a validregular sudoku, it does not have all the digits 1 through 9 exactly once along either of itsdiagonals. The digits 2 and 7 are repeated along the bottom-left to top-right diagonal(highlighted in yellow). The other diagonal also contains repeated digits (not highlighted).For this assignment, we will be using a 2D (2-dimensional) int array torepresent the grid of aSudoku puzzle and implementingvariousmethods to check if a given sudoku is a valid solution
based on the rules explained above. We will also work with the unique diagonal variant ofsudoku and check its validity as well. The assignment does not involve solving sudoku puzzlesor making an interactive sudoku playing system.For simplicity, we use 0-based indexing for rows and columns in the sudoku. For example, inthe sudoku shown in Figure 4 above, we would say that the top-left corner cell (containing thedigit 9) is at row 0 column 0. The 4 in the cell adjacent to it is at row 0 column 1. The bottomright cell (containingthe digit 5) is at row 8 column 8.Assignment 1CS 1027Computer Science Fundamentals II

3.Classes to Implement

For this assignment, you must implement two (2) Java classes: Sudoku andUniqueDiagonalSudoku. Follow the guidelines for each one below.
In these classes, you may implement more private (helper) methods ifyou want. However, youmay not implement more public methods except public static void main(String[] args) for testingpurposes (this is allowed and encouraged).You may not add instance variables other than the ones specified in these instructions norchange the variable types or accessibility (i.e. making a variable public when it should be
private). Penalties will be applied if you implementadditionalinstance variables or change thevariable types or modifiers from what is described here.You may not import any Java libraries such as java.util.Arrays.Sudoku.javaThis class is used to represent a sudoku containing integers in a 2D array.The class must have exactly (no more and no less) the following private instance variables: private int size (this represents the size of the grid, assuming itwill always be a square) private int[][] grid (this is the grid containing all the digits)The class must have the following public methods: public Sudoku (int[][] numbers): constructoro Initialize the instance variables size and grid using the given parameter numbers.
o Note that grid must be copied as a shallow copy, meaning the sameobjectreference from the parameter numbers will be used for thisinstance variable grid

 public int getSize ()
o Return the size variable
 public int[][] getGrid ()
o Return the grid variable
 public int getDigitAt (int row, int col)
o Return the digit stored in the grid at the given row and col indices
o If either of the indices are out of range (i.e. less than 0 or larger than size-1),return -1public boolean isValidRow (int row)
o Determine if the row at index row in the sudoku is valid, i.e. that it contains all the digits from 1 through size (inclusive) exactly once each. Return true if it's valid, orfalse otherwise. If the row index is out of range, return false. public boolean isValidCol (int col)Assignment 1CS 1027Computer Science Fundamentals IIo Determine if the column at index col in the sudoku is valid, i.e. that it contains allthe digits from 1 through size (inclusive) exactly once each. Return true if it'svalid, or false otherwise. Ifthe col index is out of range, return false. public boolean isValidBox (int row, int col)o Determine if the 3x3 box whose top-left corner is at index row, col in the sudokuis valid, i.e. that it contains all the digits from 1 through 9 (inclusive) exactly onceeach. Return true if it's valid, or false otherwise. If the row or col indices are out ofrange, return false.o NOTE: this method will only be called for a 3x3 box in a 9-sized sudoku so itdoes not need to work for any other sized boxes public boolean isValidSolution ()o Determine if the entire sudoku is valid by calling isValidRow() and isValidCol() forevery row and column and ensuring they are all true. If the sudoku is size 9, youmust also call isValidBox for all nine 3x3 boxes (this is only needed for size 9sudokus) and ensure that they are all true as well. If all conditions are true, thenreturn true to indicate the entire sudoku is valid, or false if at least one conditionis not met.public boolean equals (Sudoku other)o Determine if the'this' sudoku is identical to the other Sudoku. To beidentical, thesize of each must be equal and the digits in the grid of each must all me equal inthe same positions. Return true if they are identical, or false otherwise. public String toString ()o Build and return a string containing all the digits in the grid with a single spaceafter each digit and a newline character (\n) at the end of each row (after thespace that follows the final digit in the row) so that the printed string looks like agridstructure.UniqueDiagonalSudoku.javaThis class is used to represent a sudoku in which the digits along one or both of the maindiagonals must all be unique (no repeats) to be considered a valid solution. Since this is aspecial type of sudoku, this class must inherit from the Sudoku class.

No new instance variables are needed in this class.The class must have the following public methods:

 public UniqueDiagonalSudoku (int[][] numbers): constructor
o Use super() to call the Sudoku constructor.
 public boolean isValidSolution ()
o This method is overriding the isValidSolution() method in the Sudoku classAssignment 1CS 1027Computer Science Fundamentals II
o The regular sudoku rules still apply for a UniqueDiagonalSudoku, so call theparent isValidSolution() to check that it follows the standard rules (hint: how canyou call the parent isValidSolution() method from inside the overridden one?)
o The additional rule is that one or both of the main diagonals (from top-left tobottom-right and from bottom-left to top-right) mustcontain all the digits from 1through size (inclusive) exactly once each.
o If both conditions are true (regular sudoku rules are followed and at least onediagonal contains all the valid digits once each without repeats), return true.Otherwise, return false.ProvidedfilesTestSudoku.java is a tester file to help check if your java classes are implementedcorrectly.Similar files will be incorporated into Gradescope's auto-grader. Additional tests will be run thatwill be hidden from you. Passing all the tests within the provided files does not necessarilymean that your code is correct in all cases.Marking NotesFunctional Specifications Does the program behave according to specifications? Does it produce the correct output and pass all tests? Are the classes implemented properly? Does the code run properly on Gradescope (even if it runs on Eclipse, it is up to you toensure it works on Gradescope to get the test marks) Does the program produce compilation or run-time errors on Gradescope?Does the program fail to follow the instructions (i.e. changing variable types, etc.)Non-Functional Specifications Are there commentsthroughout the code (Javadocs or other comments)Are the variables and methods given appropriate, meaningful names? Is the code clean and readable with proper indenting and white-space?Is the code consistent regarding formatting and naming conventions?Submission errors (i.e. missing files, too many files, etc.) will receive a penalty. Including a"package" line at the top of a file will receive a penalty.Assignment 1CS 1027Computer Science Fundamentals IIRemember you must do all the work on your own. Do not copy or even look at the work ofanother student. All submitted code will be run through similarity-detection software.

4.Submission

(due Thursday, October 5 at 11:55 pm)Assignments must be submitted to Gradescope, not on OWL. If you are new to this platform,see these instructions on submitting on Gradescope.Rules Please only submit the files specified below. Do not attach other files even if they were part of the assignment. Do not upload the .class files! Penalties will be applied for this. Submit the assignment on time. Late submissions will receive a penalty of 10% per day.Forgetting to submit is not a valid excuse for submitting late.Submissions must be done through Gradescope. If your code runs on