Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Coxeter formula to build Magic Squares (odd sizes)
// t12e14.coxeter.cpp
// juanfc 2022-01-22
// juanfc 26/1/02, 2006-12-14, 2019-01-10
//
//
// magicsquareSTL.cpp
// https://gist.github.com/9273b8a29955e043d26596b440e9b756
// \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 test(int n);
int main()
{
for (int i = 3; i < 16; i+=2)
test(i);
return 0;
}
void magicSquare (TSqMat &a, int N);
void test(int n)
{
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;
}
}
void magicSquare (TSqMat &a, 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment