A magic square is an NxN matrix that is filled with the numbers 1,2... N^2, with

Question

A magic square is an NxN matrix that is filled with the numbers 1,2... N^2, with the property that the sum of the numbers in each row, column, and in the two diagonals is the same value.
Besign an algorithm to construct magic NxN squares where N is an odd integer. Your program should accept the value N as input, and should reject even values of N with a suitable message. Your output must be an NxN magic Square.
Place 1 in the middle of the rightmost column. Now use the following seguence of steps: suppose the number K has been put into a square (r,c), put K+1 into the square to the right and above (r-1, c+1), wrapping around the borders. However, if you reach a quare that already has been filled or the top right corner, then you must more the square immediately tothe left in the same row (r, c-1), and continue trying to place k+1. Here is an example for N= 5
9 3 22 16 15
2 21 20 14 8
25 19 13 7 1
18 12 6 5 24
11 10 4 23 17

Explanation / Answer

#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
   //PROTOTYPES
   void getDimension(int &dimension);
   void printSquare(int **sqr, int dimension);
   void fillMagicSquare(int **sqr, int dimension);

   //LOCAL DECLARATIONS
   int dimension;
   int **sqr = 0;

   //Get dimension from user
   getDimension(dimension);
   cout << endl;

   //Allocate memory for the square
   sqr = new int*[dimension];
   for (int r = 0; r < dimension; r++)
      sqr[r] = new int[dimension];

   //Fill & print magic square
   fillMagicSquare(sqr, dimension);
   printSquare(sqr, dimension);

   //Free memory
   for (int r = 0; r < dimension; r++)
      delete [] sqr[r];
   delete [] sqr;

   //End
   cout << endl;
   cin.sync();
   cin.get();
   return 0;
}

//---------------------------------------------------------
// FUNCTION DEFINITIONS
//---------------------------------------------------------
void fillMagicSquare(int **sqr, int dimension)
{
   //Initialize the square
   for (int r = 0; r < dimension; r++)
      for (int c = 0; c < dimension; c++)
         sqr[r][c] = 0;

   //Begin filling the square
   int row = dimension / 2;
   int col = dimension - 1;
   sqr[row][col] = 1;
   for (int i = 2; i <= dimension * dimension; i++)
   {
      int nextRow = (row - 1 + dimension) % dimension;
      int nextCol = (col + 1) % dimension;
      if (sqr[nextRow][nextCol] || (row == 0 && col == dimension - 1))
         col--;
      else
      {
         row = nextRow;
         col = nextCol;
      }
      sqr[row][col] = i;
   }
}
//---------------------------------------------------------
void printSquare(int **sqr, int dimension)
{
   //Get print width
   int maxNumber = dimension * dimension;
   int digit = 0;
   while (maxNumber)
   {
      digit++;
      maxNumber /= 10;
   }

   //Print
   for (int r = 0; r < dimension; r++)
   {
      for (int c = 0; c < dimension; c++)
         cout << setw(digit + 1) << sqr[r][c];
      cout << endl;
   }
}
//---------------------------------------------------------
void getDimension(int &dimension)
{
   dimension = 0;
   while (dimension % 2 == 0)
   {
      cout << "Enter N: ";
      cin >> dimension;
      if (dimension % 2 == 0)
         cout << "N must be an odd number ";
   }
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.