[Solved] HW4 Leveraging Reuse with Adapters, Facades and Template Methods

In this assignment, you will build a Sudoku puzzle solver (not an interactive player) and in the process make use of Temple Method pattern and other appropriate patterns that we have studied to date.For information about the Sudoku game, look at https://en.wikipedia.org/wiki/Sudoku and other online resources about the game, its rules, and strategies for solving it.Functional Requirements1. The solver should accept as input: a) the name of file containing a puzzle and b) the name of an output file that will contain the results.1.1. The solver may have a Graphical User Interface, but doesnt need to. It could be a console application that accepted command-line arguments or provided the user with a simple consolebased user interface. Again the only require inputs are the name of the input file and output file.2. The solver must be able to solve puzzles of the following sizes: 44, 99, 1616, 2525, 3636.2.1. You do not need to consider puzzles that are not perfect squares.3. Your solver should be able to be able to solve all solvable puzzles and detected and report invalidpuzzles as such3.1. A puzzle is a valid Sudoku puzzle if it has one and only one answer3.2. A puzzle is invalid if it is a) not formatted corrected or is not a 44, 99, 1616, 2525, or3636, b) doesnt contain the right symbols, c) doesnt have a have a solution, or d) has morethan one solution.4. The input file will be a text file containing the grid size, n, on the first row, followed by rowcontaining the n different symbols that will be used in the puzzle. The each symbols must eventuallyappear in every row, column, or block. The 3rd to n+2 lines of the input file represent n rows thepuzzle, and each should contain n symbols or dashes. The dashes represent the places (i.e., cells)where the solver needs to figure out which symbol bellows there. Here are some examples:41 2 3 44 2 1 23 2 4 3161 2 3 4 5 6 7 8 9 A B C D E F G4 9 1 3 6 7 8 D 6 3 5 9 A 5 2 9 3 6 4 B 2 3 1 4 7 4 2 1 F 1 6 4 8 2 1 8 6 9 2 5 4 5 1 8 3 D 2 3 9 4 8 7 4 9 1 3 6 7 8 D 6 3 5 9 A 5 2 9 3 6 4 B 2 3 1 4 7 4 2 1 F 1 6 4 8 2 1 8 6 9 2 5 5. The solver must write its results to the specific output file.5.1. If a puzzle is solvable with one and only one solution, then solver save the solution into theoutput text file, using in the same format described for the input file, but with all of the dashesreplaced by their correct symbols. For example, the output for the first puzzle shown abovewould be as follows:41 2 3 44 2 3 11 3 4 23 1 2 42 4 1 35.2. If the puzzle is not formatted correctly. The solver should output the original puzzle, followedby the line with the word Bad Puzzle.5.3. If the puzzle is not solvable. The solver should output the original puzzle, followed by the linewith the word Unsolvable.5.4. If the puzzle has multiple solutions. The solver should output the original puzzle, followed bythe line with the word Multiple Solutions, and then each solution (including size row andsymbol rows)InstructionsTo build this system, you will need to do the following:1. Research different techniques for determining blank (dash) cells in a puzzle. Well call thesetechniques cell-solution algorithms.2. Spend some time modeling Sudoku puzzles from a structural perspective. For example, you couldthink about it as simple n x n array. Or, you could think about as rows, columns, and blocks, each ofwhich contain n cells and where each cell is in exactly 1 row, 1 column, and 1 block. Or, you couldthink about them in term of some other data structure. Note that how you choose to think aboutthe puzzle will have a direct impact on what cell-solution algorithms you can envision. With this kind of program, how think object structure directly constrains how you solve problems. Dont hesitate to experience with multiple structures.3. After settling on an object structure, try to find at least three such cell-solution algorithms.Depending on how you break the up or classify them, you may have many more.4. Determine the steps in each algorithm5. Generalize the steps so you can extract a common template for all of the algorithms, this will become your template method.6. Design the rest of your system.6.1. Feel free to use other patterns, but do not use a pattern without good justification. The emphasis will be on appropriate application and not blind or forced use. Hint: the template method and strategy patterns often work well together.7. Implement your solver based on your design. Your implementation will be evaluate based on yourdesign.8. Test all non-GUI components using thorough executable test cases.9. Test the system against the functional requirements, using test cases provided by the instructor andyour own test cases.10. Pay attention to performance. Think about how you can make your performance faster, withoutcomprising design principles.