HW4 – Leveraging Reuse with Adapters, Facades and Template Methods Solved

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 Requirements
1. 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 doesn’t 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: 4x4, 9x9, 16x16, 25x25, 36x36.
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 invalid
puzzles as such
3.1. A puzzle is a “valid” Sudoku puzzle if it has one and only one answer
3.2. A puzzle is “invalid” if it is a) not formatted corrected or is not a 4x4, 9x9, 16x16, 25x25, or
36x36, b) doesn’t contain the right symbols, c) doesn’t have a have a solution, or d) has more
than one solution.
4. The input file will be a text file containing the grid size, n, on the first row, followed by row
containing the n different symbols that will be used in the puzzle. The each symbols must eventually
appear in every row, column, or block. The 3rd to n+2 lines of the input file represent n rows the
puzzle, 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:
4
1 2 3 4
4 2 - 1
- - - 2
3 - 2 -
- 4 - 3
16
1 2 3 4 5 6 7 8 9 A B C D E F G
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 - - - - - - -
- 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 the
output text file, using in the same format described for the input file, but with all of the dashes
replaced by their correct symbols. For example, the output for the first puzzle shown above
would be as follows:
4
1 2 3 4
4 2 3 1
1 3 4 2
3 1 2 4
2 4 1 3
5.2. If the puzzle is not formatted correctly. The solver should output the original puzzle, followed
by 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 line
with the word “Unsolvable”.
5.4. If the puzzle has multiple solutions. The solver should output the original puzzle, followed by
the line with the word “Multiple Solutions”, and then each solution (including size row and
symbol rows)
Instructions
To build this system, you will need to do the following:
1. Research different techniques for determining blank (dash) cells in a puzzle. We’ll call these
techniques “cell-solution algorithms”.
2. Spend some time modeling Sudoku puzzles from a structural perspective. For example, you could
think about it as simple n x n array. Or, you could think about as rows, columns, and blocks, each of
which contain n cells and where each cell is in exactly 1 row, 1 column, and 1 block. Or, you could
think about them in term of some other data structure. Note that how you choose to think about
the 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. Don’t 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 algorithm
5. 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 your
design.
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 and
your own test cases.
10. Pay attention to performance. Think about how you can make your performance faster, without
comprising design principles.