Develop and implement a stack-based Sudoku puzzle solver. Details You are most likely familiar with the Sudoku puzzle game. It consists of a 9-by-9 grid; initially, some of the positions are filled with numbers and others are blank. When solved, each row must have all of the integers 1 - 9, each column must have all of the integers 19 and each of the nine 3-by-3 blocks must have all of the integers 1 - 9 . One method to solve a Sudoku puzzle is trial-and-error. If a valid guess can be made, make it and repeat. If no valid guess can be made, go back to the previous guess and change it; if no other guesses can be made, go back to the guess before that. Continue until either all boxes are filled or all guesses are exhausted (which shouldn't happen because that means there is no solution.) Create a stack of integers which represent the location of cells being filled in. The top location on the stack represents the cell currently being filled in. Note that there will be at most 64 locations to track, since any Sudoku puzzle must have at least 17 cells filled in initially. Note: If you're clever, you only need one integer to represent the location, not two. Read the data from cin. Input consists of nine lines of nine characters. If a cell is filled in, its character will be a digit 1 - 9 . If it is blank, its character is a period. Pro tip: You only need a single char variable for the input; no strings necessary. Once the data is read, use the following algorithm to solve the puzzle. DKeeping track of choices You should use bit manipulation to keep track of information for each cell. All of the information for one cell can be kept in 14 bits: - One bit to indicate if the cell has been filled in - Nine bits to keep track of which digits you are allowed to place in the cell - Four bits to hold the current choice for the cell Although it's not strictly necessary, you can fit all of the information into the short int data type. You'll want to use the masking operations at various points in the program to turn bits on and turn them off. You'll also want to use the left shift operation to look at the valid choices for a cell. Selecting the best empty cell Hypothetically, you can pick any empty cell for your next choice. However, to minimize the work the computer performs in backtracking, there is a preferred cell. The best cell to choose has the fewest valid choices for its digit. The following algorithm selects the best empty cell and places its location on the stack. Algorithm 2 Finding the best empty cell Preconditions board contains an unsolved Sudoku puzzle Postconditions the best location is pushed onto the stack the best location is marked as filled in What to turn in Turn in your source code and Makefi le. If you are using an IDE, compress the folder containing the project and submit that. sInput 4....... .2.7.59. .98.437 ..1.2..7. .53.49. .8.9.2 798.12. .527.3. 8..7 - Output Solution: 476259381 123768594 598143762 931825476 265374918 784691253 347986125 652417839 819532647 Example 2 DInput 47... .36 8...4 ... 1 2.4 .2548. 1.3.7 21...48 .9.3.2.7. - Output Solution: 361827954 472195836 859643721 786234519 925716483 143958267 217569348 538471692 694382175 Example 3 DInput42393.27.6.9.3.54486.9.92617.9..41.6345 - Output Solution: 754238169 391654278 682917543 863129754 427586391 519473826 148795632 935862417 276341985 Example 4 blnput 1.....9 9 .5.86. .9.8.4 43..81 6... ...1 ..65..43 5.6.3 .78.3. 2.7 - Output Solution: 148276359 759843162 362195874 437981625 695324781 821657943 516732498 974518236 283469517