magic square

A square matrix of integers such that each row, column and diagonal have the same sum. Usually consecutive integers are used to fill in the square (of course you can start with any number). Famous historical magic squares have additional properties.

Here's a 3x3 example; each sum is 15.

  8 1 6
  3 5 7
  4 9 2

There's an algorithm for generating odd-order magic squares.

A simple puzzle played on the old Merlin handheld game units. The playing field is nine boxes in three rows of three, like a tic-tac-toe board. The game begins with small LED lights blinking in several of the nine spaces. The object is to create a "magic square" or ring, leaving the center box dark. This is done by observing the light patterns triggered when pressing each of the nine spaces. Find a correct sequence and voila - you've made a Magic Square!

a c c u s e
p r o p e l
h a n d e d
i n v a d e
d i e t e r
s a y e r s

Magic Squares might also be applied to words. I'd previously had some fun finding some four by four squares by hand, when, out of interest's sake, my friend and I coded a small program to find the silly things for us. We used a fairly standard Unix English dictionary, although I believe my friend added five or so *cough* choice four-letter words. The only rules we used were that each word had to be unique, taking the transpose (switching rows and columns) was cheating, and the diagonals didn't have to make sense. The square above was the only six by six square found.

Here's the breakdown of the number of squares per dimension:

Two by Two: 46
Three by Three: 10734
Four by Four: 148250
Five by Five: 4872
Six by Six: 1
Seven by Seven: 0
Eight by Eight and beyond: untested

There's a magic square described in the book Necroscope by Brian Lumley with some interesting properties and an interesting method of construction. It's so simple but so powerful the memory of this trick has stuck with me years after reading the book. This square also has some historical meaning.

Take a magic square, 4x4, and fill it in just by counting from 1-16:

 
      1   2   3   4

      5   6   7   8
  
      9  10  11  12

     13  14  15  16

Now the idea behind this method is to use a simple mechanism to achieve an equal distribution of the numbers. Take the diagonal, {1,6,11,16}, and flip it so it becomes {16,11,6,1}:

 
     16   2   3   4

      5  11   7   8
  
      9  10   6  12

     13  14  15   1

Now do the same to the {4,7,10,13} diagonal:

 
     16   2   3  13

      5  11  10   8
  
      9   7   6  12

      4  14  15   1

Each row, column and diagonal adds up to 34, but that's just like any other magic square. The cool thing about this one is that the following patterns also add up to 34:

 
     16   2   3  13      16  2   3  13

      5  11  10   8      5  11  10   8
  
      9   7   6  12      9   7   6  12

      4  14  15   1      4  14  15   1



     16   2   3  13      16  2   3  13

      5  11  10   8      5  11  10   8
  
      9   7   6  12      9   7   6  12

      4  14  15   1      4  14  15   1

Working with permutations of these patterns will also give you a sum of 34:

 
     16   2   3  13      16  2   3  13

      5  11  10   8      5  11  10   8
  
      9   7   6  12      9   7   6  12

      4  14  15   1      4  14  15   1

It's very easy to make a magic square if the length of a side is an odd number.

Step 1:

Draw out your square (I'm doing a 5x5 square):

 _ _ _ _ _
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|_|

Step 2:

Find the center space in the first row, and put the number '1' in it.

 _ _ _ _ _
|_|_|1|_|_|
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|_|

Step 3:

Finish filling in the square by moving up and to the right from the last number you added. If you go off the edge, then just wrap around.

 _ _ _ _ _
|_|_|1|_|_|
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|2|_|

When you get to a point where the next space is already filled, instead of going up and to the right, drop a row, and then continue.

 _ _ _ _ _
|_|_|1|_|_|
|_|5|_|_|_|
|4|6|_|_|_|
|_|_|_|_|3|
|_|_|_|2|_|

When you're finished, the magic square will work. Each row and column on a 5x5 equals 65.

 __ __ __ __ __
|17|24|1 |8 |15|
|23|5 |7 |14|16|
|4 |6 |13|20|22|
|10|12|19|21|3 |
|11|18|25|2 |9 |
 ¯¯ ¯¯ ¯¯ ¯¯ ¯¯

A method for generating 3x3 and 4x4 magic squares

Consider the magic square as a sum of component matrices:

     (1 1 1)    (1  -1 0)    (0  1 -1)
M = A(1 1 1) + B(-1 0  1) + C(-1 0  1)
     (1 1 1)    (0  1 -1)    (1  -1 0)

Choosing different values of A, B and C produces a magic square every time. Substituting A=5, B=3 and C=-1 yields ariels' magic square:

(8 1 6)
(3 5 7)
(4 9 2)

A 4x4 magic square can be generated in a similar way:

     (1 1 1 1)    (1 0 0 1)    (1 0 1 0)    (1 1 0 0)    (1 0 0 1)
M = A(1 1 1 1) + B(0 1 1 0) + C(0 1 0 1) + D(0 0 1 1) + E(1 0 0 1)
     (1 1 1 1)    (1 0 0 1)    (0 1 0 1)    (0 0 1 1)    (0 1 1 0)
     (1 1 1 1)    (0 1 1 0)    (1 0 1 0)    (1 1 0 0)    (0 1 1 0)

To generate the one mentioned by jerkass, substitute A=1, B=8, C=2, D=1, E=4. It is no coincidence that B, C, D and E are powers of 2 - the binary number system generates consecutive integers in this case.

For those of us who like to make the computer do all of our work, here is a C++ implementation of the algorithm explained by Eternal Shroud. This version also prints out the totals of each row, column, and diagonal (which are all the same by definition, but it was handy for debugging). It was tested with g++ 3.2.2.

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

class cMagicSquare {
private:
    int       **m_ippMagicSquare;
    const int m_iDim;
    int       m_iOtherDiagonal;
public:
    cMagicSquare(int iInput);
    ~cMagicSquare();
    void print() const;
};

cMagicSquare::cMagicSquare(int iInput):m_iDim(iInput) {
    int iCol, iRow;

    m_ippMagicSquare = new int *[m_iDim+1];
    for(int i = 0; i <= m_iDim; m_ippMagicSquare[i++] = new int[m_iDim+1]);

    for(iRow = 0; iRow <= m_iDim; iRow++)
        for(iCol = 0; iCol <= m_iDim; m_ippMagicSquare[iRow][iCol++] = 0);

    iRow = 1;
    iCol = m_iDim / 2 + 1;
    m_iOtherDiagonal = 0;

    for(int iValue = 1; iValue <= m_iDim * m_iDim; iValue++) {
        if(m_ippMagicSquare[iRow][iCol] > 0) {
            iRow += 2;
            if(iRow > m_iDim)
                iRow -= m_iDim;
            if(--iCol < 1)
                iCol = m_iDim;
        }

        m_ippMagicSquare[iRow][iCol] = iValue;

        m_ippMagicSquare[0][iCol] += iValue;
        m_ippMagicSquare[iRow][0] += iValue;

        if(iRow == iCol)
            m_ippMagicSquare[0][0] += iValue;
        if(iRow+iCol == m_iDim+1)
            m_iOtherDiagonal += iValue;

        if(--iRow < 1)
            iRow = m_iDim;
        if(++iCol > m_iDim)
            iCol = 1;
    }
}

cMagicSquare::~cMagicSquare() {
    for(int i = 0; i <= m_iDim; delete [] m_ippMagicSquare[i++]);
    delete [] m_ippMagicSquare;
}

void cMagicSquare::print() const {
    cout<<"\nThe number you selected was "<<m_iDim<<", and the matrix is:\n\n";

    int iCol, iRow;
    for(iRow = 1; iRow <= m_iDim; iRow++) {
        cout<<"     ";
        for(iCol = 1; iCol <= m_iDim; cout<<setw(5)<<m_ippMagicSquare[iRow][iCol++]);
        cout<<" = "<<setw(5)<<m_ippMagicSquare[iRow][0]<<"\n";
    }

    for(iCol = 0; iCol <= m_iDim; iCol++, cout<<"-----");
    cout<<"\n"<<setw(5)<<m_iOtherDiagonal;
    for(iCol = 1; iCol <= m_iDim; cout<<setw(5)<<m_ippMagicSquare[0][iCol++]);
    cout<<"   "<<setw(5)<<m_ippMagicSquare[0][0]<<endl;
}

int main() {
    cout<<"\nMagic Squares: This program produces an NxN matrix where\n"
          "N is some positive odd integer.  The matrix contains the\n"
          "values 1 to N*N.  The sum of each row, each column, and\n"
          "the two main diagonals are all equal.  Not only does this\n"
          "program produce the matrix, it also computes the totals for\n"
          "each row, column, and two main diagonals.\n\n"
          "Because of display constraints, this program can work with\n"
          "values up to 13 only.\n"<<endl;

    for(int iInput = 1; iInput != -1;) {
        cout<<"\nEnter a positive, odd integer (-1 to exit program): "<<flush;
        cin>>iInput;
        if(cin.good()) {
            if(iInput <= 0) {
                if(iInput != -1)
                    cerr<<"Sorry, but the integer has to be positive."<<endl;
            } else if(iInput % 2 == 0) {
                cerr<<"Sorry, but the integer has to be odd."<<endl;
            } else if(iInput > 13) {
                cerr<<"Sorry, but the integer has to be less than 14"<<endl;
            } else {
                cMagicSquare *mspMySquare = new cMagicSquare(iInput);
                mspMySquare->print();
                delete mspMySquare;
            }
        } else {
            cerr<<"Sorry, but a number must be entered."<<endl;
            cin.clear();
        }
        cin.ignore(100,'\n');
    }
    cout<<"\nBye bye!"<<endl;
    return 0;
}

---

Thanks to OldMiner for some efficiency modifications and help in editing this code so that it also works in Microsoft Visual C++ 6.0 (which doesn't handle variable scope correctly).
Thank you, node your homework!