IE523: Financial ComputingFall, 2019Programming Assignment 2: Sudoku Solver viaExhaustive-Search using RecursionDue Date: 13 September, 2019c©Prof. R.S. SreenivasA Sudoku Puzzle consists of a 9× 9 grid, that is subdivided into nine 3× 3blocks. Each entry in the grid must be filled with a number from {1, 2, . . . , 9},where some entries are already filled in. The constraints are that every numbershould occur exactly once in each row, each column, and each 3× 3 block.Write a C++ program that takes the initial board position as input andpresents the solved puzzle as the output. Your program is to take the nameof the input file as a command-line input, print out the initial- and final-boardpositions (cf. figure 4 for an illustration). The input file is formatted as followsFigure 1: Sample output.– there are 9 rows and 9 numbers, where the number 0 represents the unfilled-value in the initial board. Figure 2 contains an illustrative sample.The approach you will take for this assignment is to use recursion to imple-ment an exhaustive-search procedure that solves a Sudoku puzzle. That is, youstart with the first unfilled-value in the board and pick a valid assignment thatsatisfies the row-, column- and block-constraints identified above. Followingthis, you move to the next unfilled position and do the same. If at some pointin this process you reach a partially-filled board-position that cannot be filled19 0 0 7 0 3 5 0 40 0 0 0 0 0 6 7 00 0 6 4 5 0 8 0 00 1 5 2 0 0 0 6 30 0 0 5 0 6 0 0 06 7 0 0 0 9 4 5 00 0 8 0 4 7 2 0 00 4 7 0 0 0 0 0 03 0 9 1 0 8 0 0 5Figure 2: Sample input file called input, which was used in the illustrativeexample of figure 4. The 0’s represent the incomplete board positions/values.further under the three constraints, you backtrack to the last assignment thatwas made before you got stuck and modify the assigned value accordingly. Thiscan be implemented using recursion as follows:Boolean Solve(row, column)1: Find an i ≥ row and j ≥ column such that puzzle[i][j] = 0. If you cannotfind such an i and j, then you have solved the puzzle.2: for k ∈ {1, 2, . . . , 9} do3: puzzle[i][j] = k.4: if Row-, Column- and Block-Assignment constraints are satisfied by theabove assignment, and Solve(i, j) returns true then5: Return true.6: end if7: end for{ /* If we got here then all assignments made to puzzle[i][j] are invalid. So,we reset its value and return false*/}.8: puzzle[i][j] = 09: Return false.Figure 3: Pseudo-code for the recursive implementation of the exhaustive-searchalgorithm for the Sudoku puzzle. You solve the puzzle by calling Solve(0,0),assuming the indices are in the range {0, 1, . . . , 8}.First Part of the AssignmentYour implementation should use a class Sudoku with appropriately defined pri-vate and public functions that1. check if the row-, column- and block-assignment constraints are met,22. reads the incomplete puzzle from an input file that is read at the command-line,3. prints the puzzle at any point of the search.along with a recursive procedure that solves the puzzle that was introducedabove.Second Part of the AssignmentThe following blog mentions Sudoku puzzles that can have multiple solutions.I want you to modify your code from the second programming assignment tofind all solutions to a Sudoku puzzle.You definitely want to be cautious with this – the empty Sudoku puzzlehas theoretically 6,670,903,752,021,072,936,960 solutions. The last thing youwant to do is to attempt to print them out! You will find four input files onCompass that identifies four different Sudoku puzzles. Two of them have justone solution, while the other two have multiple solutions. I suggest you runyour code on these input files.Write a C++ program that takes the initial board position as input andpresents all solutions the puzzle as the output. Your program is to take thename of the input file as a command-line input, print out the initial- and final-board positions (cf. figure 4 for an illustration). The input file format is exactlythe same as what was used for the second programming assignment.The approach you will take for this assignment is to use recursion to modifythe exhaustive-search procedure that solved the Sudoku puzzle in the secondprogramming assignment. This is a relatively straightforward thing to do, ifyou have understood the recursion in the previous programming assignment.3Figure 4: Sample output.4
