Assignment Purpose and OverviewThe purpose of this assignment is to implement a Sudoku(https://en.wikipedia.org/wiki/Sudoku) puzzle solver program. The puzzle can be representedas a 9×9 grid as illustrated below.2 7 14 79 1 2 4 8 54 5 72 6 1 37 3 21 8 9 6 5 72 99 1 6As it can be observed, some numbers are provided while some numbers are missing.The objective is to fill the missing numbers in such a way that the following constraints are met:• Row constraint: each row contains all of the numbers from 1 to 9• Column constraint: each column contains all of the numbers from 1 to 9• Block constraint: each of the nine 3×3 blocks, which compose the grid, contain all ofthe numbers from 1 to 9.A well-posed puzzle, such as the one illustrated before, has a single solution. For example, theonly solution for the puzzle is illustrated below; the red numbers are the ones that should bediscovered by the solver.5 8 2 3 7 9 1 6 46 4 3 1 8 5 9 7 29 7 1 2 6 4 8 3 53 1 4 6 5 2 7 8 92 6 5 8 9 7 4 1 38 9 7 4 3 1 2 5 61 3 8 9 2 6 5 4 77 2 6 5 4 8 3 9 14 5 9 7 1 3 6 2 8For the purposes of this assignment, in order to allow the solver to load puzzles, the puzzles willbe stored in text files in the format presented below, where:• the first number indicates the number of rows of the puzzle• the second number indicates the number of columns of the puzzle• the remaining 81 numbers, presented as 9 rows of 9 columns each, represent theinitially provided puzzle numbers and the missing positions, the latter represented as 0990 0 2 0 7 0 1 0 00 4 0 0 0 0 0 7 09 0 1 2 0 4 8 0 50 0 4 0 5 0 7 0 02 6 0 0 0 0 0 1 30 0 7 0 3 0 2 0 01 0 8 9 0 6 5 0 70 2 0 0 0 0 0 9 00 0 9 0 1 0 6 0 0The solver program must investigate if there is a solution to the puzzle, and if there is, it needsto print it to the console, accompanied by the number of steps it required to perform to reachthe solution.Overall, in this assignment, you will:• Evaluate different data structures for storing Sudoku puzzles and their solutions• Implement efficient data structures for storing and manipulating Sudoku puzzles and theirsolutions• Design an algorithm that solves Sudoku puzzles using backtracking• Design and implement appropriate data structures for supporting the algorithm’sbacktracking operation• Develop a program that implements the algorithm which solves Sudoku puzzles usingbacktrackingAssignment Requirements and ConstraintsThe assignment must start by defining efficient data structuresto load a Sudoku puzzle. To thatend, you will define the SudokuPuzzle data structure and will use a function to initialize aninstance of the data structure accordingly. In particular, the SudokuPuzzle data structure mustbe able to preserve the following important information about a Sudoku puzzle:• number of rows and columns in the puzzle• the Sudoku puzzle numbers in a two-dimensional array• the positions of the initially provided puzzle numbers in order to prevent programs fromchanging them. This must be implemented as a two-dimensional bool array named locked• the number of missing numbers in the puzzle• the start position for solving the puzzle (i.e., the position of the first 0)• the last missing element position of the puzzle (i.e., the position of the last 0)To facilitate our description, the following figure presents an example input file and what needsto be saved according to the above specification:In the above example, the number of missing numbers is 49, the first and last missing numbersare located at positions (0,0) and (8,8) respectively. As soon as the file is loaded, you shouldprint this information on the console in the following format:+-----------------+|0|0|2|0|7|0|1|0|0||0|4|0|0|0|0|0|7|0||9|0|1|2|0|4|8|0|5||0|0|4|0|5|0|7|0|0||2|6|0|0|0|0|0|1|3||0|0|7|0|3|0|2|0|0||1|0|8|9|0|6|5|0|7||0|2|0|0|0|0|0|9|0||0|0|9|0|1|0|6|0|0|+-----------------+Number of missing numbers: 49First missing number: (0,0)Last missing number: (8,8)The signature of the loading function must be the following:SudokuPuzzle* loadPuzzle(string filename)A number of puzzles are provided in Appendix 1 for you to test your implementation.Number of rowsTwo-dimensionalarray representing aSudoku PuzzleNumber of columnsFirst empty number; the startposition of the puzzleLast missing number; thefinish position of the puzzleThe program should then proceed to solve the puzzle. The algorithm will employ a backtrackingapproach according to the following high-level concept:• Test if a missing number cell can accept a valid number in the range of 1-9• If a valid number has been found, then proceed to the next missing number• Otherwise, you have reached a dead end and you need to backtrackTo facilitate our description, we provide an example based on the input file described above.The algorithm starts by setting up the missing numbers one by one reaching the followingintermediate state:+-----------------+|3|5|2|6|7|8|1|4|9||6|4|0|0|0|0|0|7|0||9|0|1|2|0|4|8|0|5||0|0|4|0|5|0|7|0|0||2|6|0|0|0|0|0|1|3||0|0|7|0|3|0|2|0|0||1|0|8|9|0|6|5|0|7||0|2|0|0|0|0|0|9|0||0|0|9|0|1|0|6|0|0|+-----------------+The next missing number to be completed is located at position (1,2) and is highlighted withbold red font in the above figure. As it can be calculated, there is no valid number to enter forthat missing position, so the program must backtrack to the previous correct state and try adifferent route.It is compulsory that you implement a Stack data structure to enable the backtrackingfunctionality. The Stack data structure must be designed using generic programming techniquesand should implement the following functions:• isEmpty: checks if the stack is empty• push: inserts an element to the top of the stack• pop: removes an element from the top of the stack, if it exists, without returning it• top: returns the element located on the top of the stack, if it existsAs soon as the program finishes, if a solution is found, you should print this information on theconsole in the following format:Solution found in 1517 steps!+-----------------+|5|8|2|3|7|9|1|6|4||6|4|3|1|8|5|9|7|2||9|7|1|2|6|4|8|3|5||3|1|4|6|5|2|7|8|9||2|6|5|8|9|7|4|1|3||8|9|7|4|3|1|2|5|6||1|3|8|9|2|6|5|4|7||7|2|6|5|4|8|3|9|1||4|5|9|7|1|3|6|2|8|+-----------------+IMPORTANT: The program must satisfy all the requirements and constraints described in thissection. However, the requirements may not be sufficiently defined. During the specifications,you will need to record your assumptions and how these have influenced your models.DeliverablesFor part A, the deliverable consists of a compressed folder, named as“202021.CO1406..zip” (e.g., 202021.CO1406.G1234567.zip), with the followingfiles:1. 1x Document (Microsoft Word format) consisting of the documentation of parts A-D2. 1x compressed file (.zip) including your source code (C++ Header files (.h) developed forpart B and C++ Source files (.cpp) developed for parts C and D) and any resources (e.g.,the puzzle files) used in your implementation.Grading CriteriaMarks will be awarded based on the following criteria. Within each part, aim to complete thework for each section before moving on to the next as you will not get the full credit for latersections if there are significant defects in an earlier section. However, do not simply stop if youare stuck on one part, ask for feedback.In assessing the work within a section, factors such as simplicity, quality and appropriateness ofcomments, and quality and completeness of the design will be considered.Part Description Range DeliverableA Documentation 0-10 • Documentation in Microsoft Word (.docx) formatB Data Structures 0-20• C++ code for supporting data structures requiredfor backtracking• C++ code for loading and manipulating Sudokuproblems and solutionsC Algorithm 0-20 • C++ code for solving Sudoku puzzles usingbacktrackingD Program 0-10 • C++ code using the deliverables of parts B and C toload and solve Sudoku puzzlesDetailed Marking SchemePart Description CriteriaA Documentation0-4 Requirements Analysis• 0 - no attempt or Fail• 1 - Requirements are poorly described• 2 - Requirements are sufficiently described. Developsrequirements for a decent solution• 3 - Provides evidence of investigative skills in problemanalysis to develop requirements for an efficient solution• 4 - Identifies several potential solutions and justifies theselection of the most efficient solution.0-4 Complexity Analysis• 0 - no attempt or Fail• 1-4 Evaluates the time complexity of the loadPuzzle andsolvePuzzle functions correctly0-2 Source code Documentation• 1 - Function comments, which describe the functionality of amethod/field before the function definition• 1 - Inline comments, which describe implementationdecisions within a method bodyB Data Structures0-2 Implementation of the Coordinates data structurerepresenting a position in the puzzle.0-8 Implementation of the SudokuPuzzle data structurerepresenting a Sudoku puzzle. Implements appropriate membersfor storing:• 1 - number of rows and columns in the puzzle• 2 - the Sudoku puzzle numbers in a two-dimensional array• 2 - the positions of the initially provided puzzle numbers inorder to prevent programs from changing them. This mustbe implemented as a two-dimensional bool array namedlocked• 1 - the number of missing numbers in the puzzle• 1 - the start position for solving the puzzle• 1 - the last missing element position of the puzzle0-4 Implementation of the SudokuSolver data structurerepresenting a Sudoku solution. Implements appropriatemembers for storing:• 1 - A Sudoku problem as this was defined above• 2 - the final solution• 1 - the number of steps required by the solver to solve thesolution0-4 Implementation of a Stack data structure for storing moves(i.e., positions) during backtracking• 1 - Development of an appropriate push method• 1 - Development of an appropriate pop method• 1 - Development of an appropriate top method• 1 - Application of Generic programming0-2 Demonstration of selecting Storage Efficient data membersfor the data structures described above.• 0 - no attempt• 1 - Consideration of trivial or infeasible alternatives• 2 - Careful consideration of alternatives and justification ofselection of data member typesC Algorithm0-10 Helper Functions to support the backtracking algorithm• 2 – checks if assigning a number to a position does notviolate the Row Constraint• 2 – checks if assigning a number to a position does notviolate the Column Constraint• 2 – checks if assigning a number to a position does notviolate the Block Constraint• 2 – retrieves the next position after a successful assignmentof a number to a position• 2 – prints a Sudoku puzzle in the format described before0-10 Backtracking Algorithm to solve Sudoku problems• 8 – utilizes backtracking to find a correct solution to theproblem• 2 – prints the solution when there is one including thenumber of stepsD Program0-8 Puzzle Loading Function• 0-6 initializes a SudokuPuzzle data structure appropriately• 0-2 checks for inconsistencies/errors in the file0-2 Main function• 1 - Uses the loadPuzzle function to load a puzzle from a fileto a SudokuPuzzle data structure• 1 - Initializes a SudokuSolver data structure, loads theSudokuPuzzle and then invokes the solverSubmission of assignment work• Anonymous marking is being used. You may include on the work. Apart from your UniversityID number (“G2…”), avoid doing anything that would allow you to be identified from yourwork.• Keep a complete copy of the work you hand in.• Avoid submitting work at the last minute, but if there is a technical problem uploading to
Appendix 1Example file 1990 0 0 2 6 0 7 0 16 8 0 0 7 0 0 9 01 9 0 0 0 4 5 0 08 2 0 1 0 0 0 4 00 0 4 6 0 2 9 0 00 5 0 0 0 3 0 2 80 0 9 3 0 0 0 7 40 4 0 0 5 0 0 3 67 0 3 0 1 8 0 0 0Example file 2990 0 2 0 7 0 1 0 00 4 0 0 0 0 0 7 09 0 1 2 0 4 8 0 50 0 4 0 5 0 7 0 02 6 0 0 0 0 0 1 30 0 7 0 3 0 2 0 01 0 8 9 0 6 5 0 70 2 0 0 0 0 0 9 00 0 9 0 1 0 6 0 0Example file 3990 2 0 6 0 8 0 0 05 8 0 0 0 9 7 0 00 0 0 0 4 0 0 0 03 7 0 0 0 0 5 0 06 0 0 0 0 0 0 0 40 0 8 0 0 0 0 1 30 0 0 0 2 0 0 0 00 0 9 8 0 0 0 3 60 0 0 3 0 6 0 9 0Example file 4990 0 0 6 0 0 4 0 07 0 0 0 0 3 6 0 00 0 0 0 9 1 0 8 00 0 0 0 0 0 0 0 00 5 0 1 8 0 0 0 30 0 0 3 0 6 0 4 50 4 0 2 0 0 0 6 09 0 3 0 0 0 0 0 00 2 0 0 0 0 1 0 0Example file 5992 0 0 3 0 0 0 0 08 0 4 0 6 2 0 0 30 1 3 8 0 0 2 0 00 0 0 0 2 0 3 9 05 0 7 0 0 0 6 2 10 3 2 0 0 6 0 0 00 2 0 0 0 9 1 4 06 0 1 2 5 0 8 0 90 0 0 0 0 1 0 0 2