MAGIC SQUARES C++

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 third 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.

In a loop over all potential candidates,

Drop in a candidate.

Make a recursive call to solvePuzzle() with the updated puzzle.

Got back a true? Return true.

Otherwise, continue the loop (try the next candidate and make another recursive call)

Completed the loop? None of them worked. Reset the candidate cell to blank and return false.

MAGIC SQUARES

A normal Magic Square of dimensionality n contains the numbers 1 through n² 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 ( n² + 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
  • If there are multiple solutions, stop at the first one found
• Create the corresponding Magic Square using the recursive algorithm given
• Display the solved puzzle, or an appropriate message if no solution is found

The entries in the file will be base-10 integers.

Display the result using only base-10 numbers.

EXTRA CREDIT:

Modify your program to search for all possible Magic Squares (based on the given input file) and display the number of solutions found.

DELIVERABLES:

Your C++ source code and a screen shot of your code in action.

NOTES:

For the 3x3 input file (an empty magic square)

0 0 0

0 0 0

0 0 0

Your program should find the first solution

2 7 6

9 5 1

4 3 8

in less than a second.

The extra credit count code should find eight solutions.

They are all reflections and rotations of the pattern above.

For the 3x3 input file

8 0 0

0 0 0

0 0 0

Your program should find the first solution (which is also given on the previous page)

8 1 6

3 5 7

4 9 2

in less than a second. If you run the extra credit count code on this input file, the answer is 2.

For the 5x5 input file

11 10 4 23 17

18 12 6 5 24

25 0 0 0 0

0 0 0 0 0

0 0 0 0 0

Your program should find the first solution

11 10 4 23 17

18 12 6 5 24

25 7 19 1 13

8 21 20 14 2

3 15 16 22 9

in a couple of seconds.