# Relaxed magic squares

I found the definition that a relaxed magic square of type $n\times n$ has row and column sums constant, and all numbers from $1$ to $n^2$ appears exactly once. How can one enumerate those, like how many $4\times 4$ squares has of upper left number at most $5$?

• The word enumerate often has the slightly specialized meaning in combinatorics of "list all possibilities", as opposed to simply "count all possibilities". Is that the case with your Question? – hardmath Aug 16 '14 at 21:02
• You might be able to simplify the problem with a bit of group theory... note that relaxed magic square are preserved under row or column swap and rotations. – Jack M Aug 16 '14 at 21:05
• I'm trying to find a method to count the number of squres having upper left corner at most 5. – student Aug 16 '14 at 21:08
• I hope this isn't a stupid remark, but have you tried exhaustive computer search? Computers are really good for that kind of thing. – MJD Aug 16 '14 at 21:26
• Since your question is “How can one enumerate those”, my answer is: get better at programming the computer to perform exhaustive searches. There is a body of technique you can learn that will help you solve this particular kind of problem. Alas, a more detailed answer would be too long for a comment, and is off-topic for this site anyway. – MJD Aug 16 '14 at 22:55

Using a modfied version of the Perl program at this MSE link that is deterministic rather than randomized I was able to confirm the count $171720$ of the total number of relaxed magic squares with a value from one to five in the upper left corner. (The Perl script could probably profit from a re-write in C.)

This is the beginning of the list:

001 002 015 016
006 011 007 010
013 012 004 005
014 009 008 003

001 002 015 016
006 011 007 010
014 009 008 003
013 012 004 005

001 002 015 016
006 011 010 007
013 009 004 008
014 012 005 003

001 002 015 016
006 011 010 007
014 012 005 003
013 009 004 008

001 002 015 016
007 008 009 010
012 011 006 005
014 013 004 003

001 002 015 016
007 008 009 010
012 013 004 005
014 011 006 003

001 002 015 016
007 008 009 010
012 013 006 003
014 011 004 005

001 002 015 016
007 008 009 010
014 011 004 005
012 013 006 003

001 002 015 016
007 008 009 010
014 011 006 003
012 013 004 005

001 002 015 016
007 008 009 010
014 013 004 003
012 011 006 005

001 002 015 016
007 008 010 009
012 011 005 006
014 013 004 003

001 002 015 016
007 008 010 009
012 011 006 005
014 013 003 004

001 002 015 016
007 008 010 009
014 013 003 004
012 011 006 005

001 002 015 016
007 008 010 009
014 013 004 003
012 011 005 006

001 002 015 016
007 010 006 011
012 013 005 004
014 009 008 003

001 002 015 016
007 010 006 011
014 009 008 003
012 013 005 004

001 002 015 016
007 010 011 006
012 009 005 008
014 013 003 004

001 002 015 016
007 010 011 006
012 013 005 004
014 009 003 008

001 002 015 016
007 010 011 006
014 009 003 008
012 013 005 004

001 002 015 016
007 010 011 006
014 013 003 004
012 009 005 008

001 002 015 016
007 011 006 010
012 008 009 005
014 013 004 003

001 002 015 016
007 011 006 010
012 013 004 005
014 008 009 003


And this is the end of the list:

005 016 012 001
015 003 002 014
010 007 011 006
004 008 009 013

005 016 012 001
015 003 002 014
010 009 007 008
004 006 013 011

005 016 012 001
015 006 002 011
004 003 013 014
010 009 007 008

005 016 012 001
015 006 002 011
004 009 007 014
010 003 013 008

005 016 012 001
015 006 002 011
004 009 013 008
010 003 007 014

005 016 012 001
015 006 002 011
010 003 007 014
004 009 013 008

005 016 012 001
015 006 002 011
010 003 013 008
004 009 007 014

005 016 012 001
015 006 002 011
010 009 007 008
004 003 013 014

005 016 012 001
015 008 002 009
003 004 013 014
011 006 007 010

005 016 012 001
015 008 002 009
004 003 014 013
010 007 006 011

005 016 012 001
015 008 002 009
010 007 006 011
004 003 014 013

005 016 012 001
015 008 002 009
011 006 007 010
003 004 013 014

005 016 012 001
015 009 002 008
004 003 013 014
010 006 007 011

005 016 012 001
015 009 002 008
004 006 013 011
010 003 007 014

005 016 012 001
015 009 002 008
010 003 007 014
004 006 013 011

005 016 012 001
015 009 002 008
010 006 007 011
004 003 013 014

005 016 012 001
015 009 004 006
003 007 010 014
011 002 008 013

005 016 012 001
015 009 004 006
011 002 008 013
003 007 010 014


Here is a central segment:

003 009 014 008
016 006 001 011
002 015 012 005
013 004 007 010

003 009 014 008
016 006 001 011
005 004 012 013
010 015 007 002

003 009 014 008
016 006 001 011
005 012 004 013
010 007 015 002

003 009 014 008
016 006 001 011
005 012 015 002
010 007 004 013

003 009 014 008
016 006 001 011
005 015 012 002
010 004 007 013

003 009 014 008
016 006 001 011
010 004 007 013
005 015 012 002

003 009 014 008
016 006 001 011
010 007 004 013
005 012 015 002

003 009 014 008
016 006 001 011
010 007 015 002
005 012 004 013

003 009 014 008
016 006 001 011
010 015 007 002
005 004 012 013

003 009 014 008
016 006 001 011
013 004 007 010
002 015 012 005

003 009 014 008
016 006 001 011
013 004 012 005
002 015 007 010

003 009 014 008
016 006 001 011
013 007 004 010
002 012 015 005

003 009 014 008
016 006 001 011
013 012 004 005
002 007 015 010

003 009 014 008
016 006 011 001
002 012 005 015
013 007 004 010

003 009 014 008
016 006 011 001
005 015 002 012
010 004 007 013

003 009 014 008
016 006 011 001
010 004 007 013
005 015 002 012


I can post the code if anyone is interested though like I said a re-write in C would probably be the better choice.

For any integer $n \ge 0$, $\begin{bmatrix}2&13+n&12&7\\11&8&1&14+n\\5&10&15+n&4\\16+n&3&6&9 \end{bmatrix}$ is a magic square with an upper left number of $2$. This gives us infinitely many such magic squares satisfying the given conditions.

EDIT: The above was posted before the OP added the constraint that the relaxed magic square contain each of the integers between $1$ and $n^2$ exactly once.

• Often a 4×4 magic square is restricted to contain exactly the elements 1…16. – MJD Aug 16 '14 at 22:32

I am posting a solution in C which is blazingly fast compared to the Perl program. (I worked on this problem before but I cannot now seem to locate the post.) The C program takes minutes to solve a problem where Perl takes hours even though both use the same algorithm. Note that we can do much better with a randomized algorithm, but here the problem seems to ask for a deterministic solution.

Here is a central segment for the four by four:

004 011 006 013
014 016 001 003
007 005 012 010
009 002 015 008

004 011 006 013
014 016 001 003
009 002 015 008
007 005 012 010

004 011 006 013
014 016 001 003
009 005 012 008
007 002 015 010

004 011 006 013
014 016 003 001
007 005 010 012
009 002 015 008

004 011 006 013
014 016 003 001
009 002 015 008
007 005 010 012

004 011 006 013
015 001 016 002
003 014 007 010
012 008 005 009

004 011 006 013
015 001 016 002
005 008 009 012
010 014 003 007


The output of the deterministic algorithm for the five-by-five starts with

001 002 013 024 025
003 008 014 017 023
018 016 015 009 007
021 019 011 010 004
022 020 012 005 006

001 002 013 024 025
003 008 014 017 023
018 016 015 009 007
022 020 012 005 006
021 019 011 010 004

001 002 013 024 025
003 008 014 017 023
018 016 015 010 006
021 019 012 009 004
022 020 011 005 007

001 002 013 024 025
003 008 014 017 023
018 016 015 010 006
021 020 011 009 004
022 019 012 005 007

001 002 013 024 025
003 008 014 017 023
018 016 015 010 006
021 020 012 005 007
022 019 011 009 004

001 002 013 024 025
003 008 014 017 023
018 016 015 010 006
022 019 011 009 004
021 020 012 005 007

001 002 013 024 025
003 008 014 017 023
018 016 015 010 006
022 019 012 005 007
021 020 011 009 004

001 002 013 024 025
003 008 014 017 023
018 016 015 010 006
022 020 011 005 007
021 019 012 009 004


Now for the five-by-five and the six-by-six I had the algorithm start by assigning a random order to the values being tried and continue deterministically thereafter, which will continue to produce all assignments, only in a different order. This gave the following segment for the five-by-five:

001 002 023 020 019
005 018 003 014 025
022 015 017 007 004
013 021 012 008 011
024 009 010 016 006

001 002 023 020 019
005 018 003 014 025
022 015 017 004 007
024 009 010 016 006
013 021 012 011 008

001 002 023 020 019
005 018 003 014 025
022 015 017 004 007
013 021 012 011 008
024 009 010 016 006

001 002 023 020 019
005 018 003 014 025
022 015 013 008 007
021 006 017 011 010
016 024 009 012 004

001 002 023 020 019
005 018 003 014 025
022 015 013 008 007
016 024 009 012 004
021 006 017 011 010

001 002 023 020 019
005 018 003 014 025
022 015 010 007 011
024 009 012 016 004
013 021 017 008 006

001 002 023 020 019
005 018 003 014 025
022 015 010 007 011
013 021 017 008 006
024 009 012 016 004


For the six-by-six, we get the segment

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 015 026 018
023 002 019 020 030 017
014 003 022 011 032 029

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 015 026 018
014 003 022 011 032 029
023 002 019 020 030 017

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 011 030 018
023 003 022 020 026 017
014 002 019 015 032 029

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 011 030 018
023 002 022 015 032 017
014 003 019 020 026 029

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 011 030 018
014 003 019 020 026 029
023 002 022 015 032 017

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 011 030 018
014 002 019 015 032 029
023 003 022 020 026 017

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 018 026 015
023 003 022 011 032 020
014 002 019 017 030 029


And this is the code, compiled with GCC 4.8.3.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void search(int **sq, int N, int sum, int sofar, int *seen,
int *cref, int pflag)
{
int row, col;

if(sofar == N*N){
if(pflag){
for(row = 0; row < N; row++){
for(col = 0; col < N; col++){
printf("%03d ", sq[row][col]);
}
printf("\n");
}
printf("\n");
}

(*cref)++;
return;
}

int loc_col = sofar % N;
int loc_row = (sofar - loc_col) / N;

int nxt;
for(nxt = 1; nxt <= N*N; nxt++){
if(!seen[nxt]){
sq[loc_row][loc_col] = nxt;
seen[nxt] = 1;

int no_admit = 0, empty, sval;

for(row = 0; row < N; row++){
empty = 0; sval = 0;

for(col = 0; col < N; col++){
if(sq[row][col] == -1){
empty++;
}
else{
sval += sq[row][col];
}
}

if((empty == 0 && sval != sum) ||
(empty > 0 && sval >= sum)){
break;
}
}

for(col = 0; col < N; col++){
empty = 0; sval = 0;

for(row = 0; row < N; row++){
if(sq[row][col] == -1){
empty++;
}
else{
sval += sq[row][col];
}
}

if((empty == 0 && sval != sum) ||
(empty > 0 && sval >= sum)){
break;
}
}

search(sq, N, sum, sofar + 1, seen,
cref, pflag);
}

seen[nxt] = 0;
sq[loc_row][loc_col] = -1;
}
}
}

int main(int argc, char **argv)
{
int printflag = 1;
int N = 4;
int maxcorner = 5;

if(argc > 1){
printflag = (!strcmp(argv[1], "yes") ? 1 : 0);
}

if(argc > 2){
N = atoi(argv[2]);

if(N < 1){
fprintf(stderr, "dimension is a positive int, "
"got %d\n", N);
exit(-1);
}
}

if(argc > 3){
maxcorner = atoi(argv[3]);

if(maxcorner < 1 || maxcorner > N*N){
fprintf(stderr, "max corner is a positive int "
"less than %d, got %d", N*N, maxcorner);
exit(-2);
}
}

int buf[N*N];
int *sq[N];

int row, col;
for(row = 0; row < N; row++){
sq[row] = buf + row*N;

for(col = 0; col < N; col++){
sq[row][col] = -1;
}
}

int sum = N*(N*N+1)/2;

int pos, seen[N*N+1];
for(pos = 0; pos < N*N+1; pos++){
seen[pos] = 0;
}

int count = 0; int corner;
for(corner = 1; corner <= maxcorner; corner++){
sq[0][0] = corner; seen[corner] = 1;

search(sq, N, sum, 1, seen, &count, printflag);

sq[0][0] = -1; seen[corner] = 0;
}

fprintf(stderr, "%d\n", count);

return 0;
}


Addendum. Here is a seven-by-seven that the second version produced:

001 011 034 038 009 035 047
041 015 018 032 014 033 022
036 026 048 025 017 010 013
042 029 008 006 049 021 020
045 012 019 030 027 037 005
003 039 002 040 031 016 044
007 043 046 004 028 023 024

001 011 034 038 009 035 047
041 015 018 032 014 033 022
036 026 048 025 017 010 013
042 029 008 006 049 021 020
045 012 019 030 027 037 005
007 043 046 004 028 023 024
003 039 002 040 031 016 044