Odd-Sided Magic Squares -- De La Loubère's Algorithm

Scripting Forums Code Exchange
#1

A magic square is a square array of integers arranged so that the rows, columns, and main diagonals all have the same sum. For odd-number-sided basic* magic squares of order 3 or more, there’s an algorithm devised by De La Loubère in the late seventeenth century to construct one. For an elegant step-by-step illustration of how De La Loubère’s algorithm proceeds in its staircase fashion see:

http://britton.disted.camosun.bc.ca/magicsq/magic_7x7.html

  • A “basic” magic square, by the way, starts with a 1 and is constructed with all the numbers required to fill the grid in sequence (e.g., for a 5-sided square, the numbers run from 1 to 25 with the “1” centered in the top row and the “25” centered in the bottom row).

The algorithm starts with 1 in the center cell of the top row, and assuming wrapping from side to side and top to bottom it follows this procedure:

  1. From the starting 1 in the top center cell, move one cell up and one to the left.
  2. If the cell is not zero (empty), write the next number in sequence and continue.
  3. If the cell is not empty, move down one cell in the column and test again.
  4. Repeat steps 1 through 3 until all cells are filled.
    When completed, the sum of any column, any row, or either diagonal is given by:
    Sum = (N^3 + N) / 2.

From: http://www.markfarrar.co.uk/msqodd01.htm where C and Python versions are given as well.

The script below uses display dialog to display the magic squares up to order 9. It gets ugly after that. This is just the outcome of translation from the Basic program given in Farrar’s site to AppleScript. It does seem that the staircase might have been better generated with modular arithmetic, but I didn’t come up with a way to do it given the necessity for wrapping and for dropping down one row if a target square is filled. There is a complementary magic square for any of these as well – just subtract each entry from N^2 + 1. It has the same sum, of course.

repeat -- check for a number, that it is odd, and that it is larger than 2
	set N to text returned of (display dialog "Enter an odd number larger than one" & return & "as the number of rows and columns of" & return & "a magic square." default answer "")
	try
		set N to N as integer
	on error
		display alert N & " is not a number! Exiting now."
		return
	end try
	-- check for 3 or more and oddness.
	if (N < 3) or ((N mod 2) = 0) then
		display alert "The number must be odd and greater than 2."
	else
		exit repeat
	end if
end repeat
set SQ to return -- just to avoid the leading quotation mark.
-- Create a list of N^2 items filled with zeros.
set SQ to {} -- holder for the answer.
set NumCells to N * N
repeat with k from 1 to NumCells
	set end of SQ to 0
end repeat
(* 
Find the starting point; the staircased magic square cell that is one step backwards from the center of the top row so the algrorithm will move to it as its first step and place a 1 there.
*)
set idx to ((N + 1) / 2) + (N - 1) -- the index of the square one move back from the center top cell in the algorithm's sequence , i.e., the first step of the repeat loop will set the index to that of the center top cell.
-- The loop to execute the staircase.
repeat with j from 1 to NumCells
	set idx1 to idx - (idx div N) * N
	if idx1 = 0 then set idx1 to N
	set idx2 to ((idx - idx1) / N) + 1
	if idx1 = N then
		set idx3 to 1
	else
		set idx3 to idx1 + 1
	end if
	if idx2 = 1 then
		set idx4 to N
	else
		set idx4 to idx2 - 1
	end if
	set idx5 to ((idx4 - 1) * N) + idx3
	if idx2 = N then
		set idx6 to 1
	else
		set idx6 to 0
	end if
	if item idx5 of SQ ≠ 0 then
		set idx3 to idx1
		set idx4 to (idx2 + 1) - (idx6 * N)
	end if
	set idx5 to ((idx4 - 1) * N) + idx3
	set item idx5 of SQ to j
	set idx to idx5
end repeat -- end of staircase loop.
-- Now the list of the numbers, needs presentation as text.
set AddsTo to ((N * N * N) + N) / 2
set Magic to ""
repeat with p from 1 to NumCells
	set cell to pad((item p of SQ) as text)
	set Magic to Magic & cell & tab
	if p mod N = 0 then set Magic to Magic & return
end repeat
display dialog Magic & return & "The sum is " & AddsTo
11
to pad(x) -- just to make the dialog box look a bit better.
	if (length of x) < 2 then
		set x to space & space & x
		return x
	else
		return x
	end if
end pad
#2

Thanks, Adam! Something fun and interesting. :slight_smile:

I’ve had a go at the modular arithmetic you mentioned. I found it easier to maintain vertical and horizontal indices rather than work from the current linear position in the list. I also noticed that the number of insertions before an already-occupied cell is encountered is always N, so it’s possible to check for ‘(i mod N = 1)’ and go directly to the appropriate next slot instead of calculating where the next slot should be, seeing if it’s occupied, and calculating the alternative if it is.

The code below replaces everything in your script from ‘set idx to ((N + 1) / 2) + (N - 1)’ to the end of the staircase loop:

set v to -1 -- Vertical index. (Counts from 0.) Preset to an imaginary row above the grid.
set h to N div 2 -- Horizontal index. (Counts from 0.) Preset to the centre column.
repeat with i from 1 to NumCells
	if (i mod N is 1) then -- Index the row below. (Same column.)
		set v to v + 1
	else -- Index the cell one up and one to the right, with wrap round if appropriate.
		set v to (v + N - 1) mod N
		set h to (h + 1) mod N
	end if
	set item (v * N + h + 1) of SQ to i -- Convert grid position to list position and insert i.
end repeat -- end of staircase loop.
#3

Beautiful, Nigel; the keys (I see now) are to work in x and y coordinates (where up and over are simple) instead of linear list coordinates, and to recognize that a jump down (instead of up and over) would occur every Nth insertion. I missed that neat trick entirely and I should have seen it in the demo of the 7 by 7 in my first link.

Trés élégant; perspicacious, even.