At the end of this work you should submit a header file MagicSquare.h that defines all classes and declares all functions, a MagicSquare.cpp that implements those functions, and a Solve.cpp file with your main routine.

MAGIC SQUARE SOLVER

A magic square is an n n array of the numbers 1 through n 2 such that each number only appears once, and the sum of every row, every column, and both main diagonals is the same. You might remember solving these back in elementary school: teachers would do this to keep the students busy... and quiet. Heres an example of one below:

4 9 2

3 5 7

8 1 6

Note that the sums for each row: 4 + 9 + 2, 3 + 5 + 7, 8 + 1 + 6 are all 15... as are the sums for each column: 4 + 3 + 8, 9 + 5 + 1, 2 + 7 + 6... as are the sums for both diagonals: 4 + 5 + 6, 2 + 5 + 8.

In this homework, you will write the implementations to solve an n by n magic square where the user may, if they wish, enforce the placement of some numbers. You must use recursion in this assignment. This is the whole point of this exercise. Credit will not be given if you do not use recursion.

By having the numbers 1, 2, ..., n^2 in the board, it can be shown mathematically that the sum of all those entries is n^2 (n^2 + 1)/2. Since there are n rows (and columns) and the sum of each row (and column) is the same, the magical target sum is 1 of the total sum. In other words to be a magic square solution, every row, column, and diagonal must sum to:

S = n(n^2 + 1)/2.

The program should operate as follows:

Enter a square size: [USER ENTERS VALID SQUARE SIZE]

Enter square format: [USER ENTERS DATA ROW BY ROW WITH ENTRIES SEPARATED BY SPACES, ROWS SEPARATED BY [ENTER] AND WHERE * SIGNIFIES THE VALUE DOES NOT MATTER]

A list of all the solutions of the magic squares satisfying the users constraints is displayed. Solving complete!

There were [CORRECT NUMBER] of solutions!

The magic square will be stored as a std::vector where 0 indicates no value has been placed in the slot at a given row and column yet (recall the valid numbers are from 1 to n^2). You may wish to store it within a class.

You must write:

an overloaded operator>> to read from a stream into a std::vector that will properly process the users input (that vector need not start empty hint!);

an overloaded operator> with an output stream in the format demonstrated;

a function empty to check if a given position in the magic square is empty;

a function taken to check if a given number is already used in the magic square;

a function checkValid to check if a complete magic square satisfies the proper conditions to be a solution; and

a recursive function solveSquare that accepts an index tracking the number of slots already considered in the recursion (and maybe a std::vector also, depending on your implementation).

Here is the gist of solving the problem recursively: suppose that we look at the slots, possibly placing values within them, left-to-right, top-to-bottom, and that we have been through num slots already. Then:

if num is equal to the total number of slots, we should check if the magic square is a valid solution and if so, print it, and increase our count of valid solutions;

if not, then we should determine if the slot is empty (recall the user could specify values, too!) and if it is empty,

we should try every possible unused value in the current slot and try solving the magic square for each value we insert by repeating the process with num now num + 1;

and for each unused value that we placed in the magic square we should remove that value after placing it (in a similar spirit to the recursive process of generating permutations)

otherwise, we should skip over the current slot and try solving the magic square by looking at the next slot and replacing num by num + 1.

Important remark on speed: do not get your hopes up in solving big squares. The algorithm given could be sped up by checking if the row sum matches the value of S each time a row is filled, or that at no point does a row/column sum exceed S, etc. But even with these checks in place to speed up the code, solving a 44 square from scratch is very slow as there are still many cases to check and more than 800 solutions to find! Focus on 2 2 and 3 3 squares.

Some initial guidance to get you on your way...

1. It may be helpful to allow the value 0 to indicate that a slot is open. Recall that for a std::vector of a given size, this is the default value assigned to each element.

2. To write std::istream& operator>>(std::istream& in, std::vector>& init), your logic could depend upon the size of init.

3. Write your operator overloads first along. Be sure you can read from and write to the vector.

4. Your empty function may have signature bool empty(size t row, size t col, const std::vector>& check). The argument in italics may/may 6 not be needed, depending on whether you implement this as a free function or as a member function.

5. Your taken function may have signature bool taken(int i, const std::vector>& check). The argument in parentheses may/may not be needed, depending on whether you implement this as a free function or as a member function.

6. Write empty, taken, and checkValid next. You should test known magic squares as to whether they are solutions. Dont worry about solving them yourself yet, just use the examples in the display or come up with your own.

7. Finally, write solveSquare. The logic is given in the paragraph Here is the gist of solving... Note that if you have found a solution, you should print it with std::cout and invoke your counter function.

The diagram below may help show you the logic in finding no solutions to the 2 x 2 magic square where the user has specified the bottom-left corner is to be 4. 4 0 Valnes top lef 1 0 4 u 4 0 1 3 21 2 3 31 32 V -cterrs 1 2 Values botfh 1 2 4 3 13 21 2 3 3 4 1 3 4 2 43 41 No The diagram below may help show you the logic in finding no solutions to the 2 x 2 magic square where the user has specified the bottom-left corner is to be 4. 4 0 Valnes top lef 1 0 4 u 4 0 1 3 21 2 3 31 32 V -cterrs 1 2 Values botfh 1 2 4 3 13 21 2 3 3 4 1 3 4 2 43 41 No