MAGIC SQUARES Backtracking and Recursion Pretty much any numeric puzzle can be solved with two Boolean methods: isCompletePuzzle() // returns true if every spot in the puzzle has a value, false otherwise isValidPuzzle() // returns true if the puzzle contains no counterexamples, false otherwise The solution strategy is implemented in a fourth method solvePuzzle() which executes the following recursive algorithm: // base cases Is the puzzle valid? If not, return false. Is the puzzle complete? If so, return true (valid and complete!) // current candidate is valid and incomplete, so we have a recursive case Locate the first blank space in the puzzle. Drop in a candidate. Make a recursive call to solvePuzzle() with the updated puzzle. Got back a true? Return true. Got back a false? Try the next candidate and make another recursive call. No next candidate? Reset the candidate cell to blank and return false. MAGIC SQUARES A normal Magic Square of dimensionality n contains the numbers 1 through n2 ordered in such a way that the sum of each row, each column, and each diagonal is the same value. The magic constant for such a square is computed as M = n ( n2 + 1) For example, here is a magic square of order 3. 8 1 6 3 5 7 4 9 2 The constant is ( 3 ) ( 9 + 1 ) = 15. HOMEWORK: Magic Square Solver Write a C++ program that performs the following tasks: Display a friendly greeting to the user Prompt the user for a filename (if the file wasnt provided on the command line) Accept that filename Attempt to open the file Read the numbers in that file Determine the dimensionality of the puzzle (guaranteed to be a perfect square) Create a square two-dimensional array containing these values Create the Magic Square using the recursive algorithm given Display the solved puzzle, or an appropriate message if no solution is found Display the result using only base-10 numbers. "advance c++"