Pan Magic Squares

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

Generate multiple (as many as desired) magic squares of a specified size. 

 

Background & Techniques

This program doesn't really solve the above problem, but it may be a first step.  It will generate what I think are all 115,139 pan-magic squares of order 5.  This is 4 times the widely published number of 28,800 so either I'll be revising this page, or several other sites will be revising theirs. 

I recently needed some magic squares for another project and realized that I did not have a generator. In fact,  there did not seem to be a Delphi version available online, so here is my first attempt at one.
 

A "Magic Square" of odd order N is a square array of integers 1 through N2 with the the property that the sum of integers each row, each column, and each of the 2 diagonals are all equal .  The value of the magic sum is for order N is N(1+N2)/2.  Panmagic (also called pandiagonal) squares have the added property that the (2N-2) broken diagonals also add to the magic sum.   There are 8 of these for order 5 squares.

There does not appear to be an algorithm for generating all magic squares, even of odd order, which are more amenable to solution than even order squares. Two methods of generating 5x5 magic squares are implemented here. Neither one is very complete even for 5x5 squares (of which there are apparently several million). This program can generate 115,000 or so with the "panmagic" property.

There is a discussion and generalization of the common De La Loubere's algorithm for generating squares of odd order in Bell and Coxeter's "Mathematical Recreations and Essays". Starting with an array of blank cells, there are two rules for generating entries.  Starting with "1", apply a specified (a,b) increment to it's column and row to get the cell for the next sequential integer. If the target cell is already occupied, a second "jump" (a+a', b+b') increment rule is applied.

These rules only generate a small subset of all possible magic squares. The 625 possible rules (5 choices each for column/row increments for the primary rule and for the jump rule) generate 1472 squares. . 32 of these are "panmagic" magic squares with the additional property that the broken diagonal also add to the common sum. These Panmagic square rules have the characteristic that a magic square can be generated for every starting cell. In other words, each of the 32 rule sets can generate 24 additional squares with every integer appearing in very location for some square, 768 in total.   So the total generated, if implemented, would be 2240 (that is 1472 +768) plus whatever additional might be created  by rotating and mirroring the panmagics.

The second algorithm uses the fact that 2 Latin squares can be combined to form a Greco-Latin square which is panmagic. See the GL section below or look online for more information. I found 576 squares, all panmagic, with 1 in the top-left corner.  Since 24 more (with the other 24 digits in the top left corner) can be generated for each of these, there are 14,400 (576 x 25) squares before considering the effect of rotating and "mirroring" which, in theory, should make 8x14,000 or 115,200. The "Generate all Panmagic" page does this, checking for duplicates as the squares are generated. I found 61 duplicates, which leaves 115,139 different 5x5
panmagic squares. These numbers do not match any that I've seen published elsewhere, so I may have a bug or overlooked something obvious.  

The "Generate" page in the program allows the generated squares to be saved in a text file format for further study.   

The "De La Loubere" Algorithm

The "De La Loubere" rule for generating odd order magic squares requires a "1' in the middle of the top row and consecutive moves generated by moving forward and up one square so long as the target cell is empty (Normal move vector V1=(1,-1)). If the target cell is already occupied, place the number one cell below the
last placed number (jump vector V2=(0,1)). You can enter your own values in the vector cells above to investigate other move combinations.

The resulting magic square is generally not "panmagic", a type where the broken diagonals also add to the magic sum.  Panmagic squares may be cut between any two rows or  columns and the pieces reversed producing a new magic square. This allows any of the N^2 numbers to appear in the upper left corner (or any other desired position) in the square. The list at left identifies the 2 move combinations which will
generate panmagic squares. Click one of the vector lines to generate a square. You can click on any cell of the square and enter any number from 1 to 25 to allow the Generate button to create a magic sqaure with that value in that position.

Greco-Latin Squares

This page is based largely on information provided by Alan Grogono at found at www.grogono.com/magic/5x5.php. A Latin square of size N contains N different symbols placed so that each
symbol occurs only once in each column and each row.  In a Greco-Latin square, two Latin squares, each with
different symbols are overlapped so that each of the N*N   combinations of the symbols appears once in each of the cells. Historically, investigations used Roman (Latin) letters for one of the squares and Greek letters for the others, hence the name Greco-Latin squares.

If we consider the numbers in a magic square running from 0 to N^2-1, they can be expressed in base N as 2
digit numbers 00, 01,... (N-1)(N-1). Eg. 00 to 44 a 5x5 square. (44 base 5 = 24 base 10). If the left digits are
arranged into a Latin square and the rightmost digits in another Latin square, the concatenation of the two into
a Greco-Latin square defines a magic square! Translating back to base 10 and adding 1 to each value
display the traditional style magic square from with numbers from 1 to N^2.

Grogono uses capital letters for the radix (leftmost) digits and lower case for the rightmost digit. He claims
that the pattern in the table at left will generate all panmagic squares of which there are 144. Each has 25
variants with a different number in the top left corner and 8 variants for rotations producing 144*25*8=28,800
different squares. I have not verified that his 144 are all of the primitive squares. He keeps A=1 and B=2 and
permutes C, D, and E values (the first 6 entries in Radix Table at right). Including B values in the permutation
generates 576 squares which are not identical and in fact do not all seem to be isomorphic to the 144 in his
original set. 

Generating Squares

Click the button above to generate all of the order 5 pan-magic squares that I can find. The 576 Greco-Latin squares with 1 in the upper left corner are translated so that each of the other 24 numbers appear there. Those squares are then rotated 90 degrees three times, "flipped over" and and rotated three more times creating 7 additional squares for each.

The process generates 115,200 (576x25x8) squares. From this total 61 duplicates are eliminated, producing 115,139 squares. The squares may be save in a text file with one 75 character record per square. Each record contains the 25 numbers by row, each 2 digit number preceded by a blank character.
 

Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.

Programmer's Notes:

There is not much novel programming here. 

Most of the problems were mathematical, such as how to manipulate a 2 dimensional array which has been collapsed into a string (5X5 with 3 characters per cell in this case but could be easily generalized): 

bulletMove a row from top to bottom.
bulletvar r:string;
begin
    r:=copy(key,1,15); {get the first row (5 string entries of length 3}
    delete(key,1,15); {delete it}
    key:=key+r; {add it to the end}
end;
bulletMove a column from first to last
bulletvar
    i:integer;
    c:string;
begin
    for i:=4 downto 0 do
    begin
        c:=copy(key,i*15+1,3); {get the 1st entry from each row}
        insert(c,key,i*15+16); {Insert it at the right end of that row}
        delete(key,i*15+1,3); {delete it from the left end}
    end;
end;
bulletRotate array by 90 degrees.
bulletvar
    i, j :integer;
    temp:string;
begin
    temp:='';
    for i:=0 to 4 do
    for j:=4 downto 0 do
     {move entries bottom to top of columns from left to right to
                rows from left to right and top to bottom }
        temp:=temp+copy(key,15*j+3*i+1,3);
     key:=temp;
end;
bulletFlip (mirror) an array
bulletvar
    r :string;
    i :integer;
begin
    r:='';
    {Move 5 rows in reverse order to invert the square }
    for i:=4 downto 0 do
    {each row is 15 characters long, 5 columns of 3 characters each
        so we'll make a new output string by adding 15 characters at a time
        as we move backwards though the input string}
    r:= r+ copy(key,15*i+1,15);
    key:=r;
end;

 

Also, there are two arrays that are used to generate magic squares using the Greco-Latin technique.  I wanted clicking on either one to generate a magic square for the currently selected rows, so a common "OnClick" exit is used.   When the user want to generate all possible squares, the same code is called as each entry in the second array is selected for each row in the first array.  But to avoid generating the same square twice when the row is changed in the first table, we need to disable the generation.  I did this by setting its "OnClick" exit to Nil before starting the generate loop and restoring it when all had been created.

Running/Exploring the Program 

bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

Keys used to define squares are saved as 75 character strings (2 digits for each cell separated by a space).  This makes it easy to read, but may not be the most efficient space wise.  One byte per cell value would reduce length by 2/3.    
.Further work is needed to generate magic squares which are not panmagic.
   

 

Original:  July 3, 2008

Modified:  July 29, 2017

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.