Coxeter Magic Squares algorithm using STL arrays

magicsquareSTL.cpp

// magicsquareSTL.cpp
// juanfc 26/1/02, 2006-12-14, 2019-01-10
//
// \ej\label{magicsq}\dificil\dificil\textbf{Magic Squares}\\
// A \href{https://en.wikipedia.org/wiki/Magic_square}{magic square} is a
// \texttt{TSqMat} of $N\times N$ distinct integer numbers (i.e. each number
// used once), where the numbers in each row, and in each column, and the
// numbers in the main and secondary diagonals, all add up to the same number,
// a \emph{magic constant} (that magically is $ (n(n^2 + 1))/2$.
// A more general formula can be found
// \href{http://mathworld.wolfram.com/MagicSquare.html}{here}).\\
// \begin{minipage}{.85\linewidth}
// Except for the size $N=2$, there can be magic squares for any $N$.  A well
// known one (the oldest known, dating from 650 BC) is:
// \end{minipage}
// \begin{minipage}{.15\linewidth}
// \begin{code}
//   8 1 6
//   3 5 7
//   4 9 2
// \end{code}
// \end{minipage}
// \begin{minipage}{.8\linewidth}
// The next is as the previous one but with 19 added to each number:
// \end{minipage}
// \begin{minipage}{.15\linewidth}
// \begin{code}
// 23  28  21
// 22  24  26
// 27  20  25
// \end{code}
// \end{minipage}
// There is an algorithm able to build simple square matrices for odd $N$s by
// H. Coxeter:\\
// {\footnotesize
// \begin{minipage}{.8\linewidth}
// \begin{enumerate}
// \item Start in the middle of the upper row with 1.
// \item Go up and right assigning consecutive numbers to the empty cells.
// \item When crossing the matrix boundaries, reset the index(es) to go to the
// other side of the matrix as if it were repeated indefinitely \item toward
// the fourth directions.
// \item If a cell is already occupied, step down a cell and continue.
// \end{enumerate}
// \end{minipage}
// }
// \emptybox{0cm}{-1cm}{\includegraphics[width=2.5cm]{MagicSquareCoxeter.png}}

// Build \verb|void coxeter(TSqMat& magic);|
// Try with matrices of different odd sizes and print them.
//  For n=5:
//  15   8   1  24  17
//  16  14   7   5  23
//  22  20  13   6   4
//   3  21  19  12  10
//   9   2  25  18  11
//  magic value 65

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

const int NMAX = 50;
typedef array<array<int, NMAX>, NMAX> TSqMat;

void magicSquare (TSqMat &a, const int N);

int main()
{

    do {
        int n;
        cout << "Size? (odd number) [0 ends]: ";
        cin >> n;
        cin.ignore(1000, '\n');
        if (n == 0) break;
        if (n % 2 == 0 or n >= NMAX or n < 1) {
            cout << "Error: the size must be odd and between 1 and " << NMAX << endl;
        } else {
            TSqMat a;
            magicSquare(a, n);

            // draw it
            cout << endl << "Magic Square of size " << n;
            int s = 0;
            for (int i = 0; i < n; i++)
                s += a[i][0];
            cout << ". Sum: " << s << endl << endl;
            // here it goes
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    cout << setw(4) << a[i][j];
                cout << endl << endl;
            }
        } // if !exit
    } while (true);
    return 0;
}


void magicSquare (TSqMat &a, const int N)
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            a[i][j] = 0;

    int i, j;
    int key = 1;
    int NN = N * N;
    i = 0;
    j = (N - 1) / 2;
    a[i][j] = key++;  // half of first row
    while (key <= NN) {
        int ii, jj;  // temp place to look at
        if (i == 0)
            ii = N - 1;
        else
            ii = i - 1;
        if (j == 0)
            jj = N - 1;
        else
            jj = j - 1;

        if (a[ii][jj] != 0)
            i = (i + 1) % N; // already occupied
        else {               // ii, jj was free
            i = ii;
            j = jj;
        }
        a[i][j] = key++;
    } // while
} // magicSquare