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$?
2026-03-25 09:33:23.1774431203
On
On
Relaxed magic squares
165 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
3
There are 3 best solutions below
1
On
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.
0
On
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)){
no_admit = 1;
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)){
no_admit = 1;
break;
}
}
if(!no_admit){
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
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:
And this is the end of the list:
Here is a central segment:
I can post the code if anyone is interested though like I said a re-write in C would probably be the better choice.