Forum Discussion
Lambda Magic Square Generator: Adventures in Mapping and Optimization
Background
When I started this adventure, my research quickly found there are 3 types of magic squares:
Doubly even - n is even and divisible by 4.
Singly even - n is even but not divisible by 4.
Odd - n is an odd integer.
Further research found each of these types of magic squares had different ways to solve. I went in with the mindset of creating a function which would take n and apply the correct approach where needed.
MAP is used for each of the three approaches. Here are some top-level notes:
Doubly even - MAP is used once, an array of remaining integers is generated, and then some simple addition.
Odd - MAP is used twice - two full passes on the entire matrix.
Singly even - The matrix is split into 4 smaller matrices and then the odd method is applied.
Doubly even is easily the fastest and can return a magic square for n = 1024 in 2.42 seconds. Can you guess which is slowest of the two remaining approaches?
Averages taken from 5 timings for each. FullCalcTimer used.
Version 2409 (Build 18025.200006) - 64 bit.
| Integer | Order | Timing (seconds) |
| 3 | Odd | .017 |
| 4 | Doubly even | .014 |
| 6 | Singly Even | .015 |
| 100 | Doubly even | .043 |
| 101 | Odd | 1.912 |
| 102 | Singly even | 1.331 |
| 157 | Odd | 10.769 |
| 165 | Odd | 30.5 |
| 167 | Odd | 45.27 |
| 170 | Singly Even | 11.06 |
| 300 | Doubly even | 0.241406 |
| 1024 | Doubly even | 2.42 |
I think it is fascinating how much Odd struggles at 167 but Singly even at 170 can run in about 11 seconds because it's creating the magic square in smaller sub tasks. This reminded me of the BMap function being used to speed up REDUCE. It would be great to see an updated article from MS in re: calculation optimization for Excel 365. There's an in-depth article out there but it predates dynamic arrays.
I welcome any thoughts on optimization and MAP.
The function:
//Patrick2788 - 8/31/2024
//Introduction
//A magic square is a matrix of equal height and width of which all sums -
//horizontal, vertical, and both diagonals equal the magic sum.
//This module contains the necessary functions needed to create magic
//squares of odd, doubly even, and singly even orders.
//Details and References
//3 Types of magic squares:
//1. odd order - (e.g. 3, 5, 7....31, etc.)
//The function is inspired by Marios Mamzeris's approach.
//https://www.oddmagicsquares.com/
//2. doubly even order - (Even and divisible by 4)
//This is possibly the 'easiest' of all magic square algorithms. My approach
//utilizes the 3rd solution from https://www.1728.org/magicsq2.htm .
//3. singly even order - (Even but not divisible by 4 - e.g 10
//14, 18, 22, 26, 30, etc.) The most difficult (but not slowest) magic square order because the
//method of solving it is splitting a matrix into 4 smaller matrices of odd order and
//then running two 'oddly' passes on each to arrive at the solution.
// https://www.1728.org/magicsq3.htm
//The Functions
//Determine if a square array is a magic square by obtaining the sum for each row,
//column, and diagonal and checking it against the magic sum.
IsMagic = LAMBDA(square,
LET(
n, ROWS(square),
msum, n / 2 * (2 * 1 + (n ^ 2 - 1) * 1),
↑, SEQUENCE(n),
↓, SEQUENCE(n, , n, -1),
↘, SUM(INDEX(square, ↑, ↑)),
↙, SUM(INDEX(square, ↓, ↑)),
check, LAMBDA(e, SUM(e)),
check↕, BYCOL(square, check) = msum,
check↔, BYROW(square, check) = msum,
check↘↙, AND(↘ = msum, ↙ = msum),
HSTACK(msum, AND(check↕, check↔, check↘↙))
)
);
//This function determines the order of the integer and calls the
//appropriate function to generate the magic square.
Magic = LAMBDA(n, IF(MOD(n, 4) = 0, DoublyEven(n), Oddly_or_Singly(n)));
//Create magic squares from doubly even integers.
DoublyEven = LAMBDA(n,
LET(
M, SEQUENCE(n, n),
i, SEQUENCE(n) * SEQUENCE(, n, 1, 0),
j, WRAPROWS(TOCOL(i, , 1), n),
q, n / 4,
discard, LAMBDA(v, i, j,
LET(
crit, IF(q = 1, n, n - q + 1),
keep_interior, AND(
j >= q + 1,
j <= n - q,
OR(AND(i >= 1, i <= q), AND(i >= crit, i <= n))
),
keep_perimeter, AND(
i >= q + 1,
i <= n - q,
OR(AND(j >= 1, j <= q), AND(j >= crit, j <= n))
),
IF(OR(keep_interior, keep_perimeter), v, 0)
)
),
M_Zero, MAP(M, i, j, discard),
M_Remaining, WRAPROWS(
INDEX(TOCOL(M - M_Zero), SEQUENCE(n ^ 2, , n ^ 2, -1)),
n
),
M_Zero + M_Remaining
)
);
//This function will first determine if n is odd. If so, create a magic square
//of odd order. If singly even, split the matrix into 4 smaller matrices then
//solve for odd.
Oddly_or_Singly = LAMBDA(n,
LET(
k, IF(ISODD(n), n, n / 2),
w, ROUND(k / 2, 0),
M, SEQUENCE(n, n),
i, SEQUENCE(k) * SEQUENCE(, k, 1, 0),
j, WRAPROWS(TOCOL(i, , 1), k),
half, INT(k / 2),
quarts, INT(QUARTILE(M, {0; 1; 2; 3})),
Oddly_pass_1, LAMBDA(vector,
LAMBDA(v, i, j,
LET(
current_row, CHOOSEROWS(vector, i),
edge_a, k - i,
edge_b, k - i + 1,
a, SMALL(current_row, i + j),
b, SMALL(current_row, i + j - 1),
c, SMALL(current_row, j - edge_a),
d, SMALL(current_row, j - edge_b),
crit_a, (i < half + 1) * (j <= edge_a),
crit_b, (i > half) * (j <= edge_b),
crit_c, (i < half + 1) * (j > edge_a),
IF(
i = half + 1,
v,
IF(crit_a, a, IF(crit_b, b, IF(crit_c, c, d)))
)
)
)
),
Oddly_pass_2, LAMBDA(vector,
LAMBDA(v, i, j,
LET(
current_col, CHOOSECOLS(vector, j),
edge_a, k - j,
edge_b, k - j + 1,
a, SMALL(current_col, i + j),
b, SMALL(current_col, j + i - 1),
c, SMALL(current_col, i - edge_a),
d, SMALL(current_col, i - edge_b),
crit_A, (j < half + 1) * (j + i <= k),
crit_b, (j > half + 1) * (j + i - 1 <= k),
crit_c, (j < half + 1) * (j + i > k),
IF(
j = half + 1,
v,
IF(crit_A, a, IF(crit_b, b, IF(crit_c, c, d)))
)
)
)
),
Oddly_shift, MAP(M, i, j, Oddly_pass_1(M)),
Oddly, MAP(Oddly_shift, i, j, Oddly_pass_2(Oddly_shift)),
IF(
ISODD(n),
//Create magic square by applying oddly method.
Oddly,
//Proceed with singly even method. The matrix is split into
//4 smaller odd matrices so the oddly approach may be used.
//Some additional shifting and 'swapping' is done before the square
//is finalized.
LET(
M_a, SEQUENCE(k, k, @INDEX(quarts, 1)),
M_b, 1 + SEQUENCE(k, k, @INDEX(quarts, 2)),
M_c, 1 + SEQUENCE(k, k, @INDEX(quarts, 3)),
M_d, 1 + SEQUENCE(k, k, @INDEX(quarts, 4)),
A₁, MAP(M_a, i, j, Oddly_pass_1(M_a)),
B₁, MAP(M_b, i, j, Oddly_pass_1(M_b)),
C₁, MAP(M_c, i, j, Oddly_pass_1(M_c)),
D₁, MAP(M_d, i, j, Oddly_pass_1(M_d)),
A₂, MAP(A₁, i, j, Oddly_pass_2(A₁)),
B₂, MAP(B₁, i, j, Oddly_pass_2(B₁)),
C₂, MAP(C₁, i, j, Oddly_pass_2(C₁)),
D₂, MAP(D₁, i, j, Oddly_pass_2(D₁)),
swap, LAMBDA(before, after,
LAMBDA(before, after, i, j,
IF(
(i = w) * (j > 1) * (j <= w),
after,
IF((i <> w) * (j < w), after, before)
)
)
),
a₃, MAP(A₂, D₂, i, j, swap(A₂, D₂)),
d₃, MAP(D₂, A₂, i, j, swap(D₂, A₂)),
cb, VSTACK(
HSTACK(
DROP(C₂, , -(half - 1)),
TAKE(B₂, , -(half - 1))
),
HSTACK(
DROP(B₂, , -(half - 1)),
TAKE(C₂, , -(half - 1))
)
),
cb₃, IF(half - 1 = 0, VSTACK(C₂, B₂), cb),
HSTACK(VSTACK(a₃, d₃), cb₃)
)
)
)
);
- Thanks for the tip. Does this apply to all Excel versions?
